Questa voce o sezione sull'argomento teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Questa voce sull'argomento teoria dei grafi è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia.

La matrice delle adiacenze o matrice di connessione costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi finiti. Dato un qualsiasi grafo la sua matrice delle adiacenze è costituita da una matrice binaria quadrata che ha come indici di righe e colonne i nomi dei vertici del grafo. Nel posto ${\displaystyle (i,j)}$ della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice ${\displaystyle i}$ al vertice ${\displaystyle j,}$ altrimenti si trova uno 0.

Questi tipi di matrici sono ampiamente utilizzate nella stesura di algoritmi che operano su grafi finiti e in generale nella loro rappresentazione informatica. Nel caso la matrice di adiacenza sia una matrice sparsa, ad essa è preferibile l'impiego della lista di adiacenza.

Se al posto degli 1 nella matrice si trovano dei numeri, questi sono da interpretare come il peso attribuito a ciascun collegamento. Ad esempio se l'insieme dei vertici del grafo rappresenta una serie di punti su una carta geografica, il peso degli archi può essere interpretato come la distanza dei punti che questi connettono. Se la somma degli elementi di ogni colonna è uguale a 1, allora la matrice è detta matrice di Markov, in quanto applicabile a un processo markoviano.

Nel caso della rappresentazione di grafi non orientati, la matrice è simmetrica rispetto alla diagonale principale.

Una delle caratteristiche fondamentali di questa matrice è di permettere di ottenere il numero di percorsi di lunghezza ${\displaystyle n}$ da un nodo ${\displaystyle i}$ ad un nodo ${\displaystyle j;}$ per ottenerlo è sufficiente fare la potenza ${\displaystyle n}$-sima della matrice e vedere il numero che compare al posto ${\displaystyle i,j.}$

• Grafo (tipo di dato astratto)
• Connessione (matematica)
• Matrice di transizione
• Ponte (teoria dei grafi)
• Lista di adiacenza

• Wikimedia Commons contiene immagini o altri file sulla matrice delle adiacenze

• (EN) Eric W. Weisstein, Matrice delle adiacenze, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica