L08 · Γραφήματα ΙΙΙ — Εφαρμογές, Διμερότητα, Κατευθυνόμενα

Τι θα δούμε

Στο L07 χτίσαμε δύο εργαλεία — BFS και DFS — που διασχίζουν ένα γράφημα σε χρόνο $O(n+m)$. Εκεί ήταν τα εργαλεία. Εδώ είναι η δουλειά: θα δούμε πόσα διαφορετικά προβλήματα λύνονται, σχεδόν χωρίς κόπο, μόλις τα αναγνωρίσεις ως «μια διάσχιση μεταμφιεσμένη».

1. Συνεκτικές συνιστώσες — βρες όλες τις ομάδες κορυφών, χωρίς να ξέρεις από πού να ξεκινήσεις.
2. Flood fill — το «κουβαδάκι» του Paint.
3. Έλεγχος διμερότητας — μπορώ να χωρίσω τις κορυφές σε δύο ομάδες ώστε κάθε ακμή να τις διασχίζει;
4. Κατευθυνόμενα γραφήματα — όταν οι ακμές έχουν φορά.
5. Ισχυρή συνεκτικότητα — φτάνουν όλοι σε όλους, σεβόμενοι τις φορές;
6. Συντομότερη διαδρομή με βάρη — η προετοιμασία για το L09.

Εφαρμογή 1 · Συνεκτικές συνιστώσες

Πρόβλημα. Δεδομένου γραφήματος $G$, βρες όλες τις συνεκτικές συνιστώσες — τις ομάδες κορυφών μέσα στις οποίες όλοι φτάνουν σε όλους, και που δεν μπορείς να τις μεγαλώσεις άλλο: αν προσθέσεις οποιαδήποτε άλλη κορυφή του γραφήματος, χαλάει το «όλοι φτάνουν σε όλους».

Ένα BFS από μια κορυφή $v$ βρίσκει τη συνιστώσα της $v$ — όλα όσα είναι προσπελάσιμα από εκείνη. Για να τις βρούμε όλες, η ιδέα είναι απλή: ξεκίνα ένα νέο BFS από κάθε κορυφή που δεν έχει ακόμα επισκεφθεί.

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

Εφαρμογή 2 · Flood fill

Πρόβλημα. Σε μια εικόνα με πράσινα εικονοστοιχεία (pixels), δίνεται ένα πράσινο pixel — άλλαξε σε μπλε όλη τη συνεκτική περιοχή πράσινων pixels γύρω του.

Φαίνεται διαφορετικό πρόβλημα, αλλά είναι το ίδιο. Αρκεί να το μοντελοποιήσεις σωστά:

• Κορυφές: τα pixels.
• Ακμή $\{p,q\}$: τα $p,q$ είναι γειτονικά (πάνω/κάτω/αριστερά/δεξιά) και τα δύο πράσινα.
• Η περιοχή: η συνεκτική συνιστώσα του δοσμένου pixel.

Η λύση είναι, λοιπόν, ένα BFS (ή DFS) από το δοσμένο pixel — χρωμάτισε μπλε ό,τι επισκέπτεσαι. Χρόνος $O(n+m)$, με $n$ τα pixels και $m$ τα γειτονικά ζεύγη.

Γίνε εσύ το «κουβαδάκι». Κάνε κλικ σε ένα πράσινο pixel και δες το BFS να απλώνεται κύμα-κύμα — να στρίβει γύρω από τα γκρι pixels και να σταματά εκεί ακριβώς που τελειώνει η συνεκτική πράσινη περιοχή:

Εφαρμογή 3 · Έλεγχος διμερότητας

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

Νιώσε: τι σημαίνει «διμερές»

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

Ισοδύναμα: μπορείς να χωρίσεις τις κορυφές σε δύο ομάδες $L$ και $R$, έτσι ώστε κάθε ακμή να πηγαίνει από το $L$ στο $R$ — καμία ακμή να μη μένει μέσα στο $L$ ή μέσα στο $R$.

Το εμπόδιο: περιττοί κύκλοι

Πότε σκάει ο 2-χρωματισμός; Πάντα στο ίδιο σημείο: σε έναν κύκλο περιττού μήκους. Η ιδέα είναι σχεδόν μηχανική: μόλις χρωματίσεις την πρώτη κορυφή κάποιου κύκλου, δεν έχεις πια άλλη επιλογή — κάθε επόμενη πρέπει να πάρει το αντίθετο χρώμα από την προηγούμενη, γιατί τις χωρίζει μια ακμή. Όταν τελικά γυρίσεις πίσω στην αφετηρία, ή το χρώμα ταιριάζει (η κλείνουσα ακμή έχει διαφορετικά χρώματα στα δύο της άκρα — όλα καλά) ή χτυπάει σε αντίφαση. Δοκίμασε κάθε μήκος κύκλου από 3 ως 8 και δες πότε ταιριάζει και πότε σπάει:

Το μοτίβο είναι αναπόφευκτο: για άρτιο $k$ καταλήγεις στην τελευταία κορυφή με χρώμα διαφορετικό από την αφετηρία — η κλείνουσα ακμή είναι «κόκκινο ↔ μπλε», όλα ταιριάζουν. Για περιττό $k$ καταλήγεις στο ίδιο χρώμα με την αφετηρία — η κλείνουσα ακμή ενώνει δύο κορυφές ίδιου χρώματος, και κανένα ξεκίνημα δεν τη γλιτώνει (αν αρχίζαμε με μπλε, θα συναντιόμασταν σε μπλε). Άρα:

Το εντυπωσιακό είναι ότι ισχύει και το αντίστροφο — και η απόδειξή του δίνει κατευθείαν τον αλγόριθμο.

Το θεώρημα: τα επίπεδα του BFS αποφασίζουν

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

Η απόδειξη

Περίπτωση 1 — καμία ακμή μέσα σε επίπεδο. Θυμήσου την ιδιότητα του BFS: κάθε ακμή ενώνει κορυφές που διαφέρουν το πολύ κατά ένα επίπεδο. Αν αποκλείσουμε και τις ακμές μέσα στο ίδιο επίπεδο, τότε κάθε ακμή πάει από επίπεδο $i$ σε επίπεδο $i+1$. Χρωματίζοντας τα άρτια επίπεδα κόκκινα και τα περιττά μπλε, κάθε ακμή ενώνει ένα άρτιο με ένα περιττό — δηλαδή κόκκινο με μπλε. Έγκυρος 2-χρωματισμός ⇒ διμερές. ✓

Περίπτωση 2 — υπάρχει ακμή $(x,y)$ με τα $x,y$ στο ίδιο επίπεδο $L_j$. Θα κατασκευάσουμε έναν περιττό κύκλο. Έστω $z$ ο χαμηλότερος κοινός πρόγονος των $x$ και $y$ στο BFS-δέντρο, και έστω ότι βρίσκεται στο επίπεδο $L_i$ (με $i<j$).

Δούλεψε την κατασκευή βήμα-βήμα: βρες το $z$, χάραξε τα δύο μονοπάτια του δέντρου, κλείσε τον κύκλο με την ακμή $(x,y)$ — και δες το μήκος να βγαίνει περιττό.

Σχηματίζουμε έναν κύκλο από τρία κομμάτια: το μονοπάτι $z\to x$ στο δέντρο (μήκος $j-i$), το μονοπάτι $z\to y$ (πάλι $j-i$), και την ακμή $(x,y)$ (μήκος $1$). Συνολικό μήκος:

$(j-i)+(j-i)+1=1+2(j-i)$

Αυτό είναι περιττός αριθμός — άρα έχουμε περιττό κύκλο, και από το λήμμα το $G$ δεν είναι διμερές. $■$

Ο αλγόριθμος

Η απόδειξη είναι ο αλγόριθμος — δεν χρειάζεται τίποτα παραπάνω από ένα BFS και μια σάρωση των ακμών.

Κατευθυνόμενα γραφήματα

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

• Ιστοσελίδες: η Wikipedia δείχνει στο Google, το Google μπορεί να μη δείχνει πίσω.
• Χρονοπρογραμματισμός εργασιών: «η εργασία α πρέπει να τελειώσει πριν την β». Το αντίθετο δεν θα είχε καν νόημα.
• Ροή κλήσεων προγράμματος: η main καλεί την parse, η parse δεν καλεί τη main.
• Τροφική αλυσίδα: το λιοντάρι τρώει το ελάφι, όχι ανάποδα.

Αυτό το αποτυπώνει το κατευθυνόμενο γράφημα:

$G=(V,A)$

όπου το σύνολο $A$ περιέχει διατεταγμένα ζευγάρια $(u,v)$ — η ακμή πάει από την $u$ προς την $v$, σχεδιάζεται με βελάκι, και είναι διαφορετική οντότητα από την $(v,u)$.

Δύο βαθμοί αντί για έναν

Όταν οι ακμές αποκτούν φορά, ο «βαθμός» μιας κορυφής σπάει στα δύο:

• Εσώβαθμος $\text{indeg}(v)$ — πόσα βελάκια καρφώνονται μέσα στην $v$.
• Εξώβαθμος $\text{outdeg}(v)$ — πόσα βελάκια ξεκινούν από την $v$.

Παρατήρησε ότι κάθε ακμή προσμετράται ακριβώς μία φορά ως εξερχόμενη (στο outdeg της αφετηρίας της) και ακριβώς μία φορά ως εισερχόμενη (στο indeg του προορισμού της). Άρα αν αθροίσεις και τους δύο μετρητές πάνω σε όλες τις κορυφές, παίρνεις από δύο διαφορετικούς δρόμους την ίδια απάντηση — πόσες ακμές υπάρχουν συνολικά:

${\sum }_{v\in V}\text{indeg}(v)={\sum }_{v\in V}\text{outdeg}(v)=|A|.$

Είναι ακριβώς το λήμμα της χειραψίας του L06, σπασμένο στα δύο. Δες τους τρεις μετρητές να τικάρουν μαζί, ακμή προς ακμή — και μετά γύρνα στο tab «Κορυφή προς κορυφή» για να δεις indeg/outdeg ξεχωριστά:

Η διάσχιση ακολουθεί ΜΟΝΟ τις εξερχόμενες ακμές

Το BFS (και το DFS) δουλεύουν με μία και μόνο αλλαγή: από κορυφή $u$ ακολουθούμε μόνο τις ακμές που βγαίνουν από την $u$. Δεν έχουμε δικαίωμα να διαβάσουμε μια ακμή ανάποδα — αν στο γράφημα υπάρχει $a\to b$, μου επιτρέπεται να πάω από a σε b, όχι από b σε a. Ο χρόνος μένει $O(n+m)$.

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

Η διαφορά ανάμεσα στην αφετηρία v1 (φτάνεις σε όλους) και την v5 (φτάνεις μόνο στον εαυτό σου) είναι το πιο καθαρό αποτύπωμα της κατευθυντικότητας: ίδιο γράφημα, ίδιοι κανόνες, ριζικά διαφορετική προσβάσιμη περιοχή. Έτσι λύνεται και η κατευθυνόμενη προσπελασιμότητα: δοσμένης κορυφής $s$, ποιες κορυφές φτάνονται από την $s$ σεβόμενοι τις φορές; — απλά ένα BFS από την $s$ που ακολουθεί μόνο εξερχόμενες ακμές.

Ισχυρή συνεκτικότητα

Στα μη κατευθυνόμενα γραφήματα, «συνεκτικό» σήμαινε «όλοι φτάνουν σε όλους» — και αν φτάσω από a στο b, ξέρω αυτόματα ότι φτάνω και από b στο a, διαβάζοντας την ίδια διαδρομή αντίστροφα. Στα κατευθυνόμενα, μόλις είδαμε, αυτή η αυτονόητη συμμετρία χάνεται: το πρώτο μπορεί να ισχύει χωρίς το δεύτερο. Άρα η έννοια της συνεκτικότητας θέλει ξανά ορισμό από την αρχή — με αυστηρότερη διατύπωση.

Δύο κορυφές $u,v$ λέγονται αμοιβαία προσπελάσιμες όταν υπάρχει διαδρομή $u\to v$ και διαδρομή $v\to u$. Είναι δηλαδή δύο ξεχωριστές απαιτήσεις — η μία δεν τραβάει την άλλη. Ένα κατευθυνόμενο γράφημα είναι ισχυρά συνεκτικό όταν κάθε ζεύγος κορυφών είναι αμοιβαία προσπελάσιμο — όχι ένα ή δέκα, ΟΛΑ.

Δοκίμασε τον ορισμό με το χέρι. Πάρε δύο γραφήματα ίδιου σχήματος (ένας πεντάγωνος κύκλος και ο ίδιος χωρίς μία ακμή) και έλεγξε ζεύγη ένα-ένα. Πάτα μετά «Δοκίμασε όλα τα ζεύγη» για να δεις πόσα σπάει η μία και μοναδική ακμή που λείπει:

Στο «καλό» γράφημα και τα δέκα ζεύγη είναι αμοιβαία προσπελάσιμα — εξ ορισμού ισχυρά συνεκτικό. Στο «σπασμένο» γράφημα, η μία ακμή που λείπει (5 → 1) τινάζει στον αέρα όλα τα ζεύγη όπου η 1 έπρεπε να φτάνεται «από κάτω»: από τις 5, 4, 3, 2 δεν φτάνεις πια στην 1, οπότε τέσσερα ζεύγη γίνονται μονόδρομα. Η μία απουσία τσακίζει τον ορισμό για το σύνολο του γραφήματος.

Ο έξυπνος έλεγχος σε γραμμικό χρόνο

Ο αφελής τρόπος — «έλεγξε κάθε ζεύγος» — είναι ακριβός. Το κλειδί είναι μια παρατήρηση που ανάγει τα $n^2$ ζεύγη σε μία κορυφή:

Πώς ελέγχουμε τη συνθήκη 2 — «η $s$ φτάνεται από όλους»; Με ένα κόλπο: αντίστρεψε τη φορά κάθε ακμής. Σκέψου το σαν να γυρνάς όλα τα βέλη ανάποδα — κάθε «δρόμος προς εμένα» γίνεται «δρόμος από εμένα». Στο αντεστραμμένο γράφημα $G^{\text{rev}}$, λοιπόν, «η $s$ φτάνει την $v$» σημαίνει «στο αρχικό $G$ η $v$ φτάνει την $s$». Άρα ένα και μόνο BFS από την $s$ στο $G^{\text{rev}}$ ελέγχει ολόκληρη τη συνθήκη 2.

Δες τα δύο BFS να τρέχουν. Διάλεξε εσύ την αφετηρία $s$ κάνοντας κλικ σε μια κορυφή — και πρόσεξε ότι, όποια κι αν διαλέξεις, η τελική ετυμηγορία δεν αλλάζει· αυτό ακριβώς εγγυάται το λήμμα.

Εισαγωγή στη συντομότερη διαδρομή με βάρη

Ως τώρα κάθε ακμή «κόστιζε» 1, και το BFS έβρισκε τη συντομότερη διαδρομή σε $O(n+m)$. Αλλά στην πράξη οι ακμές δεν είναι ισότιμες: ένας δρόμος είναι μακρύτερος από έναν άλλο, μια σύνδεση δικτύου πιο αργή.

Δίνουμε λοιπόν σε κάθε ακμή $e$ ένα βάρος ${\ell }_e>0$, και ορίζουμε το μήκος μιας διαδρομής ως το άθροισμα των βαρών των ακμών της. Το πρόβλημα συντομότερης διαδρομής ζητάει, για δοσμένα $s$ και $t$, τη διαδρομή με το ελάχιστο συνολικό βάρος.

Πριν φτάσουμε στους αλγορίθμους, η εξέταση αγαπά μια προαπαιτούμενη ερώτηση: αν αλλάξουμε τα βάρη, διατηρείται το συντομότερο μονοπάτι;

Γιατί το BFS δεν αρκεί πια

Το BFS βρίσκει τη διαδρομή με τον μικρότερο αριθμό ακμών. Με βάρη όμως, αυτό δεν είναι το ίδιο με τη φθηνότερη διαδρομή.

Δες το λάθος να συμβαίνει. Γύρνα τον διακόπτη ανάμεσα στο «πώς μετράει το BFS» (μετράει ακμές) και στο πραγματικό κόστος (άθροισμα βαρών):

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

Και μια εντελώς διαφορετική στρατηγική για τα πολυφασικά προβλήματα — αλλάζεις τη δομή του ίδιου του γράφου αντί για τα βάρη:

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

Βάλε στη σειρά τα βήματα του ελέγχου ισχυρής συνεκτικότητας:

Και συμπλήρωσε τα κενά για τη διμερότητα:

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