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

Componenti connesse di un grafo

Le componenti connesse sono invarianti per isomorfismo

Proposizione 16.1   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.2   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.3   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)}$.

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$.

Esercizio 16.1    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.4   Un grafo si dice connesso se ha una sola componente connessa. Un grafo non connesso si dice sconnesso.

Osservazione 16.5   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.6   Dal teorema 16.3 segue in particolare che se due grafi sono isomorfi, allora o sono entrambi connessi oppure sono entrambi sconnessi.

La matrice di incidenza di un grafo finito

Definizione 16.7   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.8   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.2    Si provi che un grafo finito G ha 3-cicli se e solo se la matrice A_G³ ha elementi non nulli sulla diagonale.
Soluzione

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