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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Πίνακας γειτνίασης
Ταξινόμηση
Dewey 512
MSC2010 05C50

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

Συγκεκριμένα, ο πίνακας γειτνίασης ενός πεπερασμένου γράφου G με n κορυφές είναι ο πίνακας διαστάσεων n × n όπου το μη διαγώνιο στοιχείο aij είναι ο αριθμός ακμών από την κορυφή i στην κορυφή j, και το διαγώνιο στοιχείο aii, είναι ανάλογα με τη σύμβαση είτε ο αριθμός είτε το διπλάσιο των ακμών (βρόχοι) από την κορυφή i στον εαυτό της. Σε μη κατευθυνόμενους γράφους συνήθως χρησιμοποιείται η δεύτερη σύμβαση (το διπλάσιο του αριθμού των βρόχων), ενώ σε κατευθυνόμενους γράφους κατά κανόνα χρησιμοποιείται η πρώτη σύμβαση. Υπάρχει μοναδικός πίνακας γειτνίασης για κάθε κλάση ισομορφισμού γράφων και είναι διάφορος του πίνακα γειτνίασης οποιασδήποτε άλλης κλάσης ισομορφισμού γράφων. Στην ειδική περίπτωση ενός πεπερασμένου απλού γράφου, ο πίνακας γειτνίασης είναι ένας (0,1)-πίνακας με μηδενικά στοιχεία στη διαγώνιό του. Αν ο γράφος είναι μη κατευθυνόμενος, ο πίνακας γειτνίασης είναι συμμετρικός.

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

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Η σύμβαση που ακολουθείται στα παραδείγματα είναι ότι μια ακμή μεταξύ των στοιχείων i και j, ορίζει την τιμή του στοιχείου aii ίση με 1 στον πίνακα ενός μη κατευθυνόμενου γράφου.

Σημασμένος γράφος Πίνακας γειτνίασης
6n-graph2.svg \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.

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg


Ο γράφος Nauru

Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg


Οι συντεταγμένες είναι 0-23.
Τα άσπρα πεδία αντιπροσωπεύουν στοιχεία του πίνακα που είναι ίσα με 0 ενώ τα χρωματισμένα στοιχεία που είναι ίσα με 1.

Symmetric group 4; Cayley graph 4,9; numbers.svg


Ο κατευθυνόμενος γράφος Cayley συμμετρικής ομάδας S4

Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg


Ο πίνακας δεν είναι συμμετρικός
επειδή ο γράφος είναι κατευθυνόμενος.

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

Πίνακας γειτνίασης διμερούς γράφου[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

Ιδιότητες[Επεξεργασία | επεξεργασία κώδικα]

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

Έστω δύο κατευθυνόμενοι ή μη κατευθυνόμενοι γράφοι G_1 and G_2 με πίνακες γειτνίασης A_1 and A_2. Οι G_1 και G_2 είναι ισόμορφοι, αν και μόνο αν υπάρχει ένας πίνακας μεταθέσεων P τέτοιος ώστε

P A_1 P^{-1} = A_2.

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

Αν A είναι ο πίνακας γειτνίασης του κατευθυνόμενου ή μη κατευθυνόμενου γράφου G, τότε ο πίνακας An (το γινόμενο n πινάκων ίσων με τον A) έχει μια ενδιαφέρουσα ερμηνεία: το στοιχείο της γραμμής i και της στήλης j ισούται με τον αριθμό των περιπάτων μήκους n από την κορυφή i στην κορυφή j. Αυτό σημαίνει ότι ο αριθμός των τριγώνων σε έναν μη κατευθυνόμενο γράφο G προκύπτει από΄τη διαίρεση του ίχνους του A3 με το 6. Η κύρια διαγώνιος κάθε πίνακα γειτνίασης που αντιστοιχεί σε γράφο χωρίς βρόχους έχει όλα τα στοιχεία της μηδενικά. Σημειώνεται ότι 'βρόχος' σημαίνει π.χ. A->A και όχι 'κύκλος' όπως π.χ. A->B->A.

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

Παραλλαγές[Επεξεργασία | επεξεργασία κώδικα]

Ένας (a, b, c)-πίνακας γειτνίασης A ενός απλού γράφου έχει Aij = a αν η ij είναι ακμή, b αν δεν είναι και c στη διαγώνιο. Ο πίνακας γειτνίασης Σάιντελ είναι ένας (−1,1,0)-πίνακας γειτνίασης. Αυτός ο πίνακας χρησιμοποιείται για τη μελέτη ισχυρά κανονικών γράφων [1]

Ο πίνακας αποστάσεων έχει στη θέση (i,j) την απόσταση ανάμεσα στις κορυφές vi and vj . Απόσταση είναι το μήκος της συντομότερης διαδρομής που συνδέει δύο κορυφές. Στην περίπτωση που το μήκος των ακμών δεν ορίζεται ρητά, το μήκος μιας διαδρομής ισούται με τον αριθμό των ακμών που περιέχει. Ο πίνακας αποστάσεων μοιάζει με τον πίνακα γειτνίασης υψωμένο σε δύναμη, που αντί να εκφράζει τη σύνδεση ή μη δύο κορυφών, καταγράφει την ακριβή απόσταση μεταξύ τους.

Δομές Δεδομένων[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

  1. 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. 

Σχετικές Πηγές[Επεξεργασία | επεξεργασία κώδικα]

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

  • Fluffschack — an educational Java web start game demonstrating the relationship between adjacency matrices and graphs.