L06 · Γραφήματα Ι — Βασικές Έννοιες

Τι θα δούμε

Με αυτή τη διάλεξη ξεκινά το μεγαλύτερο κομμάτι του μαθήματος. Σύμφωνα με τα παλιά θέματα, οι αλγόριθμοι σε γραφήματα είναι περίπου το 30–35% του βαθμού στις εξετάσεις — το μεγαλύτερο μονοκόμματο μπλοκ. Τα τέσσερα επόμενα κεφάλαια (L07–L09) χτίζονται πάνω σε αυτό εδώ.

Το L06 είναι το προετοιμαστικό κεφάλαιο — και θα είναι ειλικρινές μαζί σου: δεν θα δεις αλγόριθμο εδώ. Θα δεις τρία πράγματα, και θα τα δεις καλά:

1. Τι είναι ένα γράφημα — η ορολογία που θα χρησιμοποιείς σε κάθε επόμενη διάλεξη.
2. Πώς το αποθηκεύεις στον υπολογιστή — και γιατί αυτή η επιλογή καθορίζει τις πολυπλοκότητες όλων των αλγορίθμων που θα μάθεις.
3. Τι θα το ρωτήσεις — τα προβλήματα που θα λύσουν τα L07–L09.

Τι είναι ένα γράφημα

Ένα μη κατευθυνόμενο γράφημα (ή απλό γράφημα) γράφεται

$G=(V,E)$

και αποτελείται από δύο σύνολα:

• $V$ — το σύνολο των κορυφών (vertices, nodes, κόμβοι): τα «αντικείμενα».
• $E$ — το σύνολο των ακμών (edges): οι συνδέσεις. Κάθε ακμή είναι ένα μη διατεταγμένο ζευγάρι κορυφών $\{u,v\}$ — «μη διατεταγμένο» σημαίνει ότι $\{u,v\}$ και $\{v,u\}$ είναι η ίδια ακμή.

Δύο μεγέθη μετράμε διαρκώς:

• $n(G)=|V|$ — το πλήθος των κορυφών.
• $m(G)=|E|$ — το πλήθος των ακμών.

Και μία έννοια ανά κορυφή: ο βαθμός (degree) μιας κορυφής $v$ είναι το πλήθος των ακμών που την ακουμπούν — διαισθητικά, «πόσους γείτονες έχει».

Ένα παράδειγμα

Σε αυτό το γράφημα:

• $V=\{1,2,3,4,5,6,7,8\}$, άρα $n(G)=8$.
• $E=\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{2,5\},\{3,5\},\{3,7\},\{3,8\},\{4,5\},\{5,6\},\{7,8\}\}$, άρα $m(G)=11$.
• Οι βαθμοί: $\mathrm{deg}(1)=2$, $\mathrm{deg}(2)=4$, $\mathrm{deg}(3)=5$, $\mathrm{deg}(6)=1$ (η κορυφή 6 ακουμπάει μόνο μία ακμή).

Πόσοι βαθμοί συνολικά;

Φαντάσου ότι σε μια συνάντηση κάθε άνθρωπος μετράει πόσα χέρια έσφιξε. Αν αθροίσεις αυτούς τους αριθμούς, παίρνεις διπλάσιο του συνολικού πλήθους χειραψιών — γιατί κάθε χειραψία προσμετρήθηκε δύο φορές, μία από κάθε άνθρωπο που συμμετείχε. Σε ένα γράφημα ισχύει ακριβώς το ίδιο, με τις ακμές στη θέση των χειραψιών:

Δοκίμασέ το ζωντανά — πρόσθεσε ακμές μία-μία και παρακολούθησε τους μετρητές: σε κάθε νέα ακμή, δύο βαθμοί τικάρουν +1 και ο μετρητής 2m τικάρει +2. Δεν θα μπορούσαν ποτέ να βγουν διαφορετικοί:

Πού κρύβονται γραφήματα

Η δύναμη της έννοιας φαίνεται στο πόσο διαφορετικά πράγματα μοντελοποιεί:

Η μοντελοποίηση είναι επιλογή

Διάβασε αυτόν τον πίνακα προσεκτικά. Σε κάθε γραμμή, κάποιος αποφάσισε τι θα είναι κορυφή και τι ακμή. Αλλά η ίδια κατάσταση μπορεί να γίνει διαφορετικό γράφημα ανάλογα με την ερώτηση που θέλεις να απαντήσεις. Δύο διαφορετικές απαντήσεις θα ζητούσαν δύο διαφορετικά γραφήματα — από τα ίδια ακριβώς δεδομένα.

Ένα παράδειγμα από το μετρό:

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

Άλλαξε τις «όψεις» παρακάτω και πάρε το ίδιο ζευγάρι αφετηρίας-προορισμού — οι δύο αριθμοί ΔΕΝ ταυτίζονται:

Πώς αποθηκεύουμε ένα γράφημα

Πριν τρέξουμε οποιονδήποτε αλγόριθμο, πρέπει να βάλουμε το γράφημα στη μνήμη. Υπάρχουν δύο βασικοί τρόποι — και η επιλογή δεν είναι λεπτομέρεια: καθορίζει την πολυπλοκότητα κάθε αλγορίθμου που θα γράψεις από εδώ και πέρα.

Πίνακας γειτνίασης (adjacency matrix)

Ένας τετραγωνικός πίνακας $A$ διαστάσεων $n\times n$, όπου το κελί $A_{ij}$ λέει αν υπάρχει ακμή ανάμεσα στις κορυφές $i$ και $j$:

$A_{ij}=\{\begin{array}{ll}1& \text{αν }\{i,j\}\in E\\ 0& \text{διαφορετικαˊ}\end{array}$

Σε μη κατευθυνόμενο γράφημα η ακμή $\{i,j\}$ είναι ίδια με την $\{j,i\}$, οπότε ο πίνακας είναι συμμετρικός: $A_{ij}=A_{ji}$.

Λίστα γειτνίασης (adjacency list)

Αντί για έναν μεγάλο πίνακα, κρατάμε $n$ μικρές λίστες — μία ανά κορυφή — όπου η λίστα της $v$ περιέχει ακριβώς τους γείτονες της $v$.

Δες τες δίπλα-δίπλα

Το σχήμα, ο πίνακας και η λίστα είναι η ίδια πληροφορία ντυμένη αλλιώς. Διάλεξε μια κορυφή στο εργαλείο και πρόσεξε πώς ανάβει ταυτόχρονα και στις τρεις όψεις — και τι κοστίζει να βρεις τους γείτονές της σε καθεμία:

Ποια να διαλέξω;

Οι δύο αναπαραστάσεις δεν είναι ισοδύναμες — η καθεμία είναι καλή σε άλλο πράγμα:

Διαδρομές και συνεκτικότητα

Με το γράφημα αποθηκευμένο, χρειαζόμαστε λεξιλόγιο για να μιλήσουμε για κίνηση μέσα του.

Διαδρομή

Φαντάσου ότι περπατάς πάνω στο γράφημα: κάθε σου βήμα είναι μια ακμή. Μια διαδρομή (path) είναι ακριβώς αυτή η περιπατητική: μια ακολουθία κορυφών

$P=v_1,v_2,\dots ,v_{k-1},v_k$

όπου κάθε διαδοχικό ζευγάρι $\{v_i,v_{i+1}\}$ είναι ακμή του γραφήματος — δηλαδή κάθε βήμα είναι «νόμιμο», ακολουθεί υπαρκτή σύνδεση. Το μήκος της διαδρομής είναι το πλήθος των βημάτων, $k-1$.

Μια απλή διαδρομή είναι μια διαδρομή όπου όλες οι κορυφές είναι διαφορετικές — δεν περνάς δύο φορές από τον ίδιο κόμβο.

Γιατί μας νοιάζει να είναι απλή; Σκέψου το αλλιώς: αν μια διαδρομή ξαναπεράσει από κάποιον κόμβο, τότε ανάμεσα στις δύο επισκέψεις έχει κάνει έναν «κύκλο» — μια κυκλική περιπλάνηση που τη φέρνει πίσω στο ίδιο σημείο. Αν σου ενδιαφέρει το μήκος (π.χ. ψάχνεις τη συντομότερη διαδρομή), αυτός ο κύκλος είναι περιττός: κόψε τον, και βγαίνεις με τα ίδια άκρα αλλά μικρότερο μήκος. Γι' αυτό μια συντομότερη διαδρομή είναι πάντα απλή.

Δοκίμασέ το: φτιάξε μια διαδρομή κάνοντας κλικ σε κορυφές με τη σειρά. Αν επαναλάβεις σκόπιμα μια κορυφή, το «ψαλίδι» θα κόψει τον κύκλο μπροστά σου, και το μήκος θα πέσει:

Συνεκτικότητα

Ένα μη κατευθυνόμενο γράφημα είναι συνεκτικό (connected) αν για κάθε ζευγάρι κορυφών $u,v$ υπάρχει διαδρομή που τις ενώνει. Διαισθητικά: κανείς δεν είναι «νησί» — από όπου κι αν ξεκινήσεις, μπορείς να φτάσεις παντού.

Αν το γράφημα δεν είναι συνεκτικό, σπάει φυσικά σε κομμάτια: τις συνεκτικές συνιστώσες (connected components). Κάθε συνιστώσα είναι ένα μέγιστο υποσύνολο κορυφών μέσα στο οποίο όλοι φτάνουν σε όλους — αλλά κανείς δεν φτάνει σε κάποιον έξω από τη συνιστώσα.

Ο πιο φυσικός τρόπος να δεις τι είναι μια συνιστώσα είναι να ξεκινήσεις από μια κορυφή και να αφήσεις ένα «κύμα» να εξαπλωθεί. Όπου σταματάει το κύμα — εκεί είναι το όριο της συνιστώσας:

Κύκλος

Ένας κύκλος (cycle) είναι, με λίγα λόγια, μια απλή διαδρομή που κλείνει — ξεκινάς από κάπου, περνάς από διαφορετικές κορυφές, και επιστρέφεις στην αφετηρία ακολουθώντας μια ακόμα ακμή. Τυπικά, μια ακολουθία $v_1,v_2,\dots ,v_k$ που:

1. είναι διαδρομή, και επιπλέον $\{v_1,v_k\}\in E$ — η αρχή ενώνεται με το τέλος με γνήσια ακμή του γραφήματος·
2. έχει $k\ge 3$ — αυτό αποκλείει τους τετριμμένους «κύκλους» μήκους 2 (πήγαινε-έλα στην ίδια ακμή, που δεν θα μέτραγε ως πραγματικός κύκλος)·
3. έχει όλες τις κορυφές διαφορετικές — όπως και στην απλή διαδρομή.

Δοκίμασε να χτίσεις έναν εσύ. Στο εργαλείο παρακάτω, κλικ σε κορυφές για να βαδίσεις· επιστροφή στην αρχή «κλείνει» τη διαδρομή. Οι τέσσερις όροι (κάθε βήμα είναι ακμή, $k\ge 3$, διακριτές, υπάρχει η κλείστρα) ελέγχονται ζωντανά — δες ποιον σπας με τα τρία προεπιλεγμένα παραδείγματα:

Δένδρα

Ανάμεσα σε όλα τα γραφήματα, μία οικογένεια είναι τόσο σημαντική που έχει δικό της όνομα. Ένα γράφημα είναι δένδρο (tree) αν είναι ταυτόχρονα:

1. συνεκτικό — όλοι φτάνουν σε όλους, και
2. ακυκλικό — δεν περιέχει κανέναν κύκλο.

Διαισθητικά, ένα δένδρο είναι το πιο οικονομικό γράφημα που μπορείς να φτιάξεις διατηρώντας τα πάντα συνδεδεμένα: αρκετές ακμές για να φτάνει κανείς οπουδήποτε, αλλά ούτε μία παραπάνω που να φτιάχνει κυκλώματα. Όπως ο σκελετός που κρατάει ένα δίκτυο όρθιο χωρίς πλεονασμό.

Αυτή η οικονομικότητα μεταφράζεται σε έναν ακριβή αριθμό — και σε ένα από τα πιο όμορφα θεωρήματα του κεφαλαίου:

«Οποιεσδήποτε δύο» ακούγεται σαν ταχυδακτυλουργία — μέχρι να το δοκιμάσεις. Στο εργαλείο παρακάτω ξεκινάς από ένα δένδρο 6 κορυφών (και οι τρεις δείκτες πράσινοι). Κάνε ένα πειραματικό κλικ:

• Πρόσθεσε μία ακμή → εμφανίζεται κύκλος, οπότε «ακυκλικό» πέφτει στο κόκκινο. Και το πλήθος ακμών γίνεται $n$ → «$n-1$» πέφτει επίσης. Δεν γίνεται να σπάσει μόνο μία από τις τρεις.
• Αφαίρεσε μία ακμή του δένδρου → το γράφημα σπάει σε δύο κομμάτια, «συνεκτικό» πέφτει. Και το πλήθος γίνεται $n-2$, «$n-1$» πέφτει κι αυτό.

Το πρότυπο «προσπάθησε να σπάσεις μόνο μία ⇒ σπάει και άλλη» είναι η απόδειξη του θεωρήματος, μεταμφιεσμένη σε παιχνίδι:

Μια συνέπεια που θα χρησιμοποιήσουμε ξανά και ξανά: σε ένα δένδρο υπάρχει μοναδικό μονοπάτι ανάμεσα σε κάθε ζευγάρι κορυφών. Αν υπήρχαν δύο διαφορετικά μονοπάτια ανάμεσα σε δύο κορυφές, ενώνοντάς τα θα σχηματιζόταν κύκλος — αντίφαση με το ότι το δένδρο είναι ακυκλικό.

Δένδρα με ρίζα

Μέχρι τώρα μιλήσαμε για δένδρα ως απλά γραφήματα — όλες οι κορυφές «ισότιμες». Συχνά όμως διαλέγουμε μία κορυφή ως ξεχωριστή και «κρεμάμε» από αυτήν όλο το δένδρο. Αυτή η κορυφή λέγεται ρίζα (root), και η επιλογή της δημιουργεί ιεραρχία: κοντά στη ρίζα = «ψηλά», μακριά της = «χαμηλά».

Με τη ρίζα διαλεγμένη, κάθε κορυφή $v$ αποκτά τρεις νέους ρόλους:

• Γονέας (parent) — ο μοναδικός γείτονας της $v$ που είναι πιο κοντά στη ρίζα. (Η ρίζα δεν έχει γονέα.)
• Παιδιά (children) — οι γείτονες που είναι πιο μακριά από τη ρίζα.
• Αν δεν έχει παιδιά, η $v$ είναι φύλλο (leaf).

Το κλειδί που πολλοί μαθητές χάνουν: το δένδρο μένει το ίδιο, η ρίζα είναι επιλογή σου. Διαφορετική ρίζα → διαφορετικός γονέας, διαφορετικά παιδιά, διαφορετικά φύλλα — από τις ίδιες ακριβώς ακμές. Άλλαξε ρίζα με κλικ και δες το να ξανακρεμιέται:

Δένδρα με ρίζα είναι παντού στην πληροφορική: φυλογενετικά δένδρα στη βιολογία, η δομή των αρχείων ενός δίσκου, το DOM μιας ιστοσελίδας, το αφηρημένο συντακτικό δένδρο (AST) ενός προγράμματος — ακόμα και τα δένδρα αναδρομής που σχεδιάσαμε στο L03.

Τι θα ρωτήσουμε — τα προβλήματα των L07–L09

Τώρα που έχουμε τη γλώσσα, ας διατυπώσουμε τα προβλήματα. Αυτά είναι που θα μας απασχολήσουν στις επόμενες διαλέξεις:

Πρόβλημα 1 — s-t συνεκτικότητα. Δεδομένων δύο κορυφών $s$ και $t$, υπάρχει διαδρομή από την $s$ στην $t$;

Πρόβλημα 2 — s-t απόσταση. Δεδομένων δύο κορυφών $s$ και $t$, ποιο είναι το μήκος της συντομότερης διαδρομής από την $s$ στην $t$;

Μοιάζουν απλά, αλλά κρύβονται παντού:

• Κοινωνικά δίκτυα — πόσο «μακριά» είναι δύο άνθρωποι;
• Λαβύρινθος — υπάρχει διαδρομή από την είσοδο στην έξοδο;
• Six Degrees of Kevin Bacon — πόσες ταινίες απέχει ένας ηθοποιός από τον Kevin Bacon;
• Routing στο διαδίκτυο — το πρωτόκολλο OSPF βρίσκει συντομότερες διαδρομές σε δίκτυα.

Κλείδωσε τη γνώση

Συμπλήρωσε τα κενά στις θεμελιώδεις έννοιες — χωρίς να κοιτάς πίσω:

Μοτίβο σκέψης