Πίνακας γειτνίασης

Στην θεωρία γράφων, ο πίνακας γειτνίασης είναι ένας τετραγωνικός πίνακας που αναπαριστά έναν γράφο.

Συγκεκριμένα, ο πίνακας γειτνίασης ενός πεπερασμένου απλού γράφου ${\displaystyle G=(V,E)}$ με κόμβους ${\displaystyle V=\{1,2,\ldots ,n\}}$ είναι ο πίνακας ${\displaystyle A}$ διαστάσεων ${\displaystyle n\times n}$ με στοιχεία ${\displaystyle 0}$ ή ${\displaystyle 1}$, όπου^{[1]:12[2]:87-89[3]:19-20}

${\displaystyle A_{ij}={\begin{cases}1&{\text{αν }}(i,j)\in E,\\0&{\text{αν }}(i,j)\not \in E.\end{cases}}}$

Σε γράφους με πολλαπλές ακμές το στοιχείο ${\displaystyle A_{ij}}$ δίνει το πλήθος των ακμών μεταξύ του κόμβου ${\displaystyle i}$ και του ${\displaystyle j}$. Σε γράφους με βρόγχους, διαγώνιο στοιχείο ${\displaystyle A_{ii}}$, είναι ανάλογα με τη σύμβαση είτε το πλήθος είτε το διπλάσιο του πλήθους των βρόγχων από τον κόμβο ${\displaystyle i}$ στον εαυτό της. ^[4]

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

Η σχέση μεταξύ ενός γράφου και των ιδιοτιμών και ιδιοδιανυσμάτων του πίνακα γειτνίασής του μελετάται στη φασματική θεωρία γράφων.^[5]

Ένας άλλος πίνακας αναπαράστασης του γράφου είναι ο πίνακας προσπτώσεων.

Παραδείγματα

Η σύμβαση που ακολουθείται στα παρακάτω παραδείγματα είναι ότι μια ακμή μεταξύ των στοιχείων ${\displaystyle i}$ και ${\displaystyle j}$, ορίζει την τιμή του στοιχείου ${\displaystyle A_{ii}}$ ίση με ${\displaystyle 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.
Ο γράφος Nauru	Οι συντεταγμένες είναι 0-23. Τα άσπρα πεδία αντιπροσωπεύουν στοιχεία του πίνακα που είναι ίσα με 0 ενώ τα χρωματισμένα στοιχεία που είναι ίσα με 1.
Ο κατευθυνόμενος γράφος Κειλι της συμμετρικής ομάδας S4	Ο πίνακας δεν είναι συμμετρικός επειδή ο γράφος είναι κατευθυνόμενος.

• Όλα τα στοιχεία του πίνακα γειτνίασης ενός πλήρους γράφου είναι ίσα με 1 εκτός από τα στοιχεία της διαγωνίου που είναι ίσα με 0.
• Ο πίνακας γειτνίασης ενός μηδενικού γράφου είναι ίσος με το μηδενικό πίνακα.

Πίνακας γειτνίασης διμερούς γράφου

Ο πίνακας γειτνίασης ${\displaystyle A}$ ενός διμερούς γράφου του οποίου τα δύο μέρη έχουν ${\displaystyle r}$ και ${\displaystyle s}$ κόμβους αντίστοιχα, έχει τη μορφή

${\displaystyle A={\begin{pmatrix}O&B\\B^{T}&O\end{pmatrix}},}$

όπου ${\displaystyle B}$ είναι ένας πίνακας ${\displaystyle r\times s}$ και ${\displaystyle O}$ είναι ένας πίνακας με όλα του τα στοιχεία ίσα με ${\displaystyle 0}$. Ο πίνακας ${\displaystyle B}$ αντιπροσωπεύει μοναδικά τους διμερείς γράφους.

Ιδιότητες

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

• Έστω δύο κατευθυνόμενοι ή μη κατευθυνόμενοι γράφοι ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ με πίνακες γειτνίασης ${\displaystyle A_{1}}$ and ${\displaystyle A_{2}}$. Οι ${\displaystyle G_{1}}$ και ${\displaystyle G_{2}}$ είναι ισόμορφοι, αν και μόνο αν υπάρχει ένας πίνακας μεταθέσεων ${\displaystyle P}$ τέτοιος ώστε

${\displaystyle PA_{1}P^{-1}=A_{2}}$.

Ειδικότερα, οι ${\displaystyle A_{1}}$ και ${\displaystyle A_{2}}$ είναι όμοιοι και επομένως έχουν το ίδιο ελάχιστο πολυώνυμο, χαρακτηριστικό πολυώνυμο, ιδιοτιμές, ορίζουσα και ίχνος. Μπορούν επομένως να λειτουργήσουν ως δείκτες ισομορφισμού των γράφων. Παρόλα αυτά, δύο γράφοι μπορούν να έχουν το ίδιο σύνολο ιδιοτιμών και να μην είναι ισόμορφοι.

• Αν ${\displaystyle A}$ είναι ο πίνακας γειτνίασης του κατευθυνόμενου ή μη κατευθυνόμενου γράφου ${\displaystyle G}$, τότε για τον πίνακα

${\displaystyle A^{k}=\underbrace {A\cdot \ldots \cdot A} _{k{\text{ φορές}}}}$,

ισχύει ότι το ${\displaystyle (A^{k})_{ij}}$, δηλαδή το στοιχείο της γραμμής i και της στήλης ${\displaystyle j}$ ισούται με το πλήθος των περιπάτων μήκους ${\displaystyle k}$ από τον κόμβο ${\displaystyle i}$ στον κόμβο ${\displaystyle j}$.

Αυτό σημαίνει ότι το πλήθος των τριγώνων σε έναν μη κατευθυνόμενο γράφο ${\displaystyle G}$ προκύπτει από τη διαίρεση του ίχνους του ${\displaystyle A^{3}}$ με το 6, δηλαδή ${\displaystyle \operatorname {tr} (A^{3})/6}$.

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

• Σε κάθε ${\displaystyle d}$-κανονικό γράφο, ${\displaystyle d}$ είναι επίσης μια ιδιοτιμή του A για το διάνυσμα ${\displaystyle v=\left(1,\dots ,1\right)}$ και ο ${\displaystyle G}$ είναι συνδεδεμένος αν και μόνο αν η πολλαπλότητα του ${\displaystyle d}$ είναι 1. Μπορεί, επίσης, να αποδειχθεί ότι ${\displaystyle -d}$ είναι επίσης μια ιδιοτιμή του ${\displaystyle A}$ αν ${\displaystyle G}$ είναι ένας συνδεδεμένος διμερής γράφος. Τα παραπάνω είναι αποτελέσματα του θεωρήματος των Περόν-Φρομπένιους.

Παραλλαγές

Ένας ${\displaystyle (a,b,c)}$-πίνακας γειτνίασης ${\displaystyle A}$ ενός απλού γράφου έχει ${\displaystyle A_{ij}=a}$ αν η ${\displaystyle (i,j)}$ είναι ακμή, ${\displaystyle b}$ αν δεν είναι και ${\displaystyle c}$ στη διαγώνιο. Ο πίνακας γειτνίασης Σάιντελ είναι ένας ${\displaystyle (-1,1,0)}$-πίνακας γειτνίασης. Αυτός ο πίνακας χρησιμοποιείται για τη μελέτη ισχυρά κανονικών γράφων ^[6]

Ο πίνακας αποστάσεων έχει στη θέση ${\displaystyle A_{ij}}$ την απόσταση ανάμεσα στους κόμβους ${\displaystyle i}$ και ${\displaystyle j}$. Απόσταση είναι το μήκος της συντομότερης διαδρομής που συνδέει δύο κόμβους. Στην περίπτωση που το μήκος των ακμών δεν ορίζεται ρητά, το μήκος μιας διαδρομής ισούται με τον αριθμό των ακμών που περιέχει. Ο πίνακας αποστάσεων μοιάζει με τον πίνακα γειτνίασης υψωμένο σε δύναμη, που αντί να εκφράζει τη σύνδεση ή μη δύο κορυφών, καταγράφει την ακριβή απόσταση μεταξύ τους.

Δομές Δεδομένων

Ο πίνακας γειτνίασης μπορεί να χρησιμοποιηθεί σε ένα πρόγραμμα ως δομή δεδομένων για την αναπαράσταση ενός γράφου.^[7] Η κύρια εναλλακτική του πίνακα γειτνίασης είναι η λίστα γειτνίασης. Επειδή κάθε στοιχείο του πίνακα γειτνίασης απαιτεί μόνο ένα bit για την αποθήκευσή του, μπορεί να αναπαρασταθεί με πολύ συμπαγή τρόπο, χρησιμοποιώντας μόνο ${\displaystyle {n^{2}}/8}$ bytes αποθηκευτικού χώρου, όπου ${\displaystyle n}$ είναι ο αριθμός των κορυφών.

Αντίθετα, για αραιούς γράφους, οι λίστες γειτνίασης επικρατούν επειδή δε χρησιμοποιούν καθόλου χώρο για ακμές που δεν υφίστανται. Χρησιμοποιώντας την υλοποίηση μιας απλής δομής δεδομένων πίνακα σε έναν 32 bit υπολογιστή, μια λίστα γειτνίασης ενός μη κατευθυνόμενου γράφου απαιτεί περίπου ${\displaystyle 8m}$ bytes αποθηκευτικού χώρου, όπου ${\displaystyle m}$ είναι ο αριθμός των ακμών.

Δεδομένου ότι ένας απλός γράφος μπορεί να έχει έως ${\displaystyle n^{2}}$ ακμές, ορίζουμε ως ${\displaystyle d=e/n^{2}}$ την πυκνότητα του γράφου. Ισχύει ${\displaystyle 8e>n^{2}/8}$, δηλαδή η λίστα γειτνίασης καταλαμβάνει περισσότερο αποθηκευτικό χώρο όταν ${\displaystyle d>1/64}$. Γι’ αυτό το λόγο η χρήση λίστας γειτνίασης δικαιολογείται για αραιούς γράφους.

Διαφορετικές δομές δεδομένων είναι κατάλληλες για διαφορετικές λειτουργίες. Η εύρεση όλων των κορυφών που είναι γειτονικές σε μια συγκεκριμένη κορυφή σε μια λίστα γειτνίασης είναι τόσο απλή όσο η προσπέλαση της λίστας. Σε έναν πίνακα γειτνίασης απαιτείται η ανάγνωση μιας ολόκληρης γραμμής που διαρκεί χρόνο ${\displaystyle \Theta (n)}$. Η διαπίστωση της ύπαρξης ακμής ανάμεσα σε δύο κορυφές μπορεί να γίνει με μια απλή ανάγνωση σε έναν πίνακα γειτνίασης σε χρόνο ${\displaystyle \Theta (1)}$. Αντίθετα απαιτεί χρόνο ανάλογο με τον ελάχιστο των βαθμών των δύο κορυφών σε μια λίστα γειτνίασης.

Παραπομπές

1. Diestel, Reinhard (2006). Graph theory (3η έκδοση). Berlin Heidelberg: Springer. ISBN 9783540261834. 
2. Kleinberg, Jon· Tardos, Éva. Algorithm design (Pearson new internat. [der] 1.ed έκδοση). Harlow: Pearson. ISBN 9781292023946. 
3. Knuth, Donald Ervin (1997). The art of computer programming. Upper Saddle River: Addison-Wesley. ISBN 978-0-201-03804-0. 
4. Σε μη κατευθυνόμενους γράφους συνήθως χρησιμοποιείται η δεύτερη σύμβαση (το διπλάσιο του αριθμού των βρόχων), ενώ σε κατευθυνόμενους γράφους κατά κανόνα χρησιμοποιείται η πρώτη σύμβαση.
5. Godsil, Chris· Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. ISBN 0387952411. 
6. 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. 
7. Cormen, Thomas H.· Leiserson, Charles E.· Rivest, Ronald L.· Stein, Clifford (2001). «Section 22.1: Representations of graphs». Introduction to Algorithms (2η έκδοση). MIT Press and McGraw-Hill. σελίδες 527–531. ISBN 0262032937. 

Εξωτερικοί σύνδεσμοι

• Πολυμέσα σχετικά με το θέμα Πίνακας γειτνίασης στο Wikimedia Commons
• VisualAlgo — εκπαιδευτική διαδραστική εφαρμογή για τους πίνακες γειτνίασης