Matrice delle adiacenze

Da Wikipedia, l'enciclopedia libera.
Un grafo, la sua matrice delle adiacenze è \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}

La matrice delle adiacenze o matrice di connessione costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi. In particolare è ampiamente utilizzata nella stesura di algoritmi che operano su grafi e in generale nella loro rappresentazione informatica. Nel caso sia una matrice sparsa, alla matrice è preferibile l'impiego della lista di adiacenza.

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 (i,j) della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice i al vertice j, altrimenti si trova uno 0.


Exquisite-kfind.png Per approfondire, vedi Matrice di Markov.

Se al posto degli 1 nella matrice si trovano dei numeri, questi sono da interpretare come il peso attribuito a ciascun collegamento, e la matrice è detta matrice di Markov, in quanto applicabile ad un processo markoviano. 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.

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 dei cammini da un nodo i ad un nodo j che devono attraversare n nodi. Per ottenere tutto ciò è sufficiente fare la potenza n-sima della matrice e vedere il numero che compare al posto i,j.

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica