Componenti connesse di un grafo
Mi è venuta una curosità su come determinare il numero di componenti connesse di un grafo.
Chiarisco un po' il problema.
Siano \(V\), con \(|V|=N\), l'insieme dei vertici ed \(A\in \mathbb{M}_{N \times N}\) la matrice di adiacenza di un grafo \(\mathcal{G}\) non direzionato.
La matrice di adiacenza di un grafo è una matrice ad entrate binarie \(a_{ij}\in \{0,1\}\), le quali indicano la presenza (\(a_{ij}=1\)) o meno (\(a_{ij}=0\)) nel grafo di un arco congiungente lo \(i\)-esimo ed il \(j\)-esimo vertice; dato che il grafo \(\mathcal{G}\) in questione non è direzionato, la matrice \(A\) è simmetrica, cioè \(a_{ij}=a_{ji}\).
Due archi di \(\mathcal{G}\) si dicono adiacenti se essi hanno un vertice in comune; se gli archi sono individuati dai valori \(a_{ij}\) e \(a_{hk}\), tali archi sono adiacenti se \(i=k \text{ oppure } j=h\).
Un percorso in\(\mathcal{G}\) è un insieme finito di archi adiacenti.
Una componente connessa di \(\mathcal{G}\) è un sottoinsieme di \(V\) i cui elementi sono a due a due collegati da un percorso.
Chiamiamo \(\kappa\) il numero di componenti connesse di \(\mathcal{G}\): evidentemente \(\kappa \in \{1,\ldots ,N\}\); se \(\kappa =1\) il grafo si dice connesso, se \(\kappa =N\) il grafo è totalmente sconnesso (cioè non ci sono archi).
A questo punto, ecco il busillis.
Supponiamo che in \(\mathcal{G}\) non esistano archi "chiusi su loro stessi", ossia che \(a_{ii}=0\).
Formiamo la matrice \(L=(l_{ij})\) nel modo seguente:
\[l_{ij}:=\begin{cases} -a_{ij} &\text{, se } i\neq j \\ \sum_{k=1}^N a_{ik} &\text{, altrimenti.}\end{cases}\]
"Sperimentalmente" è facile constatare che per \(N\) piccoli vale la relazione:
\[\kappa =N-\text{rank }L\; .\]
Mi chiedevo: tale relazione è vera in generale?
E, in caso affermativo, come si dimostra questo fatto?
P.S.: Cosa consigliereste come riferimento base per la Teoria dei Grafi?
Chiarisco un po' il problema.
Siano \(V\), con \(|V|=N\), l'insieme dei vertici ed \(A\in \mathbb{M}_{N \times N}\) la matrice di adiacenza di un grafo \(\mathcal{G}\) non direzionato.
La matrice di adiacenza di un grafo è una matrice ad entrate binarie \(a_{ij}\in \{0,1\}\), le quali indicano la presenza (\(a_{ij}=1\)) o meno (\(a_{ij}=0\)) nel grafo di un arco congiungente lo \(i\)-esimo ed il \(j\)-esimo vertice; dato che il grafo \(\mathcal{G}\) in questione non è direzionato, la matrice \(A\) è simmetrica, cioè \(a_{ij}=a_{ji}\).
Due archi di \(\mathcal{G}\) si dicono adiacenti se essi hanno un vertice in comune; se gli archi sono individuati dai valori \(a_{ij}\) e \(a_{hk}\), tali archi sono adiacenti se \(i=k \text{ oppure } j=h\).
Un percorso in\(\mathcal{G}\) è un insieme finito di archi adiacenti.
Una componente connessa di \(\mathcal{G}\) è un sottoinsieme di \(V\) i cui elementi sono a due a due collegati da un percorso.
Chiamiamo \(\kappa\) il numero di componenti connesse di \(\mathcal{G}\): evidentemente \(\kappa \in \{1,\ldots ,N\}\); se \(\kappa =1\) il grafo si dice connesso, se \(\kappa =N\) il grafo è totalmente sconnesso (cioè non ci sono archi).
A questo punto, ecco il busillis.
Supponiamo che in \(\mathcal{G}\) non esistano archi "chiusi su loro stessi", ossia che \(a_{ii}=0\).
Formiamo la matrice \(L=(l_{ij})\) nel modo seguente:
\[l_{ij}:=\begin{cases} -a_{ij} &\text{, se } i\neq j \\ \sum_{k=1}^N a_{ik} &\text{, altrimenti.}\end{cases}\]
"Sperimentalmente" è facile constatare che per \(N\) piccoli vale la relazione:
\[\kappa =N-\text{rank }L\; .\]
Mi chiedevo: tale relazione è vera in generale?
E, in caso affermativo, come si dimostra questo fatto?
P.S.: Cosa consigliereste come riferimento base per la Teoria dei Grafi?
Risposte
"gugo82":
P.S.: Cosa consigliereste come riferimento base per la Teoria dei Grafi?
C'è il classico (un po' datato) "Graph Theory" di Harary, però se t'interessa la teoria algebrica dei grafi ci sono libri ad essa appositamente dedicati.
E in uno di questi libri troverai la soluzione al quesito che cerchi: la matrice da te descritta è detta laplaciana (o matrice di Kirchoff, ma immagino questo lo sapevi già) e il tuo è un teorema conosciuto. Lo puoi trovare a pagina 278 del Godsile-Royle. Ti incollo i frammenti significativi:
Nel teorema 8.3.1 $B$ è la matrice d'incidenza di $X$. Un orientazione di $X$ è semplicemente un grafo che ha nella sua matrice d'incidenza non solo $0$ e $1$ ma anche $-1$: si assegna ad ogni lato un vertice testa, che corrisponderà a un $1$ nella matrice di adiacenza, e un vertice coda, $-1$ nella matrice di adiacenza. Inoltre vale $L = DD^T$
P.S.: non sono un esperto di teoria dei grafi (adesso che mi ci fai pensare non lo sono di nulla), tanto meno della parte algebrica; però il libro da cui ti ho incollato quell'estratto è uno di quei libri che Calvino avrebbe etichettato come LibriCheMiPiacerebbeAverLettoMaCheNonHoMaiAvutoNéTempoNéVogliaDiLeggere e in cui ero quasi sicuro di trovare la risposta.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo