Δομές Δεδομένων: Γράφοι

Μάθημα Πληροφορικής Γ' Λυκείου (Ενότητα 1.3.3)

Τι είναι ο Γράφος;

Όπως μάθατε, τα δένδρα έχουν συγκεκριμένους κανόνες (ρίζα, γονείς, παιδιά, όχι κύκλοι). Τι συμβαίνει όμως αν αγνοήσουμε αυτούς τους περιορισμούς; Τότε έχουμε τον Γράφο (Graph).

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

🌲 Δένδρο vs Γράφος

Το δένδρο είναι μια ειδική περίπτωση γράφου.

  • Δένδρο: Έχει ρίζα, ιεραρχία, μοναδική διαδρομή, όχι κύκλους.
  • Γράφος: Δεν έχει ρίζα, οι κόμβοι συνδέονται ελεύθερα, μπορεί να έχει κύκλους (βρόχους).

➡️ Τύποι Ακμών

Η βασική διαφορά στους γράφους είναι το είδος της σύνδεσης:

  • Κατευθυνόμενος (Directed): Η ακμή είναι βέλος (μονόδρομος).
  • Μη κατευθυνόμενος (Undirected): Η ακμή είναι γραμμή (αμφίδρομος).

Διάγραμμα Γράφων (Σχήματα)

Μη Κατευθυνόμενος

(Π.χ. Φιλία στο Facebook)

A B C

Κατευθυνόμενος

(Π.χ. Follow στο Twitter)

A B C

Γράφοι στην Καθημερινότητα

🚗

GPS & Δρόμοι

Όταν το GPS (π.χ. Google Maps) σου δείχνει τη διαδρομή, χρησιμοποιεί γράφους:

  • Κόμβοι: Διασταυρώσεις ή πόλεις.
  • Ακμές: Οι δρόμοι που τις ενώνουν.
🧪

Χημεία (Μόρια)

Στη Χημεία, η δομή ενός μορίου απεικονίζεται ως γράφος:

  • Κόμβοι: Τα άτομα.
  • Ακμές: Οι χημικοί δεσμοί.
✈️

Αεροπορικά Δίκτυα

Πώς ταξιδεύουμε από τη μία χώρα στην άλλη;

  • Κόμβοι: Τα αεροδρόμια.
  • Ακμές: Οι πτήσεις που συνδέουν τα αεροδρόμια.
👥

Facebook

Η σχέση "Φιλίας" είναι αμφίδρομη (Μη Κατευθυνόμενος).

A ── B
🐦

Twitter/Instagram

Η σχέση "Follow" είναι μονόδρομη (Κατευθυνόμενος).

A ➔ B
🌐

WWW (Internet)

Οι ιστοσελίδες είναι κόμβοι και τα Links είναι οι κατευθυνόμενες ακμές.

Το Πρόβλημα των Γεφυρών του Königsberg

Το Πρόβλημα: Στην πόλη Königsberg υπήρχε ο ποταμός Pregel που χώριζε την πόλη σε 4 τμήματα γης. Αυτά συνδέονταν με 7 γέφυρες.

"Μπορείς να διασχίσεις και τις 7 γέφυρες ΑΚΡΙΒΩΣ ΜΙΑ ΦΟΡΑ;"

Βόρεια Όχθη (A) Νότια Όχθη (B) Νησί (C) Νησί (D)

Η Λύση του Euler (Αφαίρεση)

Ο Euler μετέτρεψε τον χάρτη σε Γράφο. Τα νησιά έγιναν κόμβοι και οι γέφυρες ακμές.

A B C D

🧠 Άσκηση Κατανόησης

Κοίταξε τον γράφο του Euler παραπάνω. Πόσες ακμές (γέφυρες) συνδέονται στον κόμβο C;

Ασκήσεις Σχεδίασης στο Εργαστήριο

Διάβασε τα σενάρια και προσπάθησε να τα σχεδιάσεις στο "Εργαστήριο Γράφων"!

Άσκηση 1: "Ποιος βοηθάει ποιον;"

Τύπος Γράφου: Κατευθυνόμενος

Σε μια παρέα 4 μαθητών συμβαίνουν τα εξής:

  • Ο Κόμβος 1 (Ανδρέας) βοηθάει τον Κόμβο 2 (Βασίλη).
  • Ο Κόμβος 2 (Βασίλης) βοηθάει τον Κόμβο 3 (Γιώργο).
  • Ο Κόμβος 3 (Γιώργος) βοηθάει πάλι τον Κόμβο 1 (Ανδρέα).
  • Η Κόμβος 4 (Μαρία) βοηθάει τον Κόμβο 2 (Βασίλη).

👉 Πήγαινε στο Εργαστήριο, πάτα "Στήσιμο" στη δεξιά στήλη και σχεδίασε τις ακμές!

Άσκηση 2: "Το Δίκτυο Υπολογιστών"

Τύπος Γράφου: Μη Κατευθυνόμενος

Θέλουμε να φτιάξουμε ένα δίκτυο με 4 υπολογιστές σε τετράγωνο:

  • Σύνδεσε: 1-2, 2-3, 3-4, 4-1.
  • Είναι ασφαλές δίκτυο γιατί αν κοπεί ένα καλώδιο, υπάρχει άλλη διαδρομή!

👉 Πήγαινε στο Εργαστήριο, πάτα "Στήσιμο" στη δεξιά στήλη και ξεκίνα.

🛠️ Εργαστήριο Γράφων

Οδηγίες Χρήσης:
  1. Κάντε Κλικ στον κενό χώρο για να δημιουργήσετε Κόμβους.
  2. Κάντε κλικ σε έναν κόμβο (θα γίνει πορτοκαλί) και μετά σε έναν άλλον για να φτιάξετε μια Ακμή.
  3. Χρησιμοποιήστε το κουμπί "Αλλαγή Τύπου" για να αλλάξετε τη φορά των βελών.
Επιλέξτε έναν κόμβο...

Άσκηση 1 (Βοήθεια)

Άσκηση 2 (Δίκτυο)

📝 Αυτοαξιολόγηση

1. Ποια είναι η βασική διαφορά μεταξύ Δένδρου και Γράφου;

2. Ποιος τύπος γράφου περιγράφει καλύτερα τη σχέση "Φιλίας" στο Facebook;

3. Γιατί ήταν αδύνατο να λυθεί το πρόβλημα των Γεφυρών του Königsberg;