Vai al contenuto

1.5 Il rango della matrice di incidenza

Parte 1 · Grafi · Capitolo 1 · Capitolo 1: Grafi · Dispensa, volume 1 (PDF) · Esercizi: Grafi · App: Ricerca su grafo: BFS e DFS

  • Sia \(G=(N,A)\) un grafo diretto con matrice di incidenza nodi-arco \(\mat{B}\). Indichiamo con \(\mat{B}_a\) il colonna dell'arco \(a\), e da \(\vet{e}_i\) il vettore unitario \(i\)-esimo di \(\R^n\), in modo che \(\mat{B}_{(i,j)}=\vet{e}_i-\vet{e}_j\).

Lemma 1.20: colonne di una foresta

Se gli archi \(F \subseteq A\) formano una foresta, le colonne \(\mat{B}_a\), \(a \in F\), sono linearmente indipendenti.

Dimostrazione

Per induzione su \(|F|\); per \(F=\emptyset\) non c'è nulla da dimostrare. Lascia che \(|F| \ge 1\) e \(\sum_{a \in F} \lambda_a \mat{B}_a=\vet{0}\).

  1. Un componente della foresta con almeno un arco è un albero con almeno \(2\) nodi, quindi ha una foglia \(\ell\) (Lemma 1.14); lascia che \(a' \in F\) sia l'unico arco di \(F\) incidente a \(\ell\).

  2. La riga \(\ell\) della combinazione contiene solo il termine di \(a'\), che è \(\pm\lambda_{a'}\); quindi \(\lambda_{a'}=0\).

  3. Gli archi \(F \setminus \{a'\}\) formano ancora una foresta, e \(\sum_{a \in F \setminus \{a'\}} \lambda_a \mat{B}_a=\vet{0}\): per induzione tutti gli \(\lambda_a\) sono zero. □

Lemma 1.21: colonne di un ciclo

Se gli archi \(C \subseteq A\) formano un ciclo, le colonne \(\mat{B}_a\), \(a \in C\), sono linearmente dipendenti.

Dimostrazione

Lascia che il ciclo visiti \(v_0,v_1,\dots,v_k=v_0\) lungo gli archi \(c_1,c_2,\dots,c_k\) e lascia che \(\varepsilon_t=+1\) se \(c_t\) è avanti e \(\varepsilon_t=-1\) se è indietro. In entrambi i casi \(\varepsilon_t \mat{B}_{c_t}=\vet{e}_{v_{t-1}}- \vet{e}_{v_t}\) e la somma dei telescopi:

\[ \sum_{t=1}^{k} \varepsilon_t \mat{B}_{c_t}=\vet{e}_{v_0}-\vet{e}_{v_k}=\vet{0}. \]

I coefficienti \(\varepsilon_t\) non sono zero, quindi le colonne sono linearmente dipendenti. □

Teorema 1.22: rango della matrice di incidenza

Sia \(G=(N,A)\) un grafo diretto il cui grafo non orientato sottostante ha componenti connessi \(k\). Poi

\[ \rank(\mat{B})=|N|-k . \]
Dimostrazione

Sia \(N_1,N_2,\dots,N_k\) gli insiemi di nodi dei componenti e \(n=|N|\).

  • \(\rank(\mat{B}) \ge n-k\). Per Corollario 1.18 il grafo ha uno spanning foresta con archi \(n-k\), le cui colonne sono linearmente indipendenti per Lemma 1.20.

  • \(\rank(\mat{B}) \le n-k\). Ogni arco ha entrambi gli estremi nello stesso componente, quindi per ogni \(h \in \{1,2,\dots,k\}\) le righe dei nodi di \(N_h\) si sommano al vettore zero. I vettori \(k\) \(\vet{y}^h\) con \(y^h_i=1\) per \(i \in N_h\) e \(0\) altrimenti soddisfare \((\vet{y}^h)' \mat{B}=\vet{0}'\).

  • Questi vettori \(k\) hanno supporti disgiunti, quindi sono linearmente indipendenti: lo spazio nullo sinistro di \(\mat{B}\) ha dimensione almeno \(k\) e \(\rank(\mat{B}) \le n-k\).

□

Corollario 1.23: basi della matrice di incidenza

Lascia che il grafo non orientato sottostante di \(G=(N,A)\) sia connesso. Quindi \(\rank(\mat{B})=|N|-1\), la matrice ottenuta da l'eliminazione di una riga qualsiasi di \(\mat{B}\) ha il rango di riga completo e un insieme di colonne \(|N|-1\) di \(\mat{B}\) è lineare indipendente se e solo se i suoi archi formano un albero coprente.

Dimostrazione

Il rango è \(n-1\) di Teorema 1.22 con \(k=1\).

  • La somma delle righe dà zero, quindi ogni riga è meno la somma delle altre: le rimanenti righe \(n-1\) si estendono sulla riga spazio, che ha dimensione \(n-1\), e sono linearmente indipendenti.

  • Se gli archi \(n-1\) formano un albero ricoprente, le loro colonne sono indipendenti da Lemma 1.20. Se le loro colonne sono indipendenti, gli archi non contengono cicli Lemma 1.21: sono aciclici con archi \(n-1\), quindi un albero ricoprente di Teorema 1.17(c).

□

Esempio 1.8: il rango sul grafo di riferimento

  • Il grafo di riferimento è debolmente connesso, quindi \(\rank(\mat{B})=6-1=5\); Eliminazione gaussiana sulla matrice di Esempio 1.4 lo conferma.

  • Le cinque colonne dello albero ricoprente di Esempio 1.7, \(a_1,a_2,a_3,a_5,a_7\), sono linearmente indipendente.

  • Il ciclo diretto \(2,4,3,2\) utilizza \(a_3=(2,4)\), \(a_6=(4,3)\), \(a_4=(3,2)\), tutto avanti e \(\mat{B}_{a_3}+\mat{B}_{a_6}+\mat{B}_{a_4}=\vet{0}\).

  • Senza gli archi \((4,6)\) e \((5,6)\) il grafo ha le due componenti \(\{1,2,3,4,5\}\) e \(\{6\}\), e il il rango della sua matrice di incidenza è \(6-2=4\).

Il rango della matrice di incidenza nodo-arco è il numero di nodi meno il numero di componenti connessi. Nell'a grafo connesso una riga è ridondante e le basi di \(\mat{B}\) sono esattamente gli albero ricoprente.

Avanti: 1.6 Ricerca su grafi