Matrice di adiacenza

In matematica , in teoria dei grafi , in informatica , una matrice di adiacenza per un grafo finito con $n$ vertici è una matrice di dimensione $n \times n il$ cui elemento non diagonale $a ij$ è il numero di archi che collegano il vertice $i$ al vertice $j$ . L'elemento diagonale $a ii$ è il numero di cicli al vertice $i$ (per grafici semplici , questo numero è quindi sempre uguale a 0 o 1).

Questo strumento matematico è ampiamente utilizzato come struttura dati in informatica (come la rappresentazione per lista di adiacenza ), ma si trova naturalmente anche nelle catene di Markov . In particolare, la probabilità limite viene interpretata come un autovettore .

Definizione

Supponiamo che sia un semplice grafico, dove . Supponiamo inoltre che i vertici di $G$ siano numerati arbitrariamente . La matrice di adiacenza $A$ di $G$ relativa a questo insieme di vertici è la matrice booleana $n$ $\times$ $n$ $A$ con $G = (V, E)$ $\ sinistra | V \ destra | = n$ $v_ {1}, \ ldots, v_ {n}$

$a _ {{ij}} = \ left \ {{\ begin {array} {rl} 1 & {\ mbox {si}} (v_ {i}, v_ {j}) \ in E \\ 0 & {\ mbox {altrimenti.}} \ end {array}} \ right.$

Esempi

Grafico etichettato	Matrice di adiacenza
	${\ displaystyle {\ begin {pmatrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \ end {pmatrix}}}}$
	${\ Displaystyle \ quad {\ begin {pmatrix} 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\ end { pmatrix}}.}$

Proprietà

Unicità

Una volta fissato l'ordine degli n vertici (ci sono n ! Possibili scelte per questo ordine), esiste un'unica matrice di adiacenza per ogni grafo. Questa non è la matrice di adiacenza di nessun altro grafo. Nel caso particolare di un grafo semplice e finito, la matrice di adiacenza è una matrice binaria con zeri sulla diagonale. Se il grafico non è orientato, la matrice di adiacenza è simmetrica , il che significa che $a ij = a ji$ .

Proprietà del file iterato

Se $A$ è la matrice di adiacenza di un insieme finito grafo $G$ i cui vertici sono numerate da $1$ a $n$ , il numero di percorsi di lunghezza esattamente $k$ va da $i$ a $j$ è il coefficiente in posizione $( i , j )$ della matrice $A k$ - questo se ogni bordo tra due vertici ha una lunghezza uguale a $1$ .

Proprietà spettrali

La teoria dei grafi spettrali studia le proprietà dello spettro di diverse matrici, la matrice di adiacenza. In particolare, il secondo autovalore più grande è legato alla velocità di espansione del grafico.

Vedi anche

Link esterno

(en) Café math: Adjacency Matrices of Graphs : Applicazione di matrici di adiacenza al calcolo di percorsi generatori di serie.