← Πίσω στην αρχική

🕸️ Κεφάλαιο 3: Δομές Δεδομένων (ΓΡΑΦΟΙ)

Θεωρία, Ερωτήσεις Ανάπτυξης, Quiz & Ασκήσεις

📌 Ορισμός Γράφου

Ένας γράφος (graph) αποτελείται από:

  • Ένα σύνολο κόμβων (ή σημείων ή κορυφών — vertices/nodes).
  • Ένα σύνολο ακμών (ή γραμμών ή τόξων — edges/arcs) που ενώνουν μερικούς ή όλους τους κόμβους.

Πολλά προβλήματα και καταστάσεις της καθημερινής μας ζωής μπορούν να περιγραφούν με τη βοήθεια γράφων. Για παράδειγμα, τα σημεία ενός γράφου μπορούν να αναπαριστούν πόλεις και οι γραμμές τις οδικές συνδέσεις μεταξύ τους.

📚 Θεωρία Γράφων: Λόγω της μεγάλης πληθώρας και ποικιλίας των προβλημάτων που σχετίζονται με γράφους, έχει αναπτυχθεί ομώνυμη θεωρία, η Θεωρία Γράφων, η οποία συχνά αποτελεί αυτοδύναμο μάθημα σε πανεπιστημιακά ιδρύματα.

🔗 Σχέση Γράφου με Άλλες Δομές

Ο γράφος αποτελεί την πιο γενική δομή δεδομένων, με την έννοια ότι όλες οι προηγούμενες δομές που παρουσιάστηκαν (λίστες, στοίβες, ουρές, δένδρα) μπορούν να θεωρηθούν ειδικές περιπτώσεις γράφων.

💡 Συμπέρασμα: Ο γράφος είναι η «μητέρα» όλων των δυναμικών δομών. Κάθε άλλη δομή επιβάλλει επιπλέον περιορισμούς πάνω στον γράφο.

🌳 Διαφορά Γράφου από Δένδρο

Τα δένδρα διέπονται από συγκεκριμένους κανόνες που δεν ισχύουν για τους γράφους:

Χαρακτηριστικό Δένδρο Γράφος
Κατεύθυνση Ρέει μόνο από ρίζα σε φύλλα (μονοδρομική ροή) Οι κόμβοι συνδέονται με οποιονδήποτε τρόπο
Γονέας Κάθε κόμβος (εκτός ρίζας) έχει ακριβώς 1 γονέα Ένας κόμβος μπορεί να συνδεθεί με οσουσδήποτε άλλους
Κύκλοι Δεν επιτρέπονται βρόχοι ή κυκλικοί δεσμοί Επιτρέπονται κύκλοι και βρόχοι
Ρίζα Υπάρχει ένας κόμβος ρίζα χωρίς γονέα Δεν υπάρχει έννοια ρίζας
Κατεύθυνση ακμών Μονοκατευθυντικές συνδέσεις Μπορεί να έχουν κατεύθυνση ή όχι
🔑 Κλειδί: Τα δένδρα είναι στην πραγματικότητα ένα υποσύνολο των γράφων. Ένα δένδρο θα είναι πάντα ένας γράφος, αλλά δεν είναι όλοι οι γράφοι δένδρα. Οι γράφοι διαφέρουν από τα δένδρα στο ότι δεν έχουν όλους τους περιορισμούς που έχουν τα δένδρα.

➡️ Δύο Βασικοί Τύποι Γράφων

Δύο τύποι γράφων είναι αρκετά εύκολο να εντοπιστούν και είναι αρκετά συνηθισμένοι στα προβλήματα θεωρίας γράφων:

1. Κατευθυνόμενος Γράφος (Directed Graph)

Οι ακμές έχουν κατεύθυνση. Μπορούμε να ταξιδέψουμε μόνο από την προέλευση στον προορισμό.

Κατευθυνόμενη ακμή:

   A ———→ B

Μπορούμε να πάμε μόνο από A → B,
όχι από B → A.

2. Μη Κατευθυνόμενος Γράφος (Undirected Graph)

Οι ακμές δεν έχουν κατεύθυνση. Η διαδρομή μεταξύ δύο κόμβων είναι αμφίδρομη.

Μη κατευθυνόμενη ακμή:

   A ——— B

Μπορούμε να πάμε από A → B
και από B → A.
📌 Ορισμός:
  • Αν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση → κατευθυνόμενος γράφος.
  • Αν όλες οι ακμές δεν έχουν κατεύθυνση → μη κατευθυνόμενος γράφος.

🌐 Παραδείγματα Χρήσης Γράφων

1. Παγκόσμιος Ιστός (World Wide Web)

Ο Παγκόσμιος Ιστός (www) είναι ένας τεράστιος γράφος. Όταν κάνουμε κλικ ανάμεσα σε ιστοσελίδες και «σερφάρουμε» από τον ένα ιστότοπο στον άλλο, κάνουμε περιήγηση σε έναν γράφο.

  • Οι ιστοσελίδες είναι οι κόμβοι.
  • Οι συνδέσεις (links) μεταξύ τους είναι οι ακμές.
  • Μερικές ακμές είναι μη κατευθυνόμενες (μπορούμε να πάμε από μια ιστοσελίδα σε μια άλλη και αντιστρόφως).
  • Άλλες ακμές είναι κατευθυνόμενες (μπορούμε να πάμε μόνο από τη μία ιστοσελίδα στην άλλη, όχι αντιστρόφως).

2. Κοινωνικά Δίκτυα

Facebook: Είναι ένας τύπος μη κατευθυνόμενου γράφου. Οι χρήστες είναι οι κόμβοι και οι σχέσεις φιλίας είναι οι ακμές. Δεν είναι δυνατόν να είμαι φίλος σου χωρίς να είσαι και δικός μου — η σχέση είναι αμφίδρομη.

Twitter/X: Λειτουργεί διαφορετικά. Μπορώ να σε ακολουθήσω, αλλά δεν απαιτείται να με ακολουθείς κι εσύ. Είναι ένας κατευθυνόμενος γράφος. Η ακμή «ακολουθώ» δημιουργεί μια κατευθυνόμενη σχέση. Αν τυχόν με ακολουθήσεις κι εσύ, δημιουργείται μια δεύτερη ακμή προς την αντίθετη κατεύθυνση.

💡 Συμβουλή: Κάνε κλικ σε κάθε ερώτηση για να δεις την αναλυτική απάντηση.

1. Τι είναι ένας γράφος και από τι αποτελείται;

▼

Ένας γράφος (graph) αποτελείται από:

  • Ένα σύνολο κόμβων (ή σημείων ή κορυφών).
  • Ένα σύνολο ακμών (ή γραμμών ή τόξων) που ενώνουν μερικούς ή όλους τους κόμβους.

Παραδείγματα: πόλεις (κόμβοι) και οδικές συνδέσεις (ακμές) μεταξύ τους.

2. Ποια σχέση έχει ο γράφος με τις άλλες δυναμικές δομές δεδομένων;

▼

Ο γράφος αποτελεί την πιο γενική δομή δεδομένων. Όλες οι προηγούμενες δομές (λίστες, στοίβες, ουρές, δένδρα) μπορούν να θεωρηθούν ειδικές περιπτώσεις γράφων, δηλαδή γράφοι με επιπλέον περιορισμούς.

3. Ποια είναι η διαφορά του γράφου από το δένδρο;

▼

Τα δένδρα έχουν περιορισμούς που δεν ισχύουν για τους γράφους:

  • Το δένδρο ρέει μόνο προς μία κατεύθυνση (από ρίζα σε φύλλα). Ο γράφος επιτρέπει οποιαδήποτε σύνδεση.
  • Στο δένδρο κάθε κόμβος (εκτός ρίζας) έχει ακριβώς έναν γονέα. Στο γράφο ένας κόμβος μπορεί να συνδεθεί με οσουσδήποτε άλλους.
  • Το δένδρο δεν επιτρέπει κύκλους (βρόχους). Ο γράφος τους επιτρέπει.
  • Το δένδρο έχει ρίζα. Ο γράφος δεν έχει έννοια ρίζας.
  • Το δένδρο έχει μονοκατευθυντική ροή. Ο γράφος μπορεί να έχει κατεύθυνση ή όχι.

Συμπέρασμα: Τα δένδρα είναι ένα υποσύνολο των γράφων. Ένα δένδρο είναι πάντα γράφος, αλλά δεν είναι όλοι οι γράφοι δένδρα.

4. Τι είναι κατευθυνόμενη ακμή;

▼

Σε μια κατευθυνόμενη ακμή (directed edge), δύο κόμβοι συνδέονται με πολύ συγκεκριμένο τρόπο:

  • Υπάρχει έννοια προέλευσης (ο κόμβος από τον οποίο ξεκινάμε).
  • Υπάρχει έννοια προορισμού (ο κόμβος προς τον οποίο ταξιδεύουμε).
  • Μπορούμε να ταξιδέψουμε μόνο από την προέλευση στον προορισμό, όχι αντιστρόφως.

5. Τι είναι μη κατευθυνόμενη ακμή;

▼

Σε μια μη κατευθυνόμενη ακμή (undirected edge), η διαδρομή μεταξύ των δύο κόμβων είναι αμφίδρομη. Οι κόμβοι προέλευσης και προορισμού δεν διακρίνονται — μπορούμε να μετακινηθούμε και προς τις δύο κατευθύνσεις.

6. Πότε ένας γράφος λέγεται κατευθυνόμενος και πότε μη κατευθυνόμενος;

▼
  • Αν όλες οι ακμές σε έναν γράφο έχουν κατεύθυνση, ο γράφος ονομάζεται κατευθυνόμενος γράφος (directed graph).
  • Αν όλες οι ακμές σε έναν γράφο δεν έχουν κατεύθυνση, ο γράφος ονομάζεται μη κατευθυνόμενος γράφος (undirected graph).

7. Δώστε παραδείγματα χρήσης γράφων από την καθημερινή ζωή.

▼

Παγκόσμιος Ιστός (WWW): Οι ιστοσελίδες είναι κόμβοι και οι υπερσυνδέσεις (links) είναι ακμές. Μερικές συνδέσεις είναι μη κατευθυνόμενες (πάμε και επιστρέφουμε) και άλλες κατευθυνόμενες (μόνο μία κατεύθυνση).

Οδικό δίκτυο: Οι πόλεις είναι κόμβοι και οι δρόμοι είναι ακμές. Οι αμφίδρομοι δρόμοι είναι μη κατευθυνόμενες ακμές, ενώ οι μονόδρομοι είναι κατευθυνόμενες.

Κοινωνικά δίκτυα: Οι χρήστες είναι κόμβοι και οι σχέσεις μεταξύ τους είναι ακμές.

8. Ποιον τύπο γράφου αντιπροσωπεύει το Facebook και γιατί;

▼

Το Facebook αντιπροσωπεύεται ως μη κατευθυνόμενος γράφος. Οι χρήστες είναι οι κόμβοι και οι σχέσεις φιλίας είναι οι ακμές. Η φιλία είναι αμφίδρομη — δεν είναι δυνατόν να είμαι φίλος σου χωρίς να είσαι και δικός μου. Δεν υπάρχει η έννοια κόμβου «προέλευσης» και «προορισμού».

9. Ποιον τύπο γράφου αντιπροσωπεύει το Twitter και γιατί;

▼

Το Twitter αντιπροσωπεύεται ως κατευθυνόμενος γράφος. Μπορώ να σε ακολουθήσω, αλλά δεν απαιτείται να με ακολουθείς κι εσύ. Η σχέση «ακολουθώ» είναι μονόδρομη. Αν τυχόν με ακολουθήσεις κι εσύ, δημιουργείται μια δεύτερη ακμή προς την αντίθετη κατεύθυνση.

10. Είναι όλα τα δένδρα γράφοι; Είναι όλοι οι γράφοι δένδρα;

▼

Ναι, όλα τα δένδρα είναι γράφοι, γιατί τα δένδρα ικανοποιούν τον ορισμό του γράφου (κόμβοι + ακμές) με επιπλέον περιορισμούς.

Όχι, δεν είναι όλοι οι γράφοι δένδρα, γιατί οι γράφοι δεν έχουν τους περιορισμούς των δένδρων (μοναδικός γονέας, απουσία κύκλων, ύπαρξη ρίζας).

🎯 Οδηγίες: Επίλεξε μία απάντηση σε κάθε ερώτηση. Θα δεις άμεση ανατροφοδότηση. Στο τέλος θα εμφανιστεί το συνολικό σου σκορ.

1. Από τι αποτελείται ένας γράφος;

α) Μόνο από κόμβους
β) Από κόμβους και ακμές
γ) Μόνο από ακμές
δ) Από ρίζες και φύλλα

2. Ποια δομή είναι η πιο γενική;

α) Το δένδρο
β) Η λίστα
γ) Ο γράφος
δ) Η στοίβα

3. Μπορεί ένας γράφος να έχει κύκλους;

α) Ναι
β) Όχι, ποτέ
γ) Μόνο αν είναι δένδρο
δ) Μόνο αν είναι λίστα

4. Ποιος από τους παρακάτω περιορισμούς ΔΕΝ ισχύει για τους γράφους;

α) Οι κόμβοι μπορούν να συνδέονται με οποιονδήποτε τρόπο
β) Οι ακμές μπορούν να έχουν κατεύθυνση
γ) Μπορούν να υπάρχουν κύκλοι
δ) Κάθε κόμβος πρέπει να έχει ακριβώς έναν γονέα

5. Σε μια κατευθυνόμενη ακμή, πώς ταξιδεύουμε;

α) Και προς τις δύο κατευθύνσεις
β) Μόνο από προέλευση σε προορισμό
γ) Μόνο από προορισμό σε προέλευση
δ) Με τυχαία κατεύθυνση

6. Σε μια μη κατευθυνόμενη ακμή, η διαδρομή είναι:

α) Αμφίδρομη
β) Μονόδρομη
γ) Μόνο προς τα πάνω
δ) Μόνο προς τα κάτω

7. Το Facebook αντιπροσωπεύεται ως:

α) Κατευθυνόμενος γράφος
β) Δένδρο
γ) Μη κατευθυνόμενος γράφος
δ) Στοίβα

8. Το Twitter αντιπροσωπεύεται ως:

α) Κατευθυνόμενος γράφος
β) Μη κατευθυνόμενος γράφος
γ) Δυαδικό δένδρο
δ) Ουρά

9. Ο Παγκόσμιος Ιστός (WWW) είναι:

α) Ένα δένδρο
β) Ένας τεράστιος γράφος
γ) Μια λίστα
δ) Μια στοίβα

10. Ένα δένδρο είναι πάντα:

α) Ένας γράφος
β) Ένας μη κατευθυνόμενος γράφος
γ) Ένας κατευθυνόμενος γράφος
δ) Κανένα από τα παραπάνω

🏆 Τελικό Σκορ

💪 Προκλήσεις: Προσπάθησε να τις λύσεις μόνος σου πριν δεις την απάντηση!

Άσκηση 1: Αναγνώριση τύπου γράφου

⭐

Δίνεται το παρακάτω σχήμα:

    A ———→ B
    ↑        ↓
    D ←——— C

Ερωτήσεις:

  1. Πόσοι κόμβοι και πόσες ακμές έχει ο γράφος;
  2. Είναι κατευθυνόμενος ή μη κατευθυνόμενος;
  3. Μπορούμε να πάμε από τον A στον C; Εξήγησε.
  4. Υπάρχει κύκλος; Αν ναι, ποιος;

Λύση:

  1. Έχει 4 κόμβους (A, B, C, D) και 4 ακμές.
  2. Είναι κατευθυνόμενος γράφος, γιατί όλες οι ακμές έχουν βέλη (κατεύθυνση).
  3. Ναι, μπορούμε: A → B → C. Δεν μπορούμε όμως C → A απευθείας.
  4. Ναι, υπάρχει κύκλος: A → B → C → D → A. Αυτό αποδεικνύει ότι δεν είναι δένδρο.

Άσκηση 2: Facebook vs Twitter

⭐⭐

Σε ένα κοινωνικό δίκτυο υπάρχουν 4 χρήστες: Άννα, Βασίλης, Γιώργος, Δήμητρα.

Σχέσεις στο Facebook:

  • Άννα είναι φίλη με Βασίλη
  • Βασίλης είναι φίλος με Γιώργο
  • Γιώργος είναι φίλος με Δήμητρα
  • Δήμητρα είναι φίλη με Άννα

Σχέσεις στο Twitter:

  • Άννα ακολουθεί Βασίλη
  • Βασίλης ακολουθεί Γιώργο
  • Γιώργος ακολουθεί Άννα
  • Δήμητρα ακολουθεί Άννα
  • Άννα δεν ακολουθεί Δήμητρα

Ερωτήσεις:

  1. Σχεδίασε τον γράφο του Facebook. Είναι κατευθυνόμενος ή μη;
  2. Σχεδίασε τον γράφο του Twitter. Είναι κατευθυνόμενος ή μη;
  3. Στο Twitter, πόσες ακμές υπάρχουν συνολικά;
  4. Στο Twitter, ο Γιώργος ακολουθεί τη Δήμητρα;

Λύση:

Facebook (μη κατευθυνόμενος):

   Άννα ——— Βασίλης
     |             |
     |             |
   Δήμητρα ——— Γιώργος

Twitter (κατευθυνόμενος):

   Άννα —→ Βασίλης —→ Γιώργος
    ↑                         |
    ↑                         |
   Δήμητρα ←—————————
  1. Ο γράφος του Facebook είναι μη κατευθυνόμενος. Η φιλία είναι αμφίδρομη.
  2. Ο γράφος του Twitter είναι κατευθυνόμενος. Το «ακολουθώ» είναι μονόδρομο.
  3. Στο Twitter υπάρχουν 4 ακμές: Άννα→Βασίλης, Βασίλης→Γιώργος, Γιώργος→Άννα, Δήμητρα→Άννα.
  4. Όχι, ο Γιώργος δεν ακολουθεί τη Δήμητρα. Η Δήμητρα ακολουθεί την Άννα, αλλά δεν υπάρχει ακμή Γιώργος→Δήμητρα.

Άσκηση 3: Δένδρο vs Γράφος

⭐⭐

Εξέτασε τα παρακάτω σχήματα και αποφάσισε αν είναι δένδρο, γράφος (αλλά όχι δένδρο), ή και τα δύο:

Σχήμα Α:
      1
     / | \
    2  3  4
       |
       5

Σχήμα Β:
     A —— B
     |     / |
     C —— D

Σχήμα Γ:
     X —— Y
     |       |
     Z —— W

Ερωτήσεις:

  1. Το Σχήμα Α είναι δένδρο; Είναι γράφος;
  2. Το Σχήμα Β είναι δένδρο; Είναι γράφος;
  3. Το Σχήμα Γ είναι δένδρο; Είναι γράφος;
  4. Ποιο χαρακτηριστικό του Σχήματος Γ το αποκλείει από τα δένδρα;

Λύση:

  1. Το Σχήμα Α είναι δένδρο (και άρα είναι και γράφος). Έχει ρίζα (1), κάθε κόμβος έχει έναν γονέα, δεν έχει κύκλους.
  2. Το Σχήμα Β δεν είναι δένδρο (ο κόμβος B έχει δύο «γονείς»: A και D), αλλά είναι γράφος. Έχει κύκλο A-B-D-C-A.
  3. Το Σχήμα Γ δεν είναι δένδρο (δεν υπάρχει ρίζα, υπάρχει κύκλος X-Y-W-Z-X), αλλά είναι γράφος.
  4. Το Σχήμα Γ έχει κύκλο (X→Y→W→Z→X), κάτι που απαγορεύεται στα δένδρα. Επίσης δεν έχει ρίζα.

Άσκηση 4: Οδικό Δίκτυο

⭐⭐⭐

Μια πόλη έχει 5 σταθμούς μετρό: Σ1, Σ2, Σ3, Σ4, Σ5. Οι συνδέσεις είναι:

  • Σ1 ↔ Σ2 (αμφίδρομη, δύο κατευθύνσεις)
  • Σ2 → Σ3 (μονόδρομη)
  • Σ3 ↔ Σ4 (αμφίδρομη)
  • Σ4 → Σ5 (μονόδρομη)
  • Σ5 → Σ1 (μονόδρομη)

Ερωτήσεις:

  1. Σχεδίασε τον γράφο με βέλη για τις κατευθυνόμενες και γραμμές για τις αμφίδρομες.
  2. Μπορώ να πάω από Σ1 σε Σ5; Περιέγραψε τη διαδρομή.
  3. Μπορώ να πάω από Σ5 σε Σ2; Περιέγραψε τη διαδρομή.
  4. Αν θεωρήσουμε όλες τις αμφίδρομες συνδέσεις ως δύο κατευθυνόμενες ακμές, πόσες ακμές έχει συνολικά ο γράφος;

Λύση:

   Σ1 ———— Σ2
    ↑           ↓
    ↑           ↓
   Σ5 ←—— Σ4 ———— Σ3
  1. Ο γράφος φαίνεται παραπάνω. Οι αμφίδρομες (Σ1↔Σ2, Σ3↔Σ4) έχουν διπλό βέλος ή διπλή γραμμή.
  2. Ναι: Σ1 → Σ2 → Σ3 → Σ4 → Σ5.
  3. Ναι: Σ5 → Σ1 → Σ2. (Η Σ5→Σ1 είναι μονόδρομη, μετά Σ1↔Σ2 είναι αμφίδρομη).
  4. Συνολικές ακμές: Σ1↔Σ2 = 2, Σ2→Σ3 = 1, Σ3↔Σ4 = 2, Σ4→Σ5 = 1, Σ5→Σ1 = 1. Σύνολο: 7 ακμές.

Άσκηση 5: Ιδιότητες Γράφων

⭐⭐⭐

Απάντησε με Σωστό (Σ) ή Λάθος (Λ) στις παρακάτω προτάσεις και δικαιολόγησε:

  1. Κάθε δένδρο είναι γράφος.
  2. Κάθε γράφος είναι δένδρο.
  3. Ένας γράφος μπορεί να έχει κόμβους χωρίς ακμές.
  4. Ένα δένδρο μπορεί να έχει κύκλους.
  5. Σε έναν μη κατευθυνόμενο γράφο, αν υπάρχει ακμή A-B, τότε μπορώ να πάω από B σε A.
  6. Σε έναν κατευθυνόμενο γράφο, αν υπάρχει ακμή A→B, τότε μπορώ να πάω από B σε A.
  7. Ο γράφος είναι πιο περιορισμένη δομή από το δένδρο.
  8. Ο γράφος δεν έχει έννοια ρίζας.

Λύση:

  1. Σ — Το δένδρο αποτελείται από κόμβους και ακμές, άρα ικανοποιεί τον ορισμό του γράφου.
  2. Λ — Οι γράφοι επιτρέπουν κύκλους και πολλαπλούς γονείς, κάτι που απαγορεύεται στα δένδρα.
  3. Σ — Ένας γράφος μπορεί να έχει απομονωμένους κόμβους (χωρίς συνδέσεις).
  4. Λ — Τα δένδρα δεν επιτρέπουν κύκλους. Αν υπάρχει κύκλος, δεν είναι δένδρο.
  5. Σ — Σε μη κατευθυνόμενο γράφο, η ακμή A-B είναι αμφίδρομη.
  6. Λ — Σε κατευθυνόμενο γράφο, η ακμή A→B επιτρέπει μόνο A→B, όχι B→A (εκτός αν υπάρχει ξεχωριστή ακμή B→A).
  7. Λ — Ο γράφος είναι η πιο γενική δομή, άρα λιγότερο περιορισμένος από το δένδρο.
  8. Σ — Ο γράφος δεν έχει έννοια ρίζας. Αυτός ο περιορισμός υπάρχει μόνο στα δένδρα.