Πίνακας γειτνίασης
From Wikipedia, the free encyclopedia
Στην θεωρία γράφων, ο πίνακας γειτνίασης είναι ένας τετραγωνικός πίνακας που αναπαριστά έναν γράφο.
Συγκεκριμένα, ο πίνακας γειτνίασης ενός πεπερασμένου απλού γράφου με κόμβους
είναι ο πίνακας
διαστάσεων
με στοιχεία
ή
, όπου[1]:12[2]:87-89[3]:19-20
Σε γράφους με πολλαπλές ακμές το στοιχείο δίνει το πλήθος των ακμών μεταξύ του κόμβου
και του
. Σε γράφους με βρόγχους, διαγώνιο στοιχείο
, είναι ανάλογα με τη σύμβαση είτε το πλήθος είτε το διπλάσιο του πλήθους των βρόγχων από τον κόμβο
στον εαυτό της. [4]
Υπάρχει μοναδικός πίνακας γειτνίασης για κάθε κλάση ισομορφισμού γράφων και είναι διάφορος του πίνακα γειτνίασης οποιασδήποτε άλλης κλάσης ισομορφισμού γράφων. Αν ο γράφος είναι μη κατευθυνόμενος, ο πίνακας γειτνίασης είναι συμμετρικός.
Η σχέση μεταξύ ενός γράφου και των ιδιοτιμών και ιδιοδιανυσμάτων του πίνακα γειτνίασής του μελετάται στη φασματική θεωρία γράφων.[5]
Ένας άλλος πίνακας αναπαράστασης του γράφου είναι ο πίνακας προσπτώσεων.