La matrice di incidenza in un grafo
La matrice di incidenza di un grafo è una matrice che rappresenta la relazione tra i vertici e i grafi dove le righe rappresentano i vertici e le colonne rappresentano gli spigoli.
E' un'altra forma di rappresentazione matematica di un grafo, sia esso diretto (digrafo) o non diretto.
Grafi semplici
In un grafo non direzionato, la matrice di incidenza è una matrice \( n \times m \), dove \( n \) è il numero di vertici \( m \) è il numero di spigoli
Ogni colonna della matrice rappresenta uno spigolo del grafo, e ogni riga rappresenta un vertice.
Gli elementi della matrice sono marcati con
- 1 se il vertice corrispondente alla riga è un estremo dello spigolo corrispondente alla colonna
- 0 se il vertice corrispondente alla riga non è un estremo dello spigolo corrispondente alla colonna
A differenza della matrice di adiacenza che si focalizza sui rapporti tra vertici, la matrice di incidenza mostra la relazione tra vertici e spigoli.
Esempio
Consideriamo un grafo con 4 vertici \( A, B, C, D \) e 4 spigoli \( e_1, e_2, e_3, e_4 \).
Dove \( e_1 \) collega \( A \) a \( B \), \( e_2 \) collega \( B \) a \( C \), \( e_3 \) collega \( C \) a \( D \), e \( e_4 \) collega \( D \) a \( A \).
Possiamo rappresentare la matrice di incidenza come segue.
\[
\begin{array}{c|cccc}
& e_1 & e_2 & e_3 & e_4 \\
\hline
A & 1 & 0 & 0 & 1 \\
B & 1 & 1 & 0 & 0 \\
C & 0 & 1 & 1 & 0 \\
D & 0 & 0 & 1 & 1 \\
\end{array}
\]
Ogni colonna rappresenta uno spigolo, e ogni riga rappresenta un vertice.
Il valore "1" indica che il vertice corrispondente è collegato da quel particolare spigolo.
Viceversa, il valore "0" significa che il vertice non è collegato allo spigolo.
Grafi diretti
Per i digrafi, la matrice di incidenza si adatta per riflettere la direzione degli spigoli.
In questo caso le righe rappresentano i vertici (nodi) mentre le colonne rappresentano gli spigoli (archi).
Gli elementi della matrice possono essere
- -1 se il vertice corrispondente alla riga è l'estremo iniziale dell'arco corrispondente alla colonna
- 1 se il vertice corrispondente alla riga è l'estremo finale dell'arco corrispondente alla colonna
- 0 se il vertice corrispondente alla riga non è un estremo dell'arco corrispondente alla colonna
Questa rappresentazione offre un modo diretto per visualizzare e manipolare le relazioni spigolo-vertice nei grafi, essendo particolarmente adatta per questioni di connettività e percorrenza.
Nella matrice di incidenza di un digrafo la somma di ogni colonna è nulla, perché ogni arco ha sempre una coda (vertice di origine) e una testa (vertice di destinazione).
Esempio
Prendiamo come esempio un digrafo con 4 vertici e 4 archi direzionati \( e_1, e_2, e_3, e_4 \).
Dove \( e_1 \) va da \( A \) a \( B \), \( e_2 \) va da \( B \) a \( C \), \( e_3 \) va da \( C \) a \( D \), e \( e_4 \) va \( D \) ad \( A \).
In questo caso la matrice di incidenza sarebbe:
\[
\begin{array}{c|cccc}
& e_1 & e_2 & e_3 & e_4 \\
\hline
A & -1 & 0 & 0 & 1 \\
B & 1 & -1 & 0 & 0 \\
C & 0 & 1 & -1 & 0 \\
D & 0 & 0 & 1 & -1 \\
\end{array}
\]
Ogni riga rappresenta un nodo (vertice) mentre ogni colonna rappresenta un arco del digrafo.
Nella matrice:
- -1 indica che il vertice è l'origine dell'arco
- 1 indica che il vertice è la destinazione dell'arco
- 0 indica che il vertice non è connesso dall'arco
Alcune rappresentazioni potrebbero utilizzare differenti convenzioni per indicare la direzione degli archi, o la presenza di cappi nei digrafi, a seconda del contesto o del software utilizzato.
La matrice di incidenza è particolarmente utile per analizzare la struttura dei grafi e dei digrafi in termini di connessioni tra vertici e spigoli.
