Μαθηματικό μοντέλο. Μετρικά χαρακτηριστικά ενός μη κατευθυνόμενου γραφήματος

Δήλωση. Εάν για δύο κορυφές υπάρχει μια διαδρομή που τις συνδέει, τότε είναι βέβαιο ότι υπάρχει μια ελάχιστη διαδρομή που συνδέει αυτές τις κορυφές. Ας υποδηλώσουμε το μήκος αυτής της διαδρομής μερε(v,w).

Ορισμός. Μέγεθοςρε(v,w) (πεπερασμένο ή άπειρο) θα κληθεί απόσταση μεταξύ κορυφών v, w . Αυτή η απόσταση ικανοποιεί τα μετρικά αξιώματα:

1) ρε(v,w) 0, καιρε(v,w) = 0 αν και μόνο ανv=w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

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

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

Παράδειγμα 82.

Για το γράφημα G που φαίνεται στο Σχ. 3.16, βρείτε την ακτίνα, τη διάμετρο και τα κέντρα.

Ρύζι. 3.16. Γράφημα για παράδειγμα 82

Λύση.

Να προσδιορίσετε τα κέντρα, την ακτίνα, τη διάμετρο του γραφήματος σολ, ας βρούμε τη μήτρα ΡΕ(ΣΟΛ)αποστάσεις μεταξύ κορυφών γραφήματος, στοιχείων d ijπου θα είναι οι αποστάσεις μεταξύ των κορυφών v iΚαι v j. Για αυτό θα χρησιμοποιήσουμε ΓΡΑΦΙΚΗ ΑΝΑΠΑΡΑΣΤΑΣΗγραφική παράσταση. Σημειώστε ότι ο πίνακας ΡΕ(ΣΟΛ)συμμετρικά ως προς την κύρια διαγώνιο.

Χρησιμοποιώντας τον πίνακα που προκύπτει για κάθε κορυφή του γραφήματος σολΑς προσδιορίσουμε τη μεγαλύτερη αφαίρεση από την έκφραση: Για Εγώ,j = 1, 2, …, 5. Ως αποτέλεσμα παίρνουμε: r(v 1) = 3,r(v 2) = 2,r(v 3) = 2,r(v 4) = 2,r(v 5) = 3.Το ελάχιστο των αριθμών που προκύπτουν είναι η ακτίνα του γραφήματος σολ, μέγιστη – διάμετρος γραφήματος σολ. Που σημαίνει, R(Ζ) = 2Και ΡΕ(Ζ) = 3, τα κέντρα είναι οι κορυφές v2,v 3,v 4.

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

Εκκεντρικότητακορυφές γραφήματος – η απόσταση από τη μέγιστη κορυφή από αυτήν. Για ένα γράφημα για το οποίο δεν έχει οριστεί βάρος στα άκρα του, η απόσταση ορίζεται ως ο αριθμός των ακμών.

Ακτίνα κύκλουγράφημα είναι η ελάχιστη εκκεντρότητα των κορυφών, και διάμετρος γράφημα – μέγιστη εκκεντρότητα κορυφών.

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

Περιφερειακόςοι κορυφές έχουν εκκεντρότητα ίση με τη διάμετρο.

Μια απλή αλυσίδα με μήκος ίσο με τη διάμετρο του γραφήματος ονομάζεται διαμετρικά .

Θεώρημα 12.1.Σε ένα συνδεδεμένο γράφημα, η διάμετρος δεν είναι μεγαλύτερη από την κατάταξη του πίνακα γειτνίασης.

Θεώρημα 12.2.(Ιορδανία) Κάθε δέντρο έχει ένα κέντρο που αποτελείται από μία ή δύο γειτονικές κορυφές.

Θεώρημα 12.3.Εάν η διάμετρος του δέντρου είναι άρτια, τότε το δέντρο έχει ένα μόνο κέντρο και όλες οι διαμετρικές αλυσίδες περνούν μέσα από αυτό, εάν η διάμετρος είναι περιττή, τότε υπάρχουν δύο κέντρα και όλες οι διαμετρικές αλυσίδες περιέχουν μια άκρη που τα συνδέει.

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

Παράδειγμα 12.5.Βρείτε την ακτίνα, τη διάμετρο και το κέντρο του γραφήματος που φαίνεται στο Σχ. 12.1.

Λύση.Σε αυτή την εργασία είναι βολικό στη χρήση πίνακας απόστασης S. Ένα στοιχείο αυτού του τετραγωνικού συμμετρικού πίνακα είναι ίσο με την απόσταση μεταξύ των κορυφών Εγώκαι την κορυφή ι. Για το γράφημα που φαίνεται στο Σχ. 12.1, ο πίνακας απόστασης έχει επόμενη προβολή:

. (12.2)

Ας υπολογίσουμε την εκκεντρότητα κάθε κορυφής. Αυτή η τιμή μπορεί να οριστεί ως το μέγιστο στοιχείο της αντίστοιχης στήλης του πίνακα απόστασης (ή γραμμής - αφού ο πίνακας μικρόσυμμετρικός). Παίρνουμε

№

Ακτίνα γραφήματος r– ελάχιστη εκκεντρότητα των κορυφών. ΣΕ σε αυτήν την περίπτωση r= 2. Οι κορυφές Νο. 2, Νο. 4 και Νο. 5 έχουν τέτοια εκκεντρότητα. Αυτές οι κορυφές σχηματίζουν το κέντρο του γραφήματος. Μέτρηση διάμετρος ρε– μέγιστη εκκεντρότητα των κορυφών. Σε αυτήν την περίπτωση ρε= 3. Οι κορυφές Νο. 1 και Νο. 3 έχουν τέτοια εκκεντρότητα αυτή είναι η περιφέρεια του γραφήματος. Στο μελετημένο γράφημα, οι κορυφές αποδείχθηκαν είτε κεντρικές είτε περιφερειακές. Σε γραφήματα υψηλότερης τάξης, υπάρχουν και άλλες κορυφές.

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

Θεώρημα 12.4. Αφήνω να είναι ο πίνακας γειτνίασης ενός γραφήματος G χωρίς βρόχους και , όπου . Τότε ίσος με τον αριθμό των διαδρομών μήκους k από κορυφή σε κορυφή.

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

Παράδειγμα 12.6.Βρείτε τον πίνακα απόστασης του γραφήματος που φαίνεται στο Σχ. 12.1, χρησιμοποιώντας την αλγεβρική μέθοδο.

Λύση.Ο πίνακας γειτνίασης αυτού του γραφήματος είναι ίσος με:

.

Θα συμπληρώσουμε τον πίνακα απόστασης λαμβάνοντας υπόψη τις μοίρες του πίνακα γειτνίασης. Οι μονάδες του πίνακα γειτνίασης εμφανίζουν ζεύγη κορυφών που έχουν απόσταση μίας μεταξύ τους (δηλαδή συνδέονται με ένα μόνο άκρο).

.

Τα διαγώνια στοιχεία του πίνακα αποστάσεων είναι μηδενικά. Πολλαπλασιάστε τον πίνακα γειτνίασης από τον εαυτό του:

.

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

.

Η απόσταση μεταξύ των κορυφών 1 και 3 παραμένει άγνωστη. Θα πολλαπλασιάσουμε τον πίνακα γειτνίασης στον εαυτό του μέχρι στο matrix μη μηδενικό στοιχείο δεν θα εμφανιστεί . Στη συνέχεια το αντίστοιχο στοιχείο του πίνακα απόστασης ίσο με τη δύναμηπίνακες γειτνίασης: . Στο επόμενο βήμα φτάνουμε

Στην τελευταία ενότητα, τονίσαμε ότι ο πίνακας γειτνίασης $A$ που εισάγεται εκεί, ή πιο συγκεκριμένα ο πίνακας γειτνίασης κορυφής του γραφήματος, παίζει πολύ σημαντικό ρόλο Σημαντικός ρόλοςστη θεωρία γραφημάτων. Σημειώσαμε τα πλεονεκτήματα αυτού του πίνακα - είναι τετράγωνο της τάξης ίσο με τον αριθμόσειρές του πίνακα πρόσπτωσης $B$, δηλαδή, κατά κανόνα, περιέχει μικρότερο αριθμόστοιχεία. Δεύτερον, αυτός ο πίνακας αποθηκεύει όλες τις πληροφορίες σχετικά με τις άκρες του γραφήματος και, με μια δεδομένη αρίθμηση κορυφών, περιγράφει μοναδικά το γράφημα. Ο πίνακας γειτνίασης, όπως ο πίνακας πρόσπτωσης ενός γραφήματος, είναι ένας πίνακας (0,1), δηλ. Τα στοιχεία του μπορούν να θεωρηθούν ως στοιχεία άλλων αλγεβρικών δομών και όχι μόνο ως στοιχεία του συνόλου των ακεραίων. Συγκεκριμένα, σημειώσαμε ότι τα στοιχεία του πίνακα γειτνίασης μπορούν να θεωρηθούν ως στοιχεία της άλγεβρας Boole, που υπόκεινται στους νόμους της Boolean αριθμητικής, αλλά δεν το εξηγήσαμε σωστά. Πριν καλύψουμε αυτό το κενό, ας τονίσουμε τα πλεονεκτήματα του πίνακα γειτνίασης που προκύπτει από το τετράγωνό του.

Για να το κάνετε αυτό, θυμηθείτε τους κανόνες για τον πολλαπλασιασμό πίνακα. Έστω να δοθούν αυθαίρετοι πίνακες με αριθμητικά στοιχεία: πίνακας $A$ της διάστασης $n\φορές m$ με στοιχεία $a_(ik)$ και πίνακας $B$ της διάστασης $m\times q$ με στοιχεία $b_(kj)$ . Ένας πίνακας $C$ της διάστασης $n\φορές q$ ονομάζεται γινόμενο του πίνακα $A$ επί $B$ (η σειρά είναι σημαντική) εάν τα στοιχεία του $c_(ij)$ ορίζονται ως εξής: $c_(ij) ) = \sum\limits_( k = 1)^m (a_(ik) b_(kj))$. Το γινόμενο των πινάκων γράφεται με τον συνήθη τρόπο $AB=C$. Όπως μπορούμε να δούμε, το γινόμενο των πινάκων απαιτεί συνέπεια στα μεγέθη του πρώτου και του δεύτερου παράγοντα (ο αριθμός των στηλών του πρώτου πίνακα παραγόντων είναι ίσος με τον αριθμό των σειρών του δεύτερου πίνακα παραγόντων). Αυτή η απαίτηση εξαφανίζεται εάν λάβουμε υπόψη τετράγωνους πίνακες της ίδιας τάξης και, επομένως, μπορούμε να εξετάσουμε αυθαίρετες δυνάμεις ενός τετραγωνικού πίνακα. Αυτό είναι ένα από τα πλεονεκτήματα τετράγωνες μήτρεςπριν από τα ορθογώνια. Ένα άλλο πλεονέκτημα είναι ότι μπορούμε να δώσουμε μια ερμηνεία γραφήματος στα στοιχεία βαθμού του πίνακα γειτνίασης.

Έστω ότι ο πίνακας γειτνίασης $A$ έχει τη μορφή: $A = \left(((\begin(array)(*c) (a_(11) ) & (a_(12) ) & (...) & (a_ (1n ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (... ) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \end(πίνακας)) \δεξιά)$, και $ k$th βαθμός της — $A^k = \left(((\begin(array)(*c) (a_(11)^((k))) & (a_(12)^(k)) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & (. .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^( ( k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \end(πίνακας) )) \δεξιά)$ , όπου $k = 2,3,...$ Προφανώς, το $A^k$, όπως και ο πίνακας $A$, θα είναι συμμετρικός πίνακας.

Έστω $k=2$. Τότε $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), και κάθε όρος $a_(il) a_(lj)$ είναι ίσος με $0$ ή $1$. Η περίπτωση που $a_(il) a_(lj) = 1$ σημαίνει ότι υπάρχουν δύο ακμές στο γράφημα: η ακμή $\(i,l\)$ (αφού $a_(il) = 1)$ και η άκρη $\( l,j\)$ (αφού $a_(lj) = 1$) και επομένως η διαδρομή $\(( \(i,l\), \(l,j\) )\)$ από $i $- th κορυφή στην κορυφή $j$th μήκους δύο (μια διαδρομή δύο ακμών). Εδώ μιλάμε για μονοπάτι, όχι για αλυσίδα, αφού η κατεύθυνση που υποδεικνύεται είναι από την κορυφή $i$th στην κορυφή $j$th. Έτσι, το $a_(ij)^((2))$ μας δίνει τον αριθμό όλων των μονοπατιών στο γράφημα (στη γεωμετρική ερμηνεία του γραφήματος) μήκους 2 που οδηγεί από την κορυφή $i$-th στην $j$ -ου.

Αν $k=3$, τότε $A^3 = A^2A = AA^2 = AAA$ και $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $ $\sum\limits_(l_1 = 1)^n (a_(il_1 ) ) \left((\sum\limits_(l_2 = 1)^n ( a_(l_1 l_2 ) a_(l_2 j) ) \right) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1 ) ) ) a_( l_1 l_2 ) a_(l_2 j) = \sum\limits_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$.

Ο όρος $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $ αν είναι ίσος με 1, ορίζει μια διαδρομή μήκους 3 που πηγαίνει από την κορυφή $i$-th στην $j$-th και διέρχεται τις κορυφές $l_1$ και $l_2$. Τότε το $a_(ij)^((3))$ μας δίνει τον αριθμό των μονοπατιών μήκους 3 που συνδέουν τις κορυφές $i$th και $j$th. ΣΕ γενική περίπτωσηΤο $a_(ij)^((k))$ καθορίζει τον αριθμό των μονοπατιών μήκους $k$ που συνδέουν τις κορυφές $i$-th και $j$-th. Σε αυτήν την περίπτωση, $a_(ij)^((k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1 ) a_(l_1 l_2 ) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

Είναι σαφές ότι η τιμή $a_(ii)^((k)) $ μας δίνει τον αριθμό των κλειστών μονοπατιών μήκους $k$ που ξεκινούν και τελειώνουν στην κορυφή $i$. Έτσι, μια διαδρομή μήκους 2 - $a_(il) a_(li)$, σημαίνει μια διαδρομή που περνά κατά μήκος της άκρης $\( i,l \)$ από την κορυφή $i$ στην κορυφή $l$ και πίσω. Επομένως $a_(ii)^((2)) = s_i$, δηλ. τα διαγώνια στοιχεία του πίνακα $A^2$ είναι ίσα με τις μοίρες των αντίστοιχων κορυφών.

Ας εξετάσουμε τώρα, μαζί με τον πίνακα $A$, τον πίνακα $\dot (A)$, ο οποίος διαφέρει από τον πίνακα $A$ μόνο στο ότι τα στοιχεία του (αριθμοί 0 ή 1) θεωρούνται στοιχεία της άλγεβρας Boole. Επομένως, οι ενέργειες με τέτοιους πίνακες θα εκτελούνται σύμφωνα με τους κανόνες της άλγεβρας Boole. Δεδομένου ότι οι ενέργειες πρόσθεσης και πολλαπλασιασμού πινάκων με στοιχεία Boolean περιορίζονται στις ενέργειες πρόσθεσης και πολλαπλασιασμού των στοιχείων αυτών των πινάκων σύμφωνα με τους κανόνες της Boolean αριθμητικής, ελπίζουμε ότι αυτό δεν θα οδηγήσει σε δυσκολίες. Ένας πίνακας με στοιχεία Boole θα ονομάζεται Boolean matrix. Είναι προφανές ότι οι πράξεις πρόσθεσης και πολλαπλασιασμού Boolean πινάκων είναι κλειστές στο σύνολο των Boolean πινάκων, δηλ. το αποτέλεσμα αυτών των πράξεων θα είναι πάλι ένας Boolean πίνακας.

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

Το αποτέλεσμα της προσθήκης δύο συμμετρικών πινάκων Boole της ίδιας τάξης θα είναι ένας Boolean συμμετρικός πίνακας της ίδιας τάξης με μηδενικά σε εκείνα τα μέρη όπου και οι δύο όροι έχουν μηδενικά και ένα σε εκείνα τα σημεία όπου τουλάχιστον ένας όρος έχει ένα. Στην ερμηνεία του γραφήματος, αυτή η λειτουργία ονομάζεται πράξη προσθήκη γραφήματος. Το άθροισμα δύο γραφημάτων, που δίνεται στο ίδιο σύνολο κορυφών με την ίδια αρίθμηση, καλείται ένα γράφημα του οποίου οι κορυφές i και j είναι μη γειτονικές αν είναι μη γειτονικές και στα δύο συστατικά του γραφήματος, και οι κορυφές i και j είναι γειτονικές αν είναι γειτονικές στο τουλάχιστον έναν γραφικό όρο.

Ας ερμηνεύσουμε τώρα τον δεύτερο βαθμό του πίνακα γειτνίασης Boole $\dot (A)^2$ με στοιχεία $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^ n (\dot ( a)_(il) \dot (a)_(lj) )$. Είναι σαφές ότι $\dot (a)_(ij)^((2)) = 1$ εάν τουλάχιστον ένας όρος $\dot (a)_(il) \dot (a)_(lj) $ είναι ίσος στο 1 και $\dot (a)_(ij)^(2)) = 0$ αν όλοι οι όροι είναι ίσοι με 0. Αν ο πίνακας $\dot (A)$ είναι ο πίνακας γειτνίασης κάποιου γραφήματος, π.χ. είναι ένας συμμετρικός (0,1) πίνακας με μηδενική κύρια διαγώνιο, τότε ο πίνακας $\dot (A)^2$, γενικά, δεν είναι πίνακας γειτνίασης ενός γραφήματος με την έννοια που δεχόμαστε, αφού όλα τα διαγώνια στοιχεία του είναι ίσα με 1 (αν το γράφημα δεν έχει μεμονωμένες κορυφές). Για να μπορούν να θεωρηθούν τέτοιοι πίνακες ως πίνακες γειτνίασης, πρέπει, όταν εξετάζουμε τις συνδέσεις μεταξύ των κορυφών κάποιου συνδεδεμένου συστήματος που ορίζουν αυτό το σύστημα ως γράφημα, να επιτρέψουμε σε ορισμένες κορυφές να συνδεθούν με τον εαυτό τους. Μια «ακμή» που ορίζει τη σύνδεση μιας ορισμένης κορυφής με τον εαυτό της ονομάζεται βρόχος. Περαιτέρω, όπως και πριν, με τη λέξη γράφημα θα εννοούμε ένα γράφημα χωρίς βρόχους και για ένα γράφημα με βρόχους, εάν αυτό δεν είναι ξεκάθαρο από τα συμφραζόμενα, θα το πούμε - ένα γράφημα με βρόχους.

Θεωρήστε το άθροισμα $\dot (A)^() = \dot (A) + \dot (A)^2$. Ο πίνακας $\dot (A)^()$ μας δίνει ένα γράφημα που λαμβάνεται από το αρχικό "κορεσμένο" με πρόσθετες συνδέσεις που αντιστοιχούν σε μονοπάτια μήκους 2. Δηλαδή, στο νέο γράφημα οι κορυφές $i$ και $ Το j$ είναι γειτονικό εάν είναι γειτονικά στο αρχικό γράφημα ή αυτές οι κορυφές συνδέονται με κάποιο μονοπάτι μήκους 2 και οι κορυφές $i$ και $j$ δεν είναι γειτονικές, εάν δεν είναι γειτονικές στο αρχικό γράφημα και εκεί δεν υπάρχει μονοπάτι μήκους 2 που συνδέει αυτές τις κορυφές.

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ ορίζεται παρόμοια. Δηλαδή στο γράφημα δίνεται από τη μήτραΟι κορυφές $\dot (A)^()$ $i$ και $j$ είναι γειτονικές εάν είναι γειτονικές στο γράφημα $\dot (A)^()$ ή αυτές οι κορυφές συνδέονται με κάποια διαδρομή μήκους 3 στο το αρχικό γράφημα και οι κορυφές $i$ και $j$ δεν είναι γειτονικές εάν δεν είναι γειτονικές στο γράφημα $\dot (A)^()$ και δεν υπάρχει διαδρομή μήκους 3 που να συνδέει αυτές τις κορυφές στο αρχικό γράφημα. Και ούτω καθεξής.

Γενικά, $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $. Είναι εύκολο να δούμε ότι όλα τα $\dot (A)^([k])$ για $k \ge n - 1$, όπου $n$ είναι η σειρά του πίνακα $\dot (A)$, είναι ίσα ο ένας στον άλλον. Πράγματι, εάν οι κορυφές $i$ και $j$ είναι συνδεδεμένες, τότε υπάρχει μια διαδρομή (αλυσίδα) που συνδέει αυτές τις κορυφές και, επομένως, υπάρχει μια απλή διαδρομή (απλή αλυσίδα) που συνδέει αυτές τις κορυφές. Η μέγιστη δυνατή απλή διαδρομή σε ένα γράφημα $n$-κορυφής έχει μήκος $n-1$ (ένα απλό μονοπάτι που συνδέει όλες τις διακριτές κορυφές του γραφήματος). Επομένως, εάν στον πίνακα $\dot (A)^()$ υπάρχει ένα 1 στη θέση $(i,j)$, τότε στην ίδια θέση στον πίνακα $\dot (A)^([k] )$ στο $k \ge n - 1$ θα είναι επίσης 1, αφού ο πίνακας $\dot (A)^()$ περιλαμβάνεται ως όρος Boole στον ορισμό του πίνακα $\dot (A)^([ κ])$. Εάν στον πίνακα $\dot (A)^()$ υπάρχει 0 στη θέση του $(i,j)$, τότε αυτό σημαίνει ότι δεν υπάρχει απλή αλυσίδα στο γράφημα που συνδέει τα $i$-th και $j $- κορυφές και, επομένως, δεν υπάρχει καθόλου αλυσίδα που να συνδέει αυτές τις κορυφές. Αυτό σημαίνει ότι στην υπό εξέταση περίπτωση και στον πίνακα $\dot (A)^([k])$ για $k \ge n - 1$ θα υπάρχει 0 στη θέση ($i$,$j)$. Αυτό αποδεικνύει η δήλωσή μας για την ισότητα όλων των πινάκων $\dot (A)^([k])$ για $k \ge n - 1$ στον πίνακα $\dot (A)^()$ και επομένως , ο ένας στον άλλον.

Καλείται ο πίνακας $\dot (A)^()$ μήτρα του μεταβατικού κλεισίματος της μήτρας$\dot (A)$, καθώς και ο πίνακας γειτνίασης του μεταβατικού κλεισίματος του γραφήματος που ορίζεται από τον πίνακα $\dot (A)$. Είναι προφανές ότι ο πίνακας του μεταβατικού κλεισίματος ενός συνδεδεμένου γραφήματος θα είναι ο πίνακας γειτνίασης πλήρες γράφημα, δηλ. ένας τετράγωνος πίνακας που αποτελείται μόνο από ένα. Αυτή η παρατήρηση μας δίνει επίσης μια μέθοδο για τον προσδιορισμό της συνδεσιμότητας ενός γραφήματος: ένα γράφημα συνδέεται εάν και μόνο εάν ο μεταβατικός πίνακας κλεισίματος του πίνακα γειτονίας του αποτελείται μόνο από ένα (θα είναι ο πίνακας του πλήρους γραφήματος).

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

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

Για να κατασκευάσουμε έναν πίνακα απόστασης για ένα γράφημα $n$-κορυφής με έναν πίνακα γειτνίασης $A$, ο οποίος θα έδειχνε την απόσταση μεταξύ οποιωνδήποτε δύο κορυφών, εισάγουμε υπόψη τους πίνακες $A^(\(k\)) = A^ ([k]) - A^()$, όπου $k = 2,3,...,n - 1$ και $A^(\(1\)) = A^() = A$. Η απουσία κουκκίδων πάνω από τον χαρακτηρισμό του πίνακα δείχνει ότι θεωρούμε τους πίνακες $A^([k])$ ($k = 1,2,...,n - 1)$ ως αριθμητικούς (0,1)-πίνακες, που λαμβάνεται φυσικά από τους πίνακες $\dot (A)^([k])$ (θεωρούμε τώρα τα Boolean στοιχεία 0 και 1 ως αριθμούς 0 και 1). Από τη μέθοδο κατασκευής πινάκων $A^([k])$ προκύπτει ότι $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$) και, επομένως, οι $A^(\(k\))$ ($k = 1,2,...,n - 1$) είναι (0,1)-πίνακες. Επιπλέον, ο πίνακας $A^(\(2\))$ περιέχει 1 μόνο σε εκείνα τα μέρη όπου οι κορυφές που καθορίζονται από αυτό το μέρος (αριθμός σειράς και αριθμός στήλης) συνδέονται με κάποια διαδρομή μήκους δύο και δεν συνδέονται με μικρότερη μονοπάτι. Ομοίως, το $A^(\(3\))$ περιέχει 1 μόνο σε εκείνα τα σημεία όπου οι κορυφές που ορίζονται από αυτό το μέρος συνδέονται με μια διαδρομή μήκους τρία και δεν συνδέονται με κανένα μονοπάτι μικρότερου μήκους, κ.λπ. Έτσι, ο πίνακας $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^(\(k\)))$ θα είναι ο απαιτούμενος πίνακας απόστασης. Το στοιχείο $d_(ij)$ αυτού του πίνακα θα είναι ίσο με την απόσταση μεταξύ των κορυφών $i$ και $j$. Θα υποδηλώσουμε επίσης την απόσταση μεταξύ των κορυφών $u$ και $v$ ως $d(u,v)$.

Σχόλιο.Συγκεκριμένος όρος προϊόντος $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ στοιχείο $a_(ij ) Το ^((k))$ της $k$-th δύναμης του πίνακα γειτνίασης $A^k$ καθορίζει μια συγκεκριμένη διαδρομή $(i,j)$-$i\(i,l_1\)l_1 \(l_1 , l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \)l_(k - 1) \(l_(k - 1) ,j\)j$ από $i$ -th κορυφή έως $j$-th. Ακολουθία γειτονικών κορυφών και ακμών που τις συνδέει $i\(i,l_1 \)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j\)j$ ονομάζεται επίσης $(i,j)$-διαδρομή. Μια διαδρομή διαφέρει από μια αλυσίδα που αποτελείται μόνο από διαφορετικές γειτονικές ακμές στο ότι η διαδρομή επιτρέπει ίσες ακμές. Μια απλή διαδρομή αποτελείται από διάφορες γειτονικές κορυφές και ακμές, δηλ. πρακτικά συμπίπτει με μια απλή αλυσίδα.

Είναι προφανές ότι το στοιχείο $d_(ij) $ του πίνακα απόστασης καθορίζει το μήκος της ελάχιστης αλυσίδας που συνδέει την κορυφή $i$th με την $j$th κορυφή.

Ας εξετάσουμε παραδείγματα των γραφημάτων που δίνονται στα Σχήματα 1 και 2, τους πίνακες γειτνίασης και τους πίνακες αποστάσεων τους.

Εικ. 1 (Γράφημα $\Gamma _1$, πίνακας γειτνίασης $A_1$, πίνακας απόστασης $D_1$).
$A_1 = \left(((\begin(array)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end(array) )) \δεξιά), $
$D_1 = \left(((\begin(array)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(array) )) \δεξιά) $

Ρύζι. 2 (Γράφημα $\Gamma _2$, πίνακας γειτνίασης $A_2$, πίνακας απόστασης $D_2$).
$A_2 = \left(((\begin(array)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0\ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end(πίνακας) )) \δεξιά)$,
$D_2 = \left(((\begin(array)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2\ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end(πίνακας) )) \δεξιά). $

Από τους πίνακες $D_1$ και $D_2$ μπορεί κανείς να προσδιορίσει εύκολα διαμέτρους$d_1$ του γραφήματος $\Gamma _1$ και $d_2$ του γραφήματος $\Gamma _2$, ως οι μέγιστες τιμές των στοιχείων αυτών των πινάκων. Άρα $d_1 = 3$ και $d_2 = 6$.

Εκτός από τον πίνακα απόστασης, η θεωρία γραφημάτων λαμβάνει υπόψη και άλλους πίνακες, τα στοιχεία των οποίων καθορίζονται μέσω του μήκους της διαδρομής. Τέτοια, για παράδειγμα, είναι μήτρα διέλευσης. ΣΕ μήτρα διέλευσης$(i,j)$th στοιχείο ίσο με μήκοςτο μεγαλύτερο μονοπάτι (μεγαλύτερη αλυσίδα) από την κορυφή $i$th έως την $j$th κορυφή, και αν δεν υπάρχουν καθόλου τέτοια μονοπάτια, τότε, σύμφωνα με τον ορισμό της απόστασης, το $(i,j)$ το στοιχείο του πίνακα διέλευσης ορίζεται ίσο με μηδέν.

Θα κάνουμε μια σημείωση στο τέλος της ενότητας σχετικά με τις μεθόδους για τον προσδιορισμό της ελάχιστης και της μέγιστης αλυσίδας χρησιμοποιώντας έναν πίνακα αποστάσεων που συνδέει τις κορυφές $i$-th και $j$-th στο γράφημα.

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

ΕκκεντρικότηταΤο $e(v)$ μιας κορυφής $v$ σε ένα συνδεδεμένο γράφημα $\Gamma$ ορίζεται ως μέγιστο $d(u,v)$ σε όλες τις κορυφές $u$ στο $\Gamma$. Ακτίνα κύκλουΤο $r(\Gamma)$ είναι η μικρότερη εκκεντρότητα των κορυφών. Σημειώστε ότι η μεγαλύτερη από τις εκκεντρότητες είναι ίση με τη διάμετρο του γραφήματος. Μια κορυφή $v$ ονομάζεται κεντρική κορυφή του γραφήματος $\Gamma$ εάν $e(v) = r(\Gamma)$; κέντρογράφημα $\Gamma$ είναι το σύνολο όλων των κεντρικών κορυφών.

Έτσι για το γράφημα $\Gamma _1$ από το Σχ. 1, η εκκεντρότητα της κορυφής 13 θα είναι ίση με 2 ($e(13) = 2$). Οι κορυφές 3, 5 και 10 θα έχουν τις ίδιες εκκεντρότητες ($e(3) = e(5) = e(10) = 2$). Μια εκκεντρότητα ίση με 2 θα είναι η μικρότερη για το γράφημα $\Gamma _1$, δηλ. $r(\Gamma _1) = 2$. Το κέντρο του γραφήματος $\Gamma _1$ θα αποτελείται από τις κορυφές 3, 5, 10 και 13. Η μεγαλύτερη εκκεντρότητα θα είναι 3 και θα είναι ίση, όπως σημειώθηκε παραπάνω, με τη διάμετρο του γραφήματος $\Gamma _1$.

Για το γράφημα $\Gamma _2$ από το Σχ. 2, η μόνη κορυφή 4 θα έχει τη μικρότερη εκκεντρότητα ($e(4) = r(\Gamma _2) = 3$). Συνεπώς, το κέντρο του γραφήματος $\Gamma _2$ αποτελείται από μια κορυφή 4. Η διάμετρος του γραφήματος $\Gamma _2$, όπως σημειώθηκε παραπάνω, είναι 6.

Το γράφημα $\Gamma _2$ είναι ένα δέντρο και η δομή του κέντρου οποιουδήποτε δέντρου περιγράφεται από το θεώρημα που δίνεται παρακάτω.

Το θεώρημα Jordan–Sylvester.Κάθε δέντρο έχει ένα κέντρο που αποτελείται είτε από μία κορυφή είτε από δύο γειτονικές κορυφές.

Απόδειξη.Ας συμβολίσουμε με $K_1$ ένα γράφημα που αποτελείται από μια απομονωμένη κορυφή και με $K_2$ ένα γράφημα που αποτελείται από δύο κορυφές που συνδέονται με μια ακμή. Εξ ορισμού, βάζουμε $e(K_1) = r(K_1) = 0$. Τότε το θεώρημα θα ισχύει για $K_1$ και $K_2$. Ας δείξουμε ότι κάθε δέντρο $T$ έχει τις ίδιες κεντρικές κορυφές με ένα δέντρο $(T)"$ που λαμβάνεται από το $T$ αφαιρώντας όλες τις κρεμαστές κορυφές του. Είναι σαφές ότι η απόσταση από μια δεδομένη κορυφή $u$ σε οποιαδήποτε άλλη κορυφή $v$ μπορεί να φτάσει υψηλότερη τιμήμόνο αν το $v$ είναι μια αναρτημένη κορυφή.

Έτσι, η εκκεντρότητα κάθε κορυφής του δέντρου $(T)"$ είναι ακριβώς ένα μικρότερη από την εκκεντρότητα της ίδιας κορυφής σε $T$. Από αυτό προκύπτει ότι οι κορυφές του δέντρου $T$ που έχουν τη μικρότερη εκκεντρότητα σε $ Το T$ συμπίπτει με τις κορυφές που έχουν τη μικρότερη εκκεντρότητα σε $(T)"$, δηλ. τα κέντρα των δέντρων $T$ και $(T)"$ συμπίπτουν. Εάν συνεχίσουμε τη διαδικασία αφαίρεσης κορυφών κρεμαστό, θα λάβουμε μια ακολουθία δέντρων με το ίδιο κέντρο με αυτό του $T$. Επειδή το $T$ είναι πεπερασμένο, θα φτάσουμε απαραιτήτως είτε στο $ K_1$, είτε στο $K_2$ Σε κάθε περίπτωση, όλες οι κορυφές του δέντρου που λαμβάνονται με αυτόν τον τρόπο σχηματίζουν το κέντρο του δέντρου, το οποίο, επομένως, αποτελείται είτε από μία μόνο κορυφή είτε. δύο γειτονικές κορυφές.

Ας δείξουμε τώρα πώς, χρησιμοποιώντας τον πίνακα απόστασης, μπορούμε να προσδιορίσουμε, για παράδειγμα, την ελάχιστη αλυσίδα που συνδέει την κορυφή 4 με την κορυφή 8 στο γράφημα $\Gamma _1$. Στον πίνακα $D_1$ το στοιχείο $d_(48) = 3$. Ας πάρουμε την 8η στήλη του πίνακα $D_1$ και ας βρούμε στη στήλη όλα τα στοιχεία αυτής της στήλης ίσα με 1. Τουλάχιστον ένα τέτοιο στοιχείο θα βρεθεί λόγω της συνδεσιμότητας του γραφήματος $D_1$. Στην πραγματικότητα, θα υπάρχουν τρεις τέτοιες μονάδες στην 8η στήλη, και βρίσκονται στην 5η, 6η και 7η σειρά. Ας πάρουμε τώρα την 4η σειρά και ας δούμε τα στοιχεία σε αυτήν που βρίσκονται στην 5η, 6η και 7η στήλη. Αυτά τα στοιχεία θα είναι 2, 3 και 3 αντίστοιχα. Μόνο το στοιχείο που βρίσκεται στην 5η στήλη είναι ίσο με 2 και, μαζί με το 1, που βρίσκεται στη θέση (5,8), δίνει το άθροισμα 3. Αυτό σημαίνει ότι η κορυφή 5 περιλαμβάνεται στην αλυσίδα $\( \(4, ?\), \(? ,5\), \(5,8\) \)$. Ας πάρουμε τώρα την 5η στήλη του πίνακα και ας εξετάσουμε το 1 αυτής της στήλης. Αυτά θα είναι στοιχεία που βρίσκονται στην 3η, 6η, 7η, 8η, 10η και 13η γραμμή. Επιστρέφουμε ξανά στην 4η γραμμή και βλέπουμε ότι μόνο στη διασταύρωση της τρίτης στήλης και της 4ης γραμμής υπάρχει ένα 1, το οποίο σε συνδυασμό με το 1 στη θέση του (3,5) δίνει συνολικά 2. Επομένως, η επιθυμητή αλυσίδα θα είναι $\( \ (4,3\), \(3,5\), \(5,8\) \)$. Έχοντας εξετάσει τώρα το Σχήμα 1, είμαστε πεπεισμένοι για την εγκυρότητα της λύσης που βρέθηκε.

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

Έστω G(V,X) ψευδογράφημα και οι κορυφές v και w (v¹w) αυτού του γραφήματος συνδέονται με μια διαδρομή. Τότε πρέπει να υπάρχει μια ελάχιστη διαδρομή που να συνδέει αυτές τις κορυφές. Ας συμβολίσουμε το μήκος αυτής της διαδρομής ως d(v, w). Ορίσαμε επίσης d(v, v) =0 για οποιαδήποτε κορυφή vÎV; d(v, w) = ¥ εάν δεν υπάρχει διαδρομή που να συνδέει τα v και w.

Η τιμή d(v,w) που ορίζεται με αυτόν τον τρόπο για οποιεσδήποτε κορυφές v και w του γραφήματος G(V, X) ονομάζεται την απόσταση μεταξύ v και w.

Ο αριθμός των αποστάσεων σε ένα γράφημα με n κορυφές είναι ίσος με τον αριθμό των συνδυασμών C n 2 .

Αφήστε το γράφημα G(V,X) να είναι συνδεδεμένο. Ας ορίσουμε τις ακόλουθες έννοιες για αυτό:

Μέτρηση διάμετρος: d(G) = maxd(v, w).

Εκκεντρότητα (μέγιστη μετατόπιση) της κορυφής: r(v) = maxd(v, w);

Ακτίνα γραφήματος: r(G) = min r(v);

Κέντρο γραφήματος: οποιαδήποτε κορυφή vÎV τέτοια ώστε r(v) = r(G).

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

Παράδειγμα. Βρείτε τα μετρικά χαρακτηριστικά της γραφικής παράστασης που δίνονται από το διάγραμμα:

Ας βρούμε όλες τις αποστάσεις, λαμβάνοντας υπόψη ότι d(v, w) = d(w, v).

Ο αριθμός των αποστάσεων σε αυτό το γράφημα C 5 2 = 5!/3!2! = 10: d(v 1 , v 2) = 1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2, v 3) = 1, d(v 2, v 4) = 1, d(v 2, v 5) = 2, d(v 3, v 4) = 1, d(v 3, v 5) = 2, d(v 4, v 5) = 1.

Διάμετρος της γραφικής παράστασης d(G) =3.

Εκκεντρότητες κορυφής: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Ακτίνα γραφήματος r(G) = 2.

Τα κέντρα του γραφήματος είναι v 2, v 3, v 4.

3. Ελάχιστες διαδρομές σε φορτωμένα γραφήματα

Ένα γράφημα G(V, X) ονομάζεται φορτωμένο εάν μια συνάρτηση που ονομάζεται συνάρτηση βάρους καθορίζεται στο σύνολο των ακμών του γραφήματος, το οποίο εκχωρεί σε κάθε ακμή x ΟΧ του γραφήματος έναν ορισμένο αριθμό l(x). Η τιμή l(x) ονομάζεται μήκος τόξου.

Μπορεί να δοθεί η τιμή l(x). διαφορετική σημασία: κόστος μεταφοράς, χρόνος ταξιδιού, απόσταση μεταξύ σημείων, κατανάλωση βενζίνης κ.λπ.

Το άθροισμα των μηκών των ακμών που περιλαμβάνονται σε μια διαδρομή ονομάζεται μήκος διαδρομής.

Σημειώστε ότι αν για όλα τα x О Х l(x) = 1, τότε το γράφημα μπορεί να θεωρηθεί ως μη φορτωμένο.

Μια διαδρομή στο γράφημα G(V, X) από την κορυφή v στην κορυφή w (v¹w) ονομάζεται ελάχιστη εάν έχει το ελάχιστο μήκος μεταξύ όλων των διαδρομών στο γράφημα G(V, X) από την κορυφή v στην κορυφή w.

Ας περιοριστούμε σε γραφήματα για τα οποία l(x)>0.

Κατά την αναζήτηση της ελάχιστης διαδρομής σε ένα φορτωμένο γράφημα με l(x)>0

Ας χρησιμοποιήσουμε την ίδια πρόταση όπως για το μη φορτωμένο γράφημα, δηλαδή:

οποιαδήποτε ελάχιστη διαδρομή είναι ένα απλό κύκλωμα.

Ας εξετάσουμε τώρα το πρόβλημα της εύρεσης της ελάχιστης διαδρομής σε ένα φορτωμένο γράφημα.

Αφήστε το γράφημα G(V,X) να φορτωθεί, ο αριθμός των κορυφών n ³ 2, είναι απαραίτητο να κατασκευαστεί μια ελάχιστη διαδρομή από v 1 έως v n .

Ας παρουσιάσουμε τον αλγόριθμο.

Βήμα 1. Αντιστοιχίστε έναν δείκτη a(v i) σε κάθε κορυφή: a(v 1) = 0, a(v i) = ¥, i ¹ 1. Χρωματίστε την κορυφή v 1 και βάλτε v = v 1.

Βήμα 2. Για κάθε άχρωμη κορυφή v j αλλάξτε τον δείκτη σύμφωνα με τον κανόνα:

a(v j) = min (a(v j), a(v) + l(v, v j)).

Χρωματίστε την κορυφή για την οποία το a(v j) είναι η μικρότερη επίσης χρωματίστε την άκρη που οδηγεί στην επιλεγμένη. αυτό το βήμακορυφή v j . Σύνολο v = v j .

Βήμα 3. Εάν v = v j, τερματίστε τη διαδικασία, καθώς η συντομότερη διαδρομή είναι από v 1 έως v n. αν v ¹ v n , τότε μεταβείτε στο βήμα 2.

Σχόλιο. Το βήμα 2 είναι αδύνατο εάν όλα τα a(v j)= ¥. Σε αυτήν την περίπτωση, η κορυφή v n δεν είναι προσβάσιμη.

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

Βήμα 1. Χρωματίστε την κορυφή v 1 . Ας αντιστοιχίσουμε δείκτες στις κορυφές: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Υποθέτουμε v 1 = v.

a(v 2) = min (¥, 0+4) = 4,

a(v 3) = min (¥, 0+7) = 7,

a(v 4) = min (¥, 0+3) = 3,

a(v 5) = min (¥, 0+¥) = ¥,

a(v 6) = min (¥, 0+¥) = ¥.

Χρωματίστε την κορυφή v 4 και την άκρη (v 1 , v 4 ).

Βήμα 3. Εφόσον η κορυφή v 6 δεν είναι έγχρωμη, εκτελούμε το βήμα 2, υποθέτοντας v = v 4 .

a(v 2) = min (4, 3+¥) = 4,

a(v 3) = min (7, 3+¥) = 7,

a(v 5) = min (¥, 3+3) = 6,

a(v 6) = min (¥, 3+¥) = ¥.

Χρωματίστε την κορυφή v 2 και την άκρη (v 1 , v 2 ).

Βήμα 3. Εφόσον η κορυφή v 6 δεν είναι χρωματισμένη, εκτελούμε το βήμα 2, υποθέτοντας v = v 2.

a(v 3) = min (7, 4+3) = 7,

a(v 5) = min (6, 4+2) = 6,

a(v 6) = min (¥, 4+¥) = ¥.

Χρωματίστε την κορυφή v 5 και την άκρη (v 4 , v 5 ).

Βήμα 3. Εφόσον η κορυφή v 6 δεν είναι έγχρωμη, εκτελούμε το βήμα 2, υποθέτοντας v = v 5 .

a(v 3) = min (7, 6+¥) = 7,

a(v 6) = min (¥, 6+2) = 8.

Χρωματίστε την κορυφή v 3 και την άκρη (v 1 , v 3 ).

Βήμα 3. Εφόσον η κορυφή v 6 δεν είναι έγχρωμη, εκτελούμε το βήμα 2, υποθέτοντας v = v 3 .

a(v 6) = min (8, 7+2) = 8.

Χρωματίστε την κορυφή v 6 και την άκρη (v 5 , v 6 ).

Εφόσον το vertex v 6 είναι έγχρωμο, σταματάμε να δουλεύουμε. Έχουμε λάβει την ελάχιστη διαδρομή v 1 v 4 v 5 v 6 , το μήκος της οποίας είναι 8 .

Σημειώστε ότι σε αυτήν την περίπτωση αυτή δεν είναι η μόνη ελάχιστη διαδρομή για τις κορυφές v 1 και v 6, αφού στον αλγόριθμο ήταν δυνατό να χρωματίσουμε αντί για την άκρη (v 4, v 5) την άκρη (v 2, v 5), τότε θα παίρναμε άλλη διαδρομή ίδιου μήκους.

4. Προβλήματα στα δέντρα

Ένα γράφημα ονομάζεται άκυκλο αν δεν έχει κύκλους.

Ένα γράφημα χωρίς κύκλους ονομάζεται δάσος.

Ένα δέντρο είναι ένα συνδεδεμένο άκυκλο γράφημα.

Έστω ένα συνδεδεμένο μη κατευθυνόμενο γράφημα. Δεδομένου ότι οποιεσδήποτε δύο κορυφές του γραφήματος είναι συνδεδεμένες, υπάρχουν απλές αλυσίδες με άκρα και . Μπορεί να υπάρχουν πολλές τέτοιες αλυσίδες. Τα μήκη τους είναι μη αρνητικοί ακέραιοι. Επομένως, μεταξύ των κορυφών και πρέπει να υπάρχει απλή μικρότερο μήκος αλυσίδας. Το μήκος της μικρότερης αλυσίδας που συνδέει τις κορυφές και συμβολίζεται με το σύμβολο και ονομάζεται απόστασημεταξύ των κορυφών και . A-priory .

Είναι εύκολο να επαληθευτεί ότι η έννοια της απόστασης που εισάγεται με αυτόν τον τρόπο ικανοποιεί τα αξιώματα της μετρικής:

2. εάν και μόνο εάν ;

3. ;

4. Η τριγωνική ανισότητα είναι αληθής:

Για μια σταθερή κορυφή του γραφήματος, η απόσταση από την κορυφή που είναι πιο απομακρυσμένη από αυτήν είναι: , που ονομάζεται εκκεντρικότητα (ανώτατο όριο διαγραφή) κορυφές.

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

.

Μια απλή αλυσίδα της οποίας το μήκος είναι ίσο με ονομάζεται διαμετρικά αλυσίδα. Προφανώς, η διάμετρος του γραφήματος είναι ίση με τη μεγαλύτερη μεταξύ όλων των εκκεντροτήτων των κορυφών του γραφήματος. Η κορυφή ονομάζεται περιφερειακός, Αν .

Η ελάχιστη εκκεντρότητα των κορυφών ενός συνδεδεμένου γραφήματος ονομάζεται ακτίνα κύκλουκαι δηλώνουν:

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

Για απεικόνιση, ας δούμε το γράφημα στο Σχ. 4.29. Εδώ

Να γιατί

Η κορυφή 2 είναι το κέντρο του γραφήματος και όλες οι άλλες κορυφές είναι περιφερειακές. Η αλυσίδα 1, 2, 3 είναι μία από τις διαμετρικές αλυσίδες.

Για ένα συνδεδεμένο δίγραφο, η απόσταση μεταξύ των κορυφών και ορίζεται ως η απόσταση μεταξύ των κορυφών και στο μη κατευθυνόμενο αντίγραφο αυτού του γραφήματος.

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

Διαβάσεις γραφήματος

Έχει ήδη σημειωθεί ότι η αρχή της θεωρίας γραφημάτων συνδέεται με το πρόβλημα των γεφυρών Königsberg. Αυτό το έργο, διάσημο στην εποχή του, είναι το εξής. Επτά γέφυρες της πόλης Koenigsberg (τώρα Καλίνινγκραντ) βρίσκονταν στον ποταμό Pregel όπως φαίνεται στην Εικ. 4.30. Το καθήκον είναι να φύγετε από το σπίτι και να επιστρέψετε πίσω, διασχίζοντας κάθε γέφυρα μόνο μία φορά.

Δεδομένου ότι μόνο οι διαβάσεις γεφυρών είναι σημαντικές στο πρόβλημα, το σχέδιο πόλης μπορεί να περιοριστεί στην εικόνα ενός γραφήματος (ακριβέστερα, ενός πολυγράφου), στο οποίο οι άκρες αντιστοιχούν σε γέφυρες και οι κορυφές αντιστοιχούν σε διάφορα διαιρεμένα μέρη της πόλης, τα οποία υποδεικνύονται με γράμματα (Εικ. 4.30, δεξιά). Ο Euler έδειξε ότι είναι αδύνατο να περπατήσετε σε όλες τις γέφυρες Königsberg μία φορά και να επιστρέψετε πίσω. Στο έργο του που δημοσιεύτηκε το 1736 διατύπωσε και έλυσε τα εξής κοινό πρόβλημαθεωρία γραφημάτων: υπό ποιες συνθήκες ένα συνδεδεμένο γράφημα περιέχει έναν κύκλο που διέρχεται από κάθε μία από τις ακμές του.

Ένας κύκλος σε ένα γράφημα ονομάζεται Ο Eulerian, εάν περιέχει όλες τις άκρες του γραφήματος. Καλείται ένα συνδεδεμένο γράφημα που περιέχει έναν κύκλο Eulerian Ο Eulerianμετρώ. Ένα τέτοιο γράφημα μπορεί να σχεδιαστεί χωρίς να σηκωθεί το μολύβι από το χαρτί και χωρίς να επαναληφθούν οι γραμμές.

Για παράδειγμα, το γράφημα που φαίνεται στο Σχ. Το 4.31 είναι Eulerian επειδή περιέχει τον Eulerian κύκλο 1, 2, 3, 4, 5, 6, 4, 2, 6, 1. Υπάρχουν άλλοι κύκλοι Eulerian σε αυτό το γράφημα. Είναι σαφές ότι δύο τέτοιοι κύκλοι διαφέρουν μεταξύ τους μόνο ως προς τη σειρά με την οποία διασχίζουν τις άκρες.

Θεώρημα 4.7.(L. Euler, 1736 .) Ένα συνδεδεμένο γράφημα είναι Eulerian αν και μόνο αν οι μοίρες όλων των κορυφών του είναι άρτιες.

Η αλυσίδα ονομάζεται Ο Eulerian, εάν περιέχει όλες τις άκρες του γραφήματος.

Θεώρημα 4.8(L. Euler, 1736 .) Ένας πολύγραφος έχει μια αλυσίδα Eulerian εάν και μόνο εάν είναι συνδεδεμένος και ο αριθμός των κορυφών περιττού βαθμού είναι 0 ή 2.

Παρά την «ομοιότητα» στους ορισμούς για τους κύκλους Eulerian και Hamiltonian, οι αντίστοιχες θεωρίες που καθορίζουν τα κριτήρια ύπαρξης και τους αλγόριθμους αναζήτησης για τέτοιους κύκλους έχουν λίγα κοινά. Θεώρημα Euler (Θεώρημα 4.7)καθιστά εύκολο τον προσδιορισμό του εάν ένα γράφημα είναι Eulerian. Έχουν αναπτυχθεί αλγόριθμοι που διευκολύνουν την εύρεση των κύκλων Euler ενός γραφήματος Euler. Όσον αφορά τα γραφήματα Hamiltonian, η κατάσταση εδώ είναι σημαντικά διαφορετική. Συνήθως είναι πολύ δύσκολο να απαντηθεί το ερώτημα εάν ένα συγκεκριμένο γράφημα είναι Χαμιλτονιανό. Γενικό κριτήριο, παρόμοιο με το κριτήριο Euler, δεν υπάρχει εδώ. Αλλά, όπως αποδείχθηκε, μεταξύ του συνόλου όλων των γραφημάτων, υπάρχουν αμελητέα λίγα γραφήματα Euler, αλλά υπάρχουν αρκετά γραφήματα Hamiltonian.