5.2 Πα, 27/9/02: Μικρή επανάληψη. Δέντρα.

Σήμερα κάναμε μια μικρή επανάληψη των εννοιών που είχαν καλυφθεί στο προηγούμενο μάθημα.

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

Ορισμός 1   Ένα γράφημα $T$ λέγεται δέντρο με ρίζα αν υπάρχει μια κορυφή $r$ του $T$ την οποία αποκαλούμε ρίζα, και το $T$ έχει τις ακόλουθες ιδιότητες:

1. Οι κορυφές χωρίζονται σε επίπεδα, το επίπεδο 0, το επίπεδο 1, κ.ο.κ, μέχρι το επίπεδο $d$ που ονομάζεται το βάθος του δέντρου.
2. Στο επίπεδο 0 βρίσκεται μόνο η ρίζα.
3. Στο επίπεδο $k>0$ βρίσκονται ακριβώς τα παιδιά των κορυφών του επιπέδου $k-1$, όλες δηλ. εκείνες οι κορυφές $v$ για τις οποίες υπάρχει μια κορυφή $u$ στο επίπεδο $k-1$ τ.ώ. υπάρχει η ακμή $u \to v$.
4. Κάθε κορυφή $v$ εκτός τη ρίζα έχει ακριβώς ένα γονέα, δηλ. μια κορυφή $u$ τ.ώ. $u \to v$. Η ρίζα δεν έχει κανένα.

Οι κορυφές που είναι προσπελάσιμες με μονοπάτι από μια κορυφή $u$ ονομάζονται συνολικά απόγονοι της $u$.

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

Ένα δέντρο απεικονίζεται στο παρακάτω σχήμα.

Σχήμα 2. Ένα δέντρο με 5 επίπεδα

Στη Θεωρία Γραφημάτων συναντάται συνήθως ο ορισμός του δέντρου κάπως διαφορετικά: ένα μη κατευθυνόμενο γράφημα $G$ λέγεται δέντρο αν δεν έχει κύκλους, δεν έχει μονοπάτια δηλ. που ξεκινούν και τελειώνουν στην ίδια κορυφή χωρίς να περνάνε πάνω από μια φορά από κάποια ακμή. Αποδεικνύεται εύκολα ότι ο ορισμός αυτός συμπίπτει με αυτόν που δώσαμε παραπάνω, αν κάποιος προσδιορίσει στο μη κατευθυνόμενο γράφημα το ποια κορυφή θεωρείται ρίζα, και κατόπιν κατευθύνει όλες τις ακμές του γραφήματος ώστε να ``απομακρύνονται'' από τη ρίζα.

Δείξαμε επίσης σήμερα το εξής:

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

Δίνουμε δύο αποδείξεις παρακάτω, μια επαγωγική και μια όχι. Η επαγωγική απόδειξη είναι τυπική της χρήσης της επαγωγής για αποδείξεις στη Θεωρία Γραφημάτων.

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

Αποδεικνύουμε τώρα το επαγωγικό βήμα. Υποθέτουμε δηλ. ότι αν ένα δέντρο έχει το πολύ $n$ κορυφές τότε ισχύεει το θεώρημα και χρησιμοποιούμε αυτή την υπόθεση για να δείξουμε την πρόταση για το τυχόν δέντρο με $n+1$ κορυφές. Έστω $T$ ένα τέτοιο δέντρο, και έστω $v_1, \ldots, v_k$, $k\ge 1$, οι απόγονοι της ρίζας. Με άλλα λόγια αυτές είναι οι κορυφές στο επίπεδο 1.

Για κάθε $i=1,\ldots,k$ τώρα παρατηρούμε τώρα ότι το γράφημα που προκύπτει από το $T$ αν κρατήσουμε μόνο τις κορυφές $v_i$ και τους απογόνους της είναι ένα δέντρο με ρίζα την κορυφή $v_i$. Αυτό το δέντρο, έστω $T_i$, ονομάζεται το υποδέντρο του $T$ με ρίζα το $v_i$, και είναι φανερό ότι τα $k$ αυτά υποδέντρα είναι μεταξύ τους ξένα, δε μοιράζονται δηλ. κορυφές ή ακμές.

Αν με $V(G)$ συμβολίζουμε το σύνολο των κορυφών του γραφήματος $G$ και με $E(G)$ το σύνολο των ακμών του $G$, αυτό που θέλουμε να δείξουμε είναι

$${\left\vert{E(T)}\right\vert} = {\left\vert{V(T)}\right\vert} -1,$$ (1)

όπου με ${\left\vert{A}\right\vert}$ συμβολίζουμε τον πληθάριθμο του συνόλου $A$. Η δε επαγωγική υπόθεση μας λέει ότι

$${\left\vert{E(T_i)}\right\vert} = {\left\vert{V(T_i)}\right\vert} -1, i=1,\ldots,k,$$ (2)

μια και τα $T_i$ έχουν το πολύ $n$ κορυφές.

Ισχύουν όμως προφανώς (αφού τα $T_i$ είναι ξένα μεταξύ τους)

$${\left\vert{V(T)}\right\vert} = {\left\vert{V(T_1)}\right\vert}+\cdots+{\left\vert{V(T_k)}\right\vert}+1,$$

$${\left\vert{E(T)}\right\vert} = (1+{\left\vert{E(T_1)}\right\vert})+\cdots+(1+{\left\vert{E(T_k)}\right\vert}).$$

Αντικαθιστώντας στην (1) και χρησιμοποιώντας τις σχέσεις (2) προκύπτει ισότητα.
$\Box$

Απόδειξη 2η: Το σύνολο των ακμών μπορεί να έρθει σε αμφιμονοσήμαντη αντιστοιχία με το σύνολο των κορυφών πλην της ρίζας, αντιστοιχίζοντας σε κάθε ακμή $u \to v$ την κορυφή $v$. Η απεικόνιση αυτή είναι 1-1 και επί αφού ακριβώς μια ακμή καταλήγει σε κάθε κορυφή πλην της ρίζας. Άρα τα δύο αυτά σύνολα είναι ισοπληθικά, δηλ. το πλήθος των ακμών είναι ίσο με αυτό των κορυφών πλην ένα.
$\Box$

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

Άσκηση 5.2.2   Σε ένα δέντρο υπάρχει το πολύ ένα μονοπάτι που ενώνει δύο δεδομένες κορυφές.

Άσκηση 5.2.3   Άν ένα δέντρο έχει το πολύ $n$ επίπεδα και από κάθε κορυφή ξεκινούν το πολύ 5 ακμές, πόσες το πολύ κορυφές έχει το δέντρο;