Στα μαθηματικά και στην επιστήμη υπολογιστών, ο πίνακας γειτνίασης χρησιμοποιείται για να αναπαραστήσει τις κορυφές ενός γράφου, οι οποίες συνδέονται με άλλες κορυφές. Ένας άλλος πίνακας αναπαράστασης του γράφου είναι ο πίνακας προσπτώσεων.
Συγκεκριμένα, ο πίνακας γειτνίασης ενός πεπερασμένου γράφου G με n κορυφές είναι ο πίνακας διαστάσεων n × n όπου το μη διαγώνιο στοιχείο aij είναι ο αριθμός ακμών από την κορυφή i στην κορυφή j, και το διαγώνιο στοιχείο aii, είναι ανάλογα με τη σύμβαση είτε ο αριθμός είτε το διπλάσιο των ακμών (βρόχοι) από την κορυφή i στον εαυτό της. Σε μη κατευθυνόμενους γράφους συνήθως χρησιμοποιείται η δεύτερη σύμβαση (το διπλάσιο του αριθμού των βρόχων), ενώ σε κατευθυνόμενους γράφους κατά κανόνα χρησιμοποιείται η πρώτη σύμβαση. Υπάρχει μοναδικός πίνακας γειτνίασης για κάθε κλάση ισομορφισμού γράφων και είναι διάφορος του πίνακα γειτνίασης οποιασδήποτε άλλης κλάσης ισομορφισμού γράφων. Στην ειδική περίπτωση ενός πεπερασμένου απλού γράφου, ο πίνακας γειτνίασης είναι ένας (0,1)-πίνακας με μηδενικά στοιχεία στη διαγώνιό του. Αν ο γράφος είναι μη κατευθυνόμενος, ο πίνακας γειτνίασης είναι συμμετρικός.
Η σχέση μεταξύ ενός γράφου και των ιδιοτιμών και ιδιοδιανυσμάτων του πίνακα γειτνίασής του μελετάται στη φασματική θεωρία γράφων.
Παραδείγματα
Η σύμβαση που ακολουθείται στα παραδείγματα είναι ότι μια ακμή μεταξύ των στοιχείων i και j, ορίζει την τιμή του στοιχείου aii ίση με 1 στον πίνακα ενός μη κατευθυνόμενου γράφου.
| Σημασμένος γράφος | Πίνακας γειτνίασης |
|---|---|
 |
\( {\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}} \)
Οι συντεταγμένες είναι 1-6. |
;_numbers.svg)
|
.svg)
|
|
.svg)
|
Όλα τα στοιχεία του πίνακα γειτνίασης ενός πλήρους γράφου είναι ίσα με 1 εκτός από τα στοιχεία της διαγωνίου που είναι ίσα με 0.
Ο πίνακας γειτνίασης ενός κενού γράφου είναι ίσος με το μηδενικό πίνακα.
Πίνακας γειτνίασης διμερούς γράφου
Ο πίνακας γειτνίασης A ενός διμερούς γράφου του οποίου τα μέρη έχουν r και s κορυφές έχει τη μορφή
\( {\displaystyle A={\begin{pmatrix}O&B\\B^{T}&O\end{pmatrix}},} \)
όπου B είναι ένας πίνακας r × s και O είναι ένας πίνακας με όλα του τα στοιχεία ίσα με 0. Ο πίνακας B αντιπροσωπεύει μοναδικά τους διμερείς γράφους.
Ιδιότητες
Ο πίνακας γειτνίασης ενός μη κατευθυνόμενου απλού γράφου είναι συμμετρικός, και ως κε τούτου έχει ένα πλήρες σύνολο από πραγματικές ιδιοτιμές και μια ορθογώνια βάση ιδιοδιανυσμάτων. Το σύνολο των ιδιοτιμών ενός γράφου είναι το φάσμα του γράφου.
Έστω δύο κατευθυνόμενοι ή μη κατευθυνόμενοι γράφοι G 1 {\displaystyle G_{1}} {\displaystyle G_{1}} and G 2 {\displaystyle G_{2}} {\displaystyle G_{2}} με πίνακες γειτνίασης A 1 {\displaystyle A_{1}} {\displaystyle A_{1}} and A 2 {\displaystyle A_{2}} {\displaystyle A_{2}}. Οι G 1 {\displaystyle G_{1}} {\displaystyle G_{1}} και G 2 {\displaystyle G_{2}} {\displaystyle G_{2}} είναι ισόμορφοι, αν και μόνο αν υπάρχει ένας πίνακας μεταθέσεων P {\displaystyle P} P τέτοιος ώστε
\( {\displaystyle PA_{1}P^{-1}=A_{2}.} \)
Ειδικότερα, οι A 1 {\displaystyle A_{1}} {\displaystyle A_{1}} και A 2 {\displaystyle A_{2}} {\displaystyle A_{2}} είναι όμοιοι και επομένως έχουν το ίδιο ελάχιστο πολυώνυμο, χαρακτηριστικό πολυώνυμο, ιδιοτιμές, ορίζουσα και ίχνος. Μπορούν επομένως να λειτουργήσουν ως δείκτες ισομορφισμού των γράφων. Παρόλα αυτά, δύο γράφοι μπορούν να έχουν το ίδιο σύνολο ιδιοτιμών και να μην είναι ισόμορφοι.
Αν A είναι ο πίνακας γειτνίασης του κατευθυνόμενου ή μη κατευθυνόμενου γράφου G, τότε ο πίνακας An (το γινόμενο n πινάκων ίσων με τον A) έχει μια ενδιαφέρουσα ερμηνεία: το στοιχείο της γραμμής i και της στήλης j ισούται με τον αριθμό των περιπάτων μήκους n από την κορυφή i στην κορυφή j. Αυτό σημαίνει ότι ο αριθμός των τριγώνων σε έναν μη κατευθυνόμενο γράφο G προκύπτει από΄τη διαίρεση του ίχνους του A3 με το 6. Η κύρια διαγώνιος κάθε πίνακα γειτνίασης που αντιστοιχεί σε γράφο χωρίς βρόχους έχει όλα τα στοιχεία της μηδενικά. Σημειώνεται ότι 'βρόχος' σημαίνει π.χ. A->A και όχι 'κύκλος' όπως π.χ. A->B->A.
Για \( {\displaystyle \left(d\right)} \) -κανονικά γραφήματα, d είναι επίσης μια ιδιοτιμή του A για το διάνυσμα \( {\displaystyle v=\left(1,\dots ,1\right)} \) και ο G είναι συνδεδεμένος αν και μόνο αν η πολλαπλότητα του d είναι 1. Μπορεί, επίσης, να αποδειχθεί ότι − d {\displaystyle -d} {\displaystyle -d} είναι επίσης μια ιδιοτιμή του A αν G είναι ένας συνδεδεμένος διμερής γράφος. Τα παραπάνω είναι αποτελέσματα του θεωρήματος των Περόν-Φρομπένιους.
Παραλλαγές
Ένας (a, b, c)-πίνακας γειτνίασης A ενός απλού γράφου έχει Aij = a αν η ij είναι ακμή, b αν δεν είναι και c στη διαγώνιο. Ο πίνακας γειτνίασης Σάιντελ είναι ένας (−1,1,0)-πίνακας γειτνίασης. Αυτός ο πίνακας χρησιμοποιείται για τη μελέτη ισχυρά κανονικών γράφων [1]
Ο πίνακας αποστάσεων έχει στη θέση (i,j) την απόσταση ανάμεσα στις κορυφές vi and vj . Απόσταση είναι το μήκος της συντομότερης διαδρομής που συνδέει δύο κορυφές. Στην περίπτωση που το μήκος των ακμών δεν ορίζεται ρητά, το μήκος μιας διαδρομής ισούται με τον αριθμό των ακμών που περιέχει. Ο πίνακας αποστάσεων μοιάζει με τον πίνακα γειτνίασης υψωμένο σε δύναμη, που αντί να εκφράζει τη σύνδεση ή μη δύο κορυφών, καταγράφει την ακριβή απόσταση μεταξύ τους.
Δομές Δεδομένων
Για τη χρήση ως μια δομή δεδομένων, η κύρια εναλλακτική του πίνακα γειτνίασης είναι η λίστα γειτνίασης. Επειδή κάθε στοιχείο του πίνακα γειτνίασης απαιτεί μόνο ένα bit για την αποθήκευσή του, μπορεί να αναπαρασταθεί με πολύ συμπαγή τρόπο, χρησιμοποιώντας μόνο \( {\displaystyle {n^{2}}/8} \) bytes αποθηκευτικού χώρου, όπου n είναι ο αριθμός των κορυφών.
Αντίθετα, για αραιούς γράφους, οι λίστες γειτνίασης επικρατούν επειδή δε χρησιμοποιούν καθόλου χώρο για ακμές που δεν υφίστανται. Χρησιμοποιώντας την υλοποίηση μιας απλής δομής δεδομένων πίνακα σε έναν 32 bit υπολογιστή, μια λίστα γειτνίασης ενός μη κατευθυνόμενου γράφου απαιτεί περίπου 8 e {\displaystyle 8e} {\displaystyle 8e} bytes αποθηκευτικού χώρου, όπου e {\displaystyle e} e είναι ο αριθμός των ακμών.
Δεδομένου ότι ένας απλός γράφος μπορεί να έχει έως \( {\displaystyle n^{2}} \) ακμές, ορίζουμε ως d\( {\displaystyle d=e/n^{2}} \)την πυκνότητα του γράφου. Ισχύει \( {\displaystyle 8e>n^{2}/8} \), δηλαδή η λίστα γειτνίασης καταλαμβάνει περισσότερο αποθηκευτικό χώρο όταν \( {\displaystyle d>1/64} \). Γι’ αυτό το λόγο η χρήση λίστας γειτνίασης δικαιολογείται για αραιούς γράφους.
Διαφορετικές δομές δεδομένων είναι κατάλληλες για διαφορετικές λειτουργίες. Η εύρεση όλων των κορυφών που είναι γειτονικές σε μια συγκεκριμένη κορυφή σε μια λίστα γειτνίασης είναι τόσο απλή όσο η προσπέλαση της λίστας. Σε έναν πίνακα γειτνίασης απαιτείται η ανάγνωση μιας ολόκληρης γραμμής που διαρκεί χρόνο O(n). Η διαπίστωση της ύπαρξης ακμής ανάμεσα σε δύο κορυφές μπορεί να γίνει με μια απλή ανάγνωση σε έναν πίνακα γειτνίασης. Αντίθετα απαιτεί χρόνο ανάλογο με τον ελάχιστο των βαθμών των δύο κορυφών σε μια λίστα γειτνίασης.
Αναφορές
Seidel, J. J. (1968). «Strongly Regular Graphs with (−1,1,0) Adjacency Matrix Having Eigenvalue 3». Lin. Alg. Appl. 1 (2): 281–298. doi:10.1016/0024-3795(68)90008-6.
Σχετικές Πηγές
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). «Section 22.1: Representations of graphs». Introduction to Algorithms (Second έκδοση). MIT Press and McGraw-Hill. σελίδες 527–531. ISBN 0262032937.
Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. ISBN 0387952411.
Εξωτερικοί σύνδεσμοι
Fluffschack — an educational Java web start game demonstrating the relationship between adjacency matrices and graphs.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
