Lezione 16 (9 maggio 2001 h. 10.30-11.30)

Componenti connesse di un grafo

Definizione 16.1   Sia $G=(V,E)$ un grafo e siano $\{V_i\}_{i\in I}$ le classi d'equivalenza di $V$ rispetto alla relazione di congiungibilità. I grafi $G[V_i]$, indotti da $G$ sui $V_i$, vengono detti le componenti connesse di $G$.

Le componenti connesse sono invarianti per isomorfismo

Proposizione 16.2   Sia $f:G\to G'$ un morfismo di grafi e $v,w\in V(G)$. $v$ e $w$ sono congiungibili allora anche $f(v)$ e $f(w)$ lo sono.

Dimostrazione.  Se $(v=v_0,v_1,\dots,v_n=w)$ è una passeggiata, allora, per definizione di morfismo, anche $(f(v)=f(v_0),f(v_1),\dots,f(v_n)=f(w))$ lo è.     $\square$

Proposizione 16.3   Sia $f:G\to G'$ un isomorfismo di grafi e $v,w\in V(G)$. $v$ e $w$ sono congiungibili se e solo se lo sono $f(v)$ e $f(w)$.

Dimostrazione.  Segue immediatamente dalla proposizione precedente applicata ad $f$ e ad $f^{-1}$.     $\square$

Teorema 16.4   Siano $G$ e $G'$ grafi isomorfi, allora hanno componenti connesse isomorfe. Più precisamente, se $\{G_i\}_{i\in I}$ e $\{G'_j\}_{j\in J}$ sono gli insiemi delle componenti connesse di $G$ e $G'$ rispettivamente, allora esiste una bigezione $\varphi :I\to J$ tale che $G_i\oldcong G'_{\varphi (i)}$.

Dimostrazione.  Siano $\{V_i\}_{i\in I}$ le classi d'equivalenza di $V(G)$ (rispetto alla congiungibilità $\sim$) e $\{V_j'\}_{j\in J}$ quelle di $V(G')$.

Proviamo innanzitutto che per ogni $i\in I$ esiste un unico $j\in J$ tale che $f(V_i)=V'_j$. Infatti sia $v\in V_i$, dato che $\{V_j'\}_{j\in J}$ è una partizione di $V(G')$, si ha che esiste un unico $j\in J$ tale che $f(v)\in V'_j$. Ma ora $u\in V_i$ se e solo se $u\sim v$ (per definizione di classe d'equivalenza) e dato che $f$ è un isomorfismo, per la proposizione precedente, questo equivale a dire che $f(u) \sim f(v)$ ovvero che $f(u)\in V'_j$, ovvero $f(V_i)\subseteq V'_j$. D'altra parte se $w\in V'_j$ allora $w\sim f(v)$, quindi, dato che $f$ è un isomorfismo $f^{-1}(w)\sim v$ e quindi $f^{-1}(w)\in V_i$. Questo prova quindi che $V_j'=f(V_i)$.

Per ogni $i\in I$, indichiamo con $\varphi (i)$ l'unico $j$ con la proprietà precedente.

Proviamo che per ogni $j\in J$ esiste un unico $i\in I$ tale che $\varphi (i)=j$, ossia $\varphi :I\to J$ è bigettiva. Dato $J$, sia $w\in V_j$, dato che $f$ è bigettiva, esiste un unico $v\in V(G)$ tale che $f(v)=w$. Esiste allora un unico $i\in I$ tale che $v\in V_i$, e questo è quindi l'unico tale che $\varphi (i)=j$.

Per concludere proviamo che $f$ induce un isomorfismo tra $G[V_i]$ e $G'[V'_\varphi (i)]$. Ma chiaramente, dato che $f$ è bigettiva e $f(V_i)=V'_{\varphi (i)}$, anche $\setbox\restrictbox=\hbox{$\hbox{$f$}_{V_i}$}\setbox0\hbox{$f$} {{f} \vrule wi... ..., \hbox{\vrule depth\dp0 height \ht0 width0pt}_{V_i}} :V_i \to V'_{\varphi (i)}$ è bigettiva. Inoltre, se $u,v\in V_i$, per definizione di sottografo indotto, $\{u,v\}\in E(G[V_i])$ se e solo se $\{u,v\}\in E(G)$ e questo, per la proprietà di isomorfism di $f$ equivale a dire che $\{f(u),f(v)\}\in E(G')$ e dato che $f(u),f(v)\in V'_{\varphi (i)}$, questo è a sua volta equivalente a dire che $\{f(u),f(v)\}\in E(G'[V'_{\varphi (i)}])$. E questa è la tesi.     $\square$

Esercizio 16.1   Si provi che se $G$ è un grafo e $\{G_i\}_{i\in I}$ sono le sue componenti connesse, allora $E(G)=\bigcup_{i\in I}E(G_i)$.
Soluzione

Esercizio 16.2   Se $G$ è un grafo finito e $G_1,\dots,G_k$ sono le sue componenti connesse, allora $\sum_{i=1}^k\left\vert V(G_i)\right\vert=\left\vert V(G)\right\vert$ e $\sum_{i=1}^k\left\vert E(G_i)\right\vert=\left\vert E(G)\right\vert$.
Soluzione

Grafi connessi

Definizione 16.5   Un grafo si dice connesso se ha una sola componente connessa. Un grafo non connesso si dice sconnesso.

Osservazione 16.6   Un grafo $G$ è connesso se e solo se per ogni $v,w\in V(G)$ $v$ e $w$ sono congiungibili da un cammino (risp. da una passeggiata).

Osservazione 16.7   Dal teorema 16.4 segue in particolare che se due grafi sono isomorfi, allora o sono entrambi connessi oppure sono entrambi sconnessi.

Esercizio 16.3   Si provi che se $G$ è un grafo e $G'$ è un sottografo di $G$ connesso e che contiene tutti i vertici (i.e. $V(G')=V(G)$), allora anche $G$ è connesso.
Soluzione

La matrice di incidenza di un grafo finito

Definizione 16.8   Sia $G$ un grafo finito e siano $v_1,\dots,v_n$ i sui vertici. Si chiama matrice di incidenza di $G$ la matrice $A_G$, che al posto $i,j$ ha $1$ se $\{v_i,v_j\}\in E{G}$ e ha $0$ altrimenti.

Proposizione 16.9   Sia $A$ la matrice di incidenza del grafo $G$, allora l'elemeto di posto $i,j$ della matrice $A^k$ è pari al numero di passeggiate lunghe $k$ dal vertice $v_i$ al vertice $v_j$.

Esercizio 16.4   Si provi che un grafo finito $G$ ha $3$-cicli se e solo se la matrice $A_G^3$ ha elementi non nulli sulla diagonale.
Soluzione

Esercizio 16.5   Si provi che il numero di $3$-cicli di un grafo finito $G$ è pari a $\mathop{\rm tr}\nolimits (A_G^3)/6$.
Soluzione