Matrice de adiacență
From Wikipedia, the free encyclopedia
În teoria grafurilor și informatică, o matrice de adiacență este o matrice pătrată folosită pentru a reprezenta un graf finit. Elementele matricei indică dacă perechea de noduri corespunzătoare sunt sau nu adiacente în graf.
În cazul special al unui grafic finit simplu, matricea de adiacență este o matrice (0,1)(d) cu zerouri pe diagonală. Dacă graful este neorientat, atunci matricea de adiacență este simetrică. Relația dintre un graf și valorile proprii și vectorii proprii ale matricei sale de adiacență este studiată în teoria spectrală a grafurilor(d).
Se face distincția între matricea de adiacență și matricea de incidență a unui graf, o altă reprezentare matricială ale cărei elemente indică dacă perechile nod–muchie sunt incidente sau nu.