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

Δήλωση. Εάν υπάρχει μια διαδρομή για δύο κορυφές που τις συνδέουν, τότε πρέπει να υπάρχει μια ελάχιστη διαδρομή που να συνδέει αυτές τις κορυφές. Ας υποδηλώσουμε το μήκος αυτής της διαδρομής ωςρε(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

Απόφαση.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ακτίνα γραφήματος 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 παραμένει άγνωστη. Θα πολλαπλασιάσουμε τον πίνακα γειτνίασης στον εαυτό του μέχρι τη μήτρα Το μη μηδενικό στοιχείο δεν θα εμφανιστεί . Στη συνέχεια το αντίστοιχο στοιχείο του πίνακα απόστασης ίσο με το βαθμόπίνακες γειτνίασης: . Στο επόμενο βήμα, παίρνουμε

Συνεπώς, , και τελικά

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

Έστω 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).

Ο αριθμός των αποστάσεων στη δεδομένη στήλη С 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 нX του γραφήματος κάποιο αριθμό l(x). Η τιμή l(x) ονομάζεται μήκος τόξου.

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

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

Σημειώστε ότι αν για όλα τα 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 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 ).

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

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

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 παραμένει άγνωστη. Θα πολλαπλασιάσουμε τον πίνακα γειτνίασης στον εαυτό του μέχρι τη μήτρα Το μη μηδενικό στοιχείο δεν θα εμφανιστεί . Τότε το αντίστοιχο στοιχείο του πίνακα απόστασης είναι ίσο με το βαθμό του πίνακα γειτνίασης: . Στο επόμενο βήμα, παίρνουμε