1.2 Rappresentazioni di un grafo¶
Parte 1 · Grafi · Capitolo 1 · Capitolo 1: Grafi · Dispensa, volume 1 (PDF) · Esercizi: Grafi · App: Ricerca su grafo: BFS e DFS
Definizione 1.7: matrice di adiacenza
La matrice di adiacenza di un grafo orientato \(G=(N,A)\) è la matrice \(n \times n\) \(\mat{M}\) con voci
La matrice di adiacenza di un grafo non orientato ha \(m_{uv}=m_{vu}=1\) per ogni lato \(\{u,v\}\): è simmetrica.
Definizione 1.8: matrice di incidenza nodo-arco
Sia \(G=(N,A)\) un grafo diretto con archi \(a_1,a_2,\dots,a_m\). La matrice di incidenza nodo–arco è la \(n \times m\) matrice \(\mat{B}\) con una riga per nodo e una colonna per arco, le cui voci sono
-
Ogni colonna di \(\mat{B}\) ha esattamente uno \(+1\) (la coda) e uno \(-1\) (la testa), quindi la somma delle righe di \(\mat{B}\) è il vettore zero.
-
La riga \(i\) ha uno \(+1\) per ogni arco di \(\delta^+(i)\) e uno \(-1\) per ogni arco di \(\delta^-(i)\): ha \(\deg^+(i)+\deg^-(i)\) voci diverse da zero.
-
La matrice di incidenza vertici–lati di un grafo non orientato ha un \(1\) in entrambi i punti finali di ogni lato.
Esempio 1.4: le matrici del grafo di riferimento
La matrice di adiacenza \(\mat{M}\) e la matrice di incidenza nodo-arco \(\mat{B}\) del grafo di riferimento di Esempio 1.2 vengono mostrati con l'indice di ogni riga (un nodo) e di ogni colonna (un nodo in \(\mat{M}\), un arco in \(\mat{B}\)):
Ad esempio, la colonna \(a_6=(4,3)\) ha \(+1\) nella riga \(4\) (la coda) e \(-1\) nella riga \(3\) (la testa). Riga \(6\) di \(\mat{M}\) è zero, perché il nodo \(6\) non ha successori.
Definizione 1.9: elenchi di adiacenze ed elenchi di archi
Sia \(G=(N,A)\) un grafo diretto.
-
Le liste di adiacenza memorizzano, per ogni nodo \(i\), la lista \(L(i)\) dei suoi successori, cioè le teste degli archi di \(\delta^+(i)\). In questo modulo ogni lista è ordinata per indice crescente.
-
Arc list memorizza due array di lunghezza \(m\), con la coda e la testa di ogni arco.
Per un grafo non orientato la lista \(L(v)\) contiene l'intorno \(N(v)\) e ogni arco appare in due liste.
Esempio 1.5: le liste del grafo di riferimento
Le liste di adiacenza e la lista di archi del grafo di riferimento sono:
| \(i\) | \(L(i)\) |
|---|---|
| \(1\) | \(2,~3\) |
| \(2\) | \(4\) |
| \(3\) | \(2,~5\) |
| \(4\) | \(3,~6\) |
| \(5\) | \(4,~6\) |
| \(6\) | (vuoto) |
| arco | \(a_1\) | \(a_2\) | \(a_3\) | \(a_4\) | \(a_5\) | \(a_6\) | \(a_7\) | \(a_8\) | \(a_9\) |
|---|---|---|---|---|---|---|---|---|---|
| coda | \(1\) | \(1\) | \(2\) | \(3\) | \(3\) | \(4\) | \(4\) | \(5\) | \(5\) |
| testa | \(2\) | \(3\) | \(4\) | \(2\) | \(5\) | \(3\) | \(6\) | \(4\) | \(6\) |
Gli elenchi del grafo non orientato sottostante sono \(L(1)=\{2,3\}\), \(L(2)=\{1,3,4\}\), \(L(3)=\{1,2,4,5\}\), \(L(4)=\{2,3,5,6\}\), \(L(5)=\{3,4,6\}\) e \(L(6)=\{4,5\}\).
1.2.1 Spazio e tempo di accesso¶
- La tabella mette a confronto le quattro rappresentazioni di un grafo orientato. Lo spazio è il numero di voci memorizzate; le due operazioni sono il test di un arco e la scansione dei successori di un nodo.
| rappresentazione e spazio ed è \((i,j) \in A\)? | successori di \(i\) | ||
|---|---|---|---|
| matrice di adiacenza | \(n^2\) | \(O(1)\) | \(O(n)\) |
| matrice di incidenza nodo-arco | \(n\,m\) | \(O(m)\) | \(O(m)\) |
| elenco archi | \(2\,m\) | \(O(m)\) | \(O(m)\) |
| elenchi di adiacenze | \(n+m\) | \(O(\deg^+(i))\) | \(O(\deg^+(i))\) |
-
Per il grafo di riferimento le quattro rappresentazioni memorizzano le voci \(36\), \(54\), \(18\) e \(15\).
-
Un grafo diretto semplice ha \(m \le n(n-1)\). Nelle reti delle applicazioni \(m\) è molto più piccolo di \(n^2\) (il grafo è sparse) e le liste di adiacenza sono la rappresentazione scelta per gli algoritmi.
1.2.2 La matrice di incidenza e la conservazione del flusso¶
-
Dato un valore \(x_{ij}\) per ogni arco, la riga \(i\) di \(\mat{B}\vet{x}\) è ciò che lascia il nodo \(i\) meno ciò che vi entra:
\[ (\mat{B}\vet{x})_i=\sum_{(i,j) \in \delta^+(i)} x_{ij} \;-\; \sum_{(j,i) \in \delta^-(i)} x_{ji}, \qquad \forall i \in N. \] -
Con \(x_{ij}=1\) per ogni arco del grafo di riferimento, \(\mat{B}\vet{x}\) è il vettore delle differenze \(\deg^+(i)-\deg^-(i)\):
\[ \mat{B}\vet{x}=(2,\,-1,\,0,\,0,\,1,\,-2)' . \]
La matrice di incidenza nodo-arco ha \(+1\) nella coda e \(-1\) nella testa di ogni arco; gli elenchi di adiacenza memorizzano a tracciare un grafo nello spazio \(n+m\) e fornire i successori di un nodo nel tempo \(O(\deg^+(i))\).
Avanti: 1.3 Connettività