5.4 Συνεκτικότητα και αποστάσεις πάνω σε γραφήματα

Ορισμός 5.7   (Μονοπάτι και μήκος του) Μονοπάτι στο $G$ θα λέγεται μια ακολουθία κορυφών

$$u_1 \stackrel{e_1}{\longrightarrow} u_2 \stackrel{e_2}{\longrightarrow} \cdots \stackrel{e_{n-1}}{\longrightarrow} u_n,$$

όπου η ακμή $e_j$ συνδέει τις κορυφές $u_j$ και $u_{j+1}$, $j=1,\ldots,n-1$. Το πλήθος των ακμών ($n-1$) που εμφανίζονται σε ένα μονοπάτι θα λέγεται μήκος του μονοπατιού.

Ένα μονοπάτι μπορεί να χρησιμοποιεί μια ακμή του γραφήματος παραπάνω από μια φορά.

Παράδειγμα 5.7   Ενα μονοπάτι σε ένα απλό γράφημα μπορούμε να το περιγράψουμε αναφέροντας μόνο τις κορυφές $u_j$ αφού οι ακμές εννοούνται. Π.χ. στο γράφημα του σχήματος 5.2 το $1\rightarrow 2 \rightarrow 3 \rightarrow 6$ είναι ένα μονοπάτι. Στο γράφημα του Σχήματος 5.1 το Ηράκλειο - Ανώγεια - Ρέθυμνο είναι ένα μονοπάτι μήκους δύο.

Άσκηση 5.22   Στο γράφημα $B$ της Άσκησης 5.18 βρείτε ένα μονοπάτι που να συνδέει τις κορυφές $(0,0,0)$ και $(1,1,1)$.

Ορισμός 5.8   (Κύκλωμα, κύκλος) Κύκλωμα λέγεται ένα μονοπάτι όπου η τελευταία κορυφή είναι ίδια με την πρώτη.

Οταν θέλουμε να μιλήσουμε για κυκλώματα χωρίς επαναλαμβανόμενες ακμές θα τα αποκαλούμε κύκλους.

Παράδειγμα 5.8   Στο Σχήμα 5.2 το $1\rightarrow2\rightarrow3\rightarrow6 \rightarrow4\rightarrow1$ είναι ένα κύκλωμα που είναι ταυτόχρονα και κύκλος αφού καμιά από τις ακμές που συμμετέχουν σε αυτό δεν επαναλαμβάνεται. Στο Σχήμα 5.1 το Ηράκλειο $\rightarrow$ Ανώγεια $\rightarrow$ Ηράκλειο $\rightarrow$ Ρέθυμνο $\rightarrow$ Ανώγεια $\rightarrow$ Ηράκλειο είναι επίσης ένα κύκλωμα μήκους 5, αλλά όχι κύκλος αφού η ακμή Ηράκλειο - Ανώγεια χρησιμοποιείται 3 φορές.

Ορισμός 5.9   (Προσιτή κορυφή) Θα λέμε ότι η κορυφή $v$ είναι προσιτή από την κορυφή $u$ αν υπάρχει μονοπάτι που να ξεκινάει από την $u$ και να καταλήγει στην $v$.

Παράδειγμα 5.9   Στα γραφήματα των Σχημάτων 5.1 και 5.2 όλες οι κορυφές είναι προσιτές από όλες.

Είναι εύκολο να δειχτεί ότι η σχέση «$v$ προσιτό από $u$» είναι μία σχέση ισοδυναμίας πάνω στο σύνολο $V$ των κορυφών. Άρα το σύνολο $V$ διαμερίζεται σε κλάσεις ισοδυναμίας που τις ονομάζουμε συνεκτικές συνιστώσες. Με άλλα λόγια δύο κορυφές ενός γραφήματος είναι στην ίδια συνεκτική συνιστώσα αν και μόνο αν υπάρχει μονοπάτι που τις ενώνει.

Σχήμα 5.16: Ενα γράφημα με $3$ συνεκτικές συνιστώσες

Παράδειγμα 5.10   Στο σχήμα 5.16 δείχνουμε ένα γράφημα του οποίου οι συνεκτικές συνιστώσες είναι οι ${\left\{{1}\right\}}$, ${\left\{{2,3,4}\right\}}$ και ${\left\{{5,6,7}\right\}}$.

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

Παράδειγμα 5.11   Τα γραφήματα των Σχημάτων 5.1 και 5.2 είναι συνεκτικά ενώ αυτό του Σχήματος 5.16 δεν είναι.

Άσκηση 5.23   Δείξτε ότι ένα συνεκτικό γράφημα με $n$ κορυφές και λιγότερες από $n$ ακμές έχει αναγκαστικά μια κορυφή βαθμού 1.

Υπόδειξη: Υποθέστε ότι δεν ισχύει το συμπέρασμα και καταλήξετε σε άτοπο χρησιμοποιώντας την Άσκηση 5.4.

Άσκηση 5.24   Δείξτε ότι αν έχουμε ένα συνεκτικό γράφημα που περιέχει ένα κύκλο, και διαγράψουμε μια ακμή αυτού του κύκλου, το γράφημα παραμένει συνεκτικό. Κάτι τέτοιο δε συμβαίνει, εν γένει, αν το γράφημα δεν έχει κύκλο (δώστε παράδειγμα).

Σχήμα 5.17: Συνεκτικό γράφημα με ένα κύκλο του οποίου διαγράφουμε μια ακμή παραμένει συνεκτικό (για Άσκηση 5.24)

Θα ορίσουμε τώρα μια συνάρτηση $d:V\times V \to {\mathbb{R}}$ που θα έχει την έννοια της απόστασης. Η ποσότητα δηλ. $d(u,v)$ θα «μετράει» το πόσο κοντά είναι οι δύο κορυφές $u$ και $v$ του γραφήματος.

Ορισμός 5.11   (Απόσταση κορυφών) Αν η κορυφή $u$ δεν είναι προσιτή από την κορυφή $v$ τότε ορίζουμε

$$d(u, v) = d(v, u) = +\infty,$$

η απόσταση δηλ. ανάμεσα σε δύο κορυφές $u$ και $v$ που δε συνδέονται με κανένα μονοπάτι θεωρείται άπειρη.

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

Παράδειγμα 5.12   Στο Σχήμα 5.16 $d(2,4)=d(5,7)=2$, $d(3,2)=1$, και $d(1,x)=+\infty$, για κάθε $x \in {\left\{{2,\ldots,7}\right\}}$. Επίσης στο Σχήμα 5.10, αριστερά, $d(u,v)=1$, για κάθε $u,v \in {\left\{{1,\ldots,5}\right\}}$.$u\neq v$.

Οπως κάθε φυσιολογική έννοια απόστασης στα Μαθηματικά, η συνάρτηση απόστασης που μόλις ορίσαμε ικανοποιεί τη λεγόμενη τριγωνική ανισότητα:

$$\forall u,v,w \in V: d(u,v) \le d(u,w) + d(w,v).$$ (5.2)

Για να δεί κανείς γιατί ισχύει αυτό, παρατηρήστε ότι αν πάρουμε οποιoδήποτε μονοπάτι από το $u$ στο $w$ και το συνεχίσουμε με ένα οποιoδήποτε μονοπάτι από το $w$ στο $v$, τότε παίρνουμε ένα μονοπάτι από το $u$ στο $v$. Οι λεπτομέρειες της απόδειξης αφήνονται στον αναγνώστη.

Άσκηση 5.25   Αποδείξτε την (5.2) με όλες τις λεπτομέρειες.

Εχοντας ορίσει μια έννοια απόστασης, μπορούμε τώρα να μιλήσουμε για τη διάμετρο ενός γραφήματος $G=(V,E)$, που τη συμβολίζουμε με ${\rm diam }G$.

Ορισμός 5.12   (Διάμετρος) Η διάμετρος ενός γραφήματος $G$ ορίζεται να είναι η μέγιστη απόσταση ανάμεσα σε δυό κορυφές του $G$:

$${\rm diam }G = \max_{u, v \in V} d(u, v).$$ (5.3)

Είναι φανερό ότι ένα γράφημα $G$ είναι συνεκτικό αν και μόνο αν ${\rm diam }G < \infty$. Για παράδειγμα, το αριστερό γράφημα του Σχήματος 4 έχει διάμετρο $1$ ενώ το δεξιό έχει διάμετρο $2$.

Άσκηση 5.26   Ποια η διάμετρος του γραφήματος $B$ της Άσκησης 5.18;

Άσκηση 5.27   Δείξτε ότι η διάμετρος ενός συνεκτικού γραφήματος με $n$ κορυφές είναι το πολύ $n-1$.

Περιγράψτε, με πλήρη απόδειξη, όλα τα γραφήματα με $n$ κορυφές και διάμετρο $n-1$.

Επίσης όλα τα γραφήματα με διάμετρο $n-2$ και όλα τα γραφήματα με διάμετρο 1.

Υπόδειξη: Για το πρώτο παρατηρήστε ότι αν $u, v$ είναι δυο κορυφές του $G$ με απόσταση $d = d(u, v)$ τότε υπάρχει ένα μονοπάτι που τις ενώνει χωρίς επαναλαμβανόμενες ακμές. Κάθε μονοπάτι που τις ενώνει και έχει μήκος $d$ είναι τέτοιο (αλλιώς η απόστασή τους θα ήταν μικρότερη).

Άσκηση 5.28   Όλοι οι κάτοικοι μιας χώρας, της οποίας το αλφάβητο έχει 10 γράμματα, έχουν ως όνομα μια λέξη μήκους ακριβώς 6. Το πλήθος των κατοίκων είναι $10^6$ και όλοι έχουν διαφορετικά ονόματα. Αν $G$ είναι το γράφημα με κορυφές τους κατοίκους, και δύο κάτοικοι συνδέονται με ακμή αν και μόνο αν τα ονόματά τους διαφέρουν σε ακριβώς μια θέση, ποια είναι η διάμετρος του $G$;

Υπόδειξη: Δύο κάτοικοι συνδέονται μεταξύ τους με ακμή αν και μόνο αν μπορούμε να αλλάξουμε το όνομα του ενός σε ακριβώς μια θέση και να πάρουμε το όνομα του άλλου. Σκεφτόμενοι έτσι βλέπουμε ότι το να διασχίσουμε μια ακμή στο γράφημα ισοδυναμεί με το να αλλάξουμε το όνομα της τρέχουσας κορυφής σε μια ακριβώς θέση. Άρα το ερώτημα «ποια είναι η διάμετρος του $G$» ισοδυναμεί με το ερώτημα «πόσες το πολύ αλλαγές πρέπει να κάνουμε στο όνομα ενός κατοίκου για να πάρουμε το όνομα ενός άλλου κατοίκου;»

Άσκηση 5.29   Ένα γράφημα έχει ως κορυφές τα 64 τετραγωνάκια μιας συνηθισμένης σκακιέρας, και δύο τετραγωνάκια συνδέονται μεταξύ τους με ακμή αν και μόνο αν έχουν μια πλευρά κοινή. Ποια η διάμετρος του γραφήματος;

Σχήμα 5.18: Το γράφημα της Άσκησης 5.29.

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

Υπόδειξη: Ας είναι $a, b$ δύο κορυφές του γραφήματος $G$ με $d(a, b) = {\rm diam }G$. Δείξτε ότι κάθε μια από τις $a, b$ μπορεί να παίξει το ρόλο της προς διαγραφή κορυφής της Άσκησης.

Άσκηση 5.31   Αν σε ένα γράφημα υπάρχουν ακριβώς δύο κορυφές με περιττό βαθμό, αυτές πρέπει αναγκαστικά να συνδέονται με κάποιο μονοπάτι.

Υπόδειξη: Δείτε την Άσκηση 5.6.

Άσκηση 5.32   Ο απλούστερος ίσως τρόπος, αν και όχι πάντα ο πιο αποτελεσματικός από άποψη υπολογιστική, για να παραστήσει κανείς ένα απλό γράφημα είναι με το λεγόμενο πίνακα συνδεσμολογίας. Εστω $G=(V,E)$ ένα απλό γράφημα με $V={\left\{{v_1,\ldots,v_n}\right\}}$. Ο πίνακας συνδεσμολογίας $A$ είναι τότε ένας $n\times n$ πίνακας με

$$A_{ij}=\left\{ \begin{array}{cl} 1 & \alpha\nu v_i \sim ... ... \alpha\lambda\lambda\iota\omega\varsigma . \end{array}\right.$$

Βάζουμε δηλ. 1 στη θέση $i,j$ αν και μόνο αν η $i$-οστή και η $j$-οστή κορυφή συνδέονται με κάποια ακμή. Από τον ορισμό προκύπτει αμέσως ότι ο πίνακας $A$ είναι συμμετρικός και έχει 0 παντού πάνω στη διαγώνιο. (Θυμίζουμε ότι μιλάμε εδώ για απλά γραφήματα, γραφήματα δηλ. στα οποία οι ακμές δεν έχουν κατεύθυνση και καμιά κορυφή δε συνδέεται με τον εαυτό της. Όταν αυτές οι ιδιότητες δεν ισχύουν τότε μπορεί και ο πίνακας συνδεσμολογίας είτε να μην είναι συμμετρικός είτε να μην έχει μόνο μηδενικά στη διαγώνιο.)

Με επαγωγή ως πρός $k$ δείξετε ότι Ο πίνακας $A^k$.$k \ge 0$, (γινόμενο του πίνακα $A$ με τον εαυτό του $k$ φορές) έχει στη θέση $i,j$ τον αριθμό $s$ αν και μόνο αν ο αριθμός των μονοπατιών μήκους $k$ από την κορυφή $i$ στην $j$ είναι ακριβώς $s$. (Παρατήρηση: Ενα μονοπάτι μήκους $k$ από το $u$ στο $v$ μπορεί να επαναλαμβάνει ακμές. Για παράδειγμα, αν $u \sim u_1 \sim v$, τότε το μονοπάτι $u \to u_1 \to u \to u_1 \to v$ είναι ένα μονοπάτι από το $u$ στο $v$ μήκους $4$.)

Υπόδειξη: Αν $X, Y$ είναι $n\times n$ πίνακες και $Z = XY$ είναι το γινόμενό τους (επίσης $n\times n$ πίνακας) τότε εξ ορισμού

$$Z_{i,j} = \sum_{r=1}^n X_{i,r}Y_{r,j}, \gamma\iota\alpha i, j = 1, 2, \ldots, n.$$

Ισχύει λοιπόν

$$A^k_{i,j} = \sum_{r=1}^n A^{k-1}_{i,r} A_{r,j}, \gamma\iota\alpha i, j = 1, 2, \ldots, n.$$ (5.4)

Με βάση την επαγωγική υπόθεση η ποσότητα $A^{k-1}_{i,r}$ μας δίνει το πλήθος των μονοπατιών από την κορυφή $i$ στην κορυφή $r$ με μήκος ακριβώς $k-1$. Χρησιμοποιώντας αυτό ερμηνεύστε το άθροισμα της (5.4) ως το πλήθος των μονοπατιών από την κορυφή $i$ στην κορυφή $j$ με μήκος ακριβώς $k$.

Άσκηση 5.33   Αν $G$ είναι ένα συνεκτικό γράφημα με $n$ κορυφές, μέγιστο βαθμό $d$ τότε

$$n \le 1+d\frac{(d-1)^{{\rm diam }G} -1}{d-2}.$$

Υπόδειξη: Έστω $u$ μια κορυφή του $G$. Τα σύνολα κορυφών

$$V(k) = {\left\{{v\in V: d(u,v)=k}\right\}}, k=0,1,\ldots,{\rm diam }G,$$

διαμερίζουν το σύνολο κορυφών $V$. Δείξτε με επαγωγή ως προς $k$ ότι

$${\left\vert{V(k)}\right\vert} \le d(d-1)^{k-1} \gamma\iota\alpha k\ge 1.$$

Αθροίστε έπειτα αυτές τις ανισότητες για $k=0, 1, \ldots, {\rm diam }G$ και χρησιμοποιήστε τον τύπο για την πεπερασμένη γεωμετρική σειρά (1.15).

Σχήμα 5.19: Τα σύνολα $V(0), V(1), V(2), V(3)$ της υπόδειξης της Άσκησης 5.33 σε ένα παράδειγμα. Το σύνολο $V(1)$ είναι οι κορυφές που απέχουν απόσταση 1 από το $u$ (πράσινος «δακτύλιος»), το σύνολο $V(2)$ είναι οι κορυφές που απέχουν απόσταση 2 από το $u$ (κόκκινος «δακτύλιος»), και το σύνολο $V(3)$ είναι οι κορυφές που απέχουν απόσταση 3 από το $u$ (μώβ περιοχή).