Matrice delle adiacenze
Da Wikipedia, l'enciclopedia libera.
La matrice delle adiacenze 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.
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.
Se al posto degli 1 nella matrice si trovano dei numeri, questi sono da interpretare come il peso attribuito a ciascun arco. Ad esempio se l'insieme dei vertici del grafo rappresenta una serie di punti su una cartina 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.
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
