5.5 Δέντρα και δάση

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

Ορισμός 5.13   (Δέντρα, δάση) Ενα συνεκτικό γράφημα που δεν περιέχει κύκλους ονομάζεται δέντρο. Ενα γράφημα, συνεκτικό ή μη, που δεν περιέχει κύκλους ονομάζεται δάσος.

Σχήμα 5.20: Ένα δάσος από 4 δέντρα

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

Τα δέντρα έχουν ενδιαφέρον επειδή, κατά κάποια έννοια, είναι τα «ελάχιστα» συνεκτικά γραφήματα: κάθε συνεκτικό γράφημα $G=(V,E)$ περιέχει ένα υπογράφημα με τις ίδιες κορυφές, συνεκτικό και χωρίς κύκλους (άρα δέντρο). (Δείτε το Θεώρημα 5.1.)

Παράδειγμα 5.13   Ας πούμε ότι έχουμε ένα γράφημα (Σχήμα 5.21) με τα δρομολόγια που εκτελεί μια αεροπορική εταιρεία ανάμεσα σε $N$ πόλεις. Κάποιες πόλεις συνδέονται μεταξύ τους απ' ευθείας, κάποιες με μία ενδιάμεση στάση, κ.λ.π.

Σχήμα 5.21: Τα δρομολόγια μιας αεροπορικής εταιρείας, πριν και μετά τις περικοπές

Σε κάποια άσχημη οικονομική συγκυρία η εταιρεία αποφασίζει πως δεν είναι πλέον σε θέση να εκτελεί τόσο πολλά δρομολόγια και ότι πρέπει να καταργήσει όσο πιο πολλά μπορεί. Η εταιρεία δε θα εισαγάγει νέα δρομολόγια, απλώς θα καταργήσει μερικά. Για λόγους πολιτικής όμως η εταιρεία δε μπορεί να σταματήσει να εξυπηρετεί καμία από τις $N$ πόλεις που μέχρι τότε εξυπηρετούσε. Επίσης, προσεγγιστικά, όλες οι πτήσεις κοστίζουν το ίδιο στην εταιρεία, ανεξάρτητα από την απόσταση.

Δείχνουμε στο Σχήμα 5.21 τη λύση που επέλεξε τελικά η εταιρεία. Παρατηρήστε ότι:

• Για τις 7 πόλεις χρησιμοποιούνται πλέον 6 πτήσεις (ακμές στο γράφημα).
• Για κάθε ζεύγος πόλεων εξακολουθεί να είναι δυνατό να πάει κανείς από τη μια στην άλλη, με κατάλληλες ενδιάμεσες στάσεις, και
• Για κάθε ζεύγος πόλεων υπάρχει μόνο ένας τρόπος να ταξιδέψει κανείς από τη μια στην άλλη (χωρίς, εννοείται, να πετάει μπρος πίσω).

Ορισμός 5.14   (Δέντρα και δάση που παράγουν) Ενα δέντρο $T$, υπογράφημα του $G$ και με τις ίδιες κορυφές, λέγεται δέντρο που παράγει το $G$ (spanning tree). Αν το $T$ δεν είναι δέντρο αλλά είναι δάσος, και κάθε συνεκτική συνιστώσα του $G$ παράγεται από κάποιο δέντρο του $T$, τότε το $T$ λέγεται δάσος που παράγει το $G$.

Θεώρημα 5.1   Κάθε συνεκτικό γράφημα $G$ περιέχει ένα δέντρο που το παράγει.

Απόδειξη. Εστω ότι το συνεκτικό γράφημα $G=(V,E)$ περιέχει κάποιο κύκλο

$$C: u_1 \stackrel{e_1}{\longrightarrow} u_2 \stackrel{e_2}{\longrightarrow} \cdots \stackrel{e_{n-1}}{\longrightarrow} u_n = u_1.$$

Ας επιλέξουμε τυχαία μια από τις ακμές του κύκλου, π.χ. την $e_1$, και ας τη σβήσουμε από το γράφημα. Ισχυριζόμαστε ότι το γράφημα παραμένει συνεκτικό. (Δείτε και την Άσκηση 5.24.) Πραγματικά, ας υποθέσουμε πως η ακμή $e_1$ που σβήσαμε συμμετείχε στο γράφημα $G$ σε κάποιο μονοπάτι $L$ που συνέδεε δύο κορυφές $v$ και $u$, όπως φαίνεται στο Σχ. 5.22.

Σχήμα 5.22: Διαγραφή της $e_1$ διατηρεί τη συνεκτικότητα

Είναι φανερό ότι, παρά το ότι τώρα πια η ακμή $e_1$ έχει διαγραφεί, μπορούμε και πάλι να πάμε από το $v$ στο $u$ διανύοντας το μονοπάτι όπως και πριν αλλά όταν θα χρειαστεί να περάσουμε την $e_1$ μπορούμε να την αντικαταστήσουμε διανύοντας το υπόλοιπο του κύκλου $C$.

Την πράξη αυτή, που μόλις δείξαμε ότι διατηρεί τη συνεκτικότητα, την ονομάζουμε «σπάσιμου του κύκλου $C$ στην ακμή $e_1$». Επαναλαμβάνοντας αυτή την πράξη όσο εξακολουθούν να υπάρχουν κύκλοι στο γράφημα, και αφού μετά από κάθε τέτοια πράξη οι ακμές λιγοστεύουν κατά μία, είναι φανερό (εφόσον μιλάμε για πεπερασμένα γραφήματα) ότι θα φτάσουμε σε ένα ύπογράφημα του $G$ με τις ίδιες κορυφές (αυτές δεν αλλάζουν με την πράξη της διαγραφής της ακμής), συνεκτικό και χωρίς πλέον κύκλους, δηλ. σε ένα δέντρο.

Αν το γράφημα $G$ δεν είναι συνεκτικό εφαρμόζουμε το πρώτο κομμάτι (που μόλις αποδείξαμε) του Θεωρήματος 5.1 σε κάθε συνεκτική του συνιστώσα και παίρνουμε έτσι από ένα δένδρο για κάθε συνιστώσα, που την παράγει. $\qedsymbol$

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

Θεώρημα 5.2   Κάθε δέντρο με $n$ κορυφές έχει ακριβώς $n-1$ ακμές.

Απόδειξη. Με επαγωγή ως πρός $n$. Για $n=1$ είναι προφανές. Εστω $G$ δέντρο με $n$ κορυφές.

Ισχυρισμός: Υπάρχει κορυφή του $G$ με βαθμό $1$.

Εστω ότι όλες οι κορυφές έχουν βαθμό $\ge 2$ (αφού καμία δεν έχει βαθμό 0 λόγω συνεκτικότητας). Μπορούμε τότε να βρούμε μονοπάτια οσουδήποτε μεγάλου μήκους στο $G$ στα οποία ποτέ δεν εμφανίζεται κάτι της μορφής

$$\cdots u \stackrel{e}{\longrightarrow} v \stackrel{e}{\longrightarrow} u \cdots$$

αφού πάντα μπορούμε να φύγουμε από κάποια κορυφή χρησιμοποιώντας κάποια άλλη ακμή από αυτή που χρησιμοποιήσαμε για να μπούμε, και μπορούμε να κινούμαστε έτσι επ' άπειρον. Αν το μονοπάτι έχει αρκετά μεγάλο μήκος θα υπάρχει σίγουρα κάποια κορυφή που εμφανίζεται εκεί πάνω από μία φορά. Επιλέγουμε μια τέτοια κορυφή $u$ που έχει επιπλέον την ιδιότητα ότι η απόσταση ανάμεσα στις δύο εμφανίσεις της είναι ελάχιστη.

Σχήμα 5.23: Ενα μονοπάτι με μια επαναλαμβανόμενη κορυφή $u$

Η κατάσταση απεικονίζεται στο Σχήμα 5.23. Η επιπλέον ιδιότητα αυτή της $u$ συνεπάγεται ότι στο κύκλωμα που απεικονίζεται στο σχήμα πάνω από το $u$ δεν υπάρχει άλλη επαναλαμβανόμενη κορυφή ή ακμή, άρα αυτό το κύκλωμα είναι κύκλος, πράγμα που απαγορεύεται σε δέντρο, και έχουμε αποδείξει τον ισχυρισμό. (Δείτε και την Άσκηση 5.23.)

Εστω λοιπόν $\deg u = 1$ και ορίζουμε το υπογράφημα $G'$ του $G$ που επάγεται από τις υπόλοιπες κορυφές $V\setminus{\left\{{u}\right\}}$, σβήνουμε δηλ. την $u$ και τη μοναδική ακμή που καταλήγει στην $u$. (Δείτε Σχήμα 5.24.)

Σχήμα 5.24: Σβήνουμε την κορυφή $u$ και τη μοναδική ακμή που καταλήγει σε αυτή για να πάρουμε το υπογράφημα $G'$ από το $G$.

Ως υπογράφημα, το $G'$ προφανώς δεν έχει κύκλους και εξακολουθεί να είναι συνεκτικό αφού είναι φανερό ότι, επειδή η $u$ έχει βαθμό $1$, δεν μπορεί να χρησιμοποιθεί για τη σύνδεση δύο άλλων κορυφών. Αλλά το $G'$ έχει $n-1$ κορυφές και από την επαγωγική μας υπόθεση έχει συνεπώς $n-2$ ακμές. Αρα το $G$ έχει $n-1$ (αυτές του $G'$ συν αυτή που καταλήγει στην $u$). $\qedsymbol$

Άσκηση 5.34   Αποδείξτε ότι ένα δάσος με $n$ κορυφές και $m$ συνεκτικές συνιστώσες ($m$ δέντρα δηλαδή) έχει ακριβώς $n-m$ ακμές.

Υπόδειξη: Εφαρμόστε το Θεώρημα 5.2 σε κάθε δέντρο του δάσους (δηλ. σε κάθε συνεκτική συνιστώσα του γραφήματος).

Άσκηση 5.35   Δείξτε ότι κάθε ζεύγος κορυφών ενός δέντρου ενώνονται μεταξύ τους με ένα μοναδικό μονοπάτι το οποίο δεν περνά δύο φορές από την ίδια ακμή. Δείξτε επίσης ότι αν ισχύει αυτό για ένα γράφημα $G$ τότε αυτό είναι αναγκαστικά δέντρο.

Υπόδειξη: Σε κάθε συνεκτικό γράφημα και για κάθε δύο κορυφές του υπάρχει μονοπάτι μεταξύ τους χωρίς επαναλαμβανόμενες ακμές (π.χ. κάθε μονοπάτι που τις ενώνει και είναι ελάχιστου μήκους). Θα πρέπει να δείξετε ότι αν το γράφημα είναι δέντρο τότε αυτό το μονοπάτι είναι μοναδικό. Επίσης, για το αντίστροφο, ότι αν σε κάποιο συνεκτικό γράφημα ισχύει η μοναδικότητα για κάθε ζεύγος κορυφών του τότε αυτό είναι δέντρο.

Για να δείξετε τη μοναδικότητα (στην περίπτωση που το γράφημα είναι δέντρο) υποθέστε, αντίθετα με αυτό που θέλετε να αποδείξετε, ότι οι κορυφές $u, v$ του δέντρου $G$ συνδέονται με δύο διαφορετικά μονοπάτια $\pi_1, \pi_2$ μεταξύ τους. Κάθε ένα από τα $\pi_1, \pi_2$ δεν περιέχει επαναλαμβανόμενες ακμές.

Η εύκολη περίπτωση είναι όταν καμιά ακμή του $\pi_1$ δεν υπάρχει στο $\pi_2$. Σε αυτή την περίπτωση το κύκλωμα που δημιουργείται αρχίζοντας από την κορυφή $u$, ακολουθώντας το $\pi_1$ ως την κορυφή $v$, και απιστρέφοντας στην κορυφή $u$ ακολουθώντας το $p_2$ ανάποδα, δεν είναι απλά ένα κύκλωμα αλλά κύκλος, δεν περιέχει δηλ. επαναλαμβανόμενες ακμές. Αυτό αντιφάσκει με το ότι το γράφημα μας είναι δέντρο (=συνεκτικό και χωρίς κύκλους).

Γενικά μπορεί όμως μια ακμή του $\pi_1$ να υπάρχει και στο $\pi_2$ οπότε ο κύκλος που θα πρέπει να βρούμε για να έχουμε αντίφαση δε μπορεί να είναι η προηγούμενος και χρειάζεται κάπως προσεκτική δουλειά.

Άσκηση 5.36   Δείξτε ότι αν προσθέσουμε μια ακμή σε ένα δέντρο τότε δημιουργούμε ακριβώς ένα κύκλο.

Υπόδειξη: Αν το δέντρο μας έχει $n$ κορυφές τότε έχει ακριβώς $n-1$ ακμές. Μετά την πρόσθεση μιας ακμής θα έχει $n$ ακμές και παραμένει φυσικά συνεκτικό, άρα δεν παραμένει δέντρο και το νέο μας γράφημα θα περιέχει κάποιο κύκλο. Θα πρέπει να δείξετε ότι περιέχει μόνο ένα κύκλο.

Εύκολα έχουμε τώρα:

Πόρισμα 5.1   Αν ένα συνεκτικό γράφημα $G$ με $n$ κορυφές έχει $n-1$ ακμές τότε είναι δέντρο.

Απόδειξη. Το $G$ περιέχει κάποιο δέντρο που παράγει, έστω $T$, το οποίο έχει $n-1$ ακμές σύμφωνα με το Θεώρημα 5.2. Αρα $G = T$. $\qedsymbol$

Άσκηση 5.37   Ένα συνεκτικό γράφημα με τουλάχιστον 3 κορυφές λέγεται διπλά συνεκτικό αν παραμένει συνεκτικό ακόμη κι αν σβήσουμε μια οποιαδήποτε ακμή του. Πόσες, το λιγότερο, ακμές πρέπει να έχει ένα τέτοιο γράφημα με $n$ κορυφές; Βρείτε ένα γράφημα που να «πιάνει» τον ελάχιστο αυτό αριθμό ακμών.

Υπόδειξη: Πόρισμα 5.1.

Άσκηση 5.38   Έστω συνεκτικό γράφημα $G$ με τουλάχιστον 3 κορυφές. Μια ακμή του, την οποία αν αφαιρέσουμε αποσυνδέουμε το γράφημα, λέγεται γέφυρα. Δηλ. ένα συνεκτικό γράφημα είναι διπλά συνεκτικό (δείτε Άσκηση 5.37) αν και μόνο αν δεν έχει γέφυρες.

(α) Δείξτε ότι μια ακμή είναι γέφυρα αν και μόνο αν δεν περιέχεται σε κανένα κύκλο.

(β) Δείξτε ότι κάθε ακμή του $G$ είναι γέφυρα αν και μόνο αν το $G$ είναι δέντρο.