Next: Lezione 17
Up: Matematica Discreta (II modulo)
Previous: Lezione 15
Subsections
Definizione 16.1
Sia
![$ G=(V,E)$](img1205.gif)
un grafo e siano
![$ \{V_i\}_{i\in I}$](img1400.gif)
le classi d'equivalenza di
![$ V$](img1206.gif)
rispetto alla relazione di congiungibilità. I grafi
![$ G[V_i]$](img1401.gif)
, indotti da
![$ G$](img3.gif)
sui
![$ V_i$](img1402.gif)
, vengono detti le
componenti connesse di
![$ G$](img3.gif)
.
Proposizione 16.2
Sia
![$ f:G\to G'$](img1299.gif)
un morfismo di grafi e
![$ v,w\in V(G)$](img1403.gif)
.
![$ v$](img1216.gif)
e
![$ w$](img1244.gif)
sono
congiungibili allora anche
![$ f(v)$](img1404.gif)
e
![$ f(w)$](img1405.gif)
lo sono.
Dimostrazione.
Se
è una passeggiata, allora, per
definizione di morfismo, anche
lo è.
Proposizione 16.3
Sia
![$ f:G\to G'$](img1299.gif)
un isomorfismo di grafi e
![$ v,w\in V(G)$](img1403.gif)
.
![$ v$](img1216.gif)
e
![$ w$](img1244.gif)
sono
congiungibili se e solo se lo sono
![$ f(v)$](img1404.gif)
e
![$ f(w)$](img1405.gif)
.
Dimostrazione.
Segue immediatamente dalla proposizione precedente applicata ad
e ad
.
Teorema 16.4
Siano
![$ G$](img3.gif)
e
![$ G'$](img1219.gif)
grafi isomorfi, allora hanno componenti connesse isomorfe.
Più precisamente, se
![$ \{G_i\}_{i\in I}$](img1408.gif)
e
![$ \{G'_j\}_{j\in J}$](img1409.gif)
sono gli
insiemi delle componenti connesse di
![$ G$](img3.gif)
e
![$ G'$](img1219.gif)
rispettivamente, allora
esiste una bigezione
![$ \varphi :I\to J$](img1410.gif)
tale che
![$ G_i\oldcong G'_{\varphi (i)}$](img1411.gif)
.
Dimostrazione.
Siano
le classi d'equivalenza di
(rispetto alla
congiungibilità
) e
quelle di
.
Proviamo innanzitutto che per ogni
esiste un unico
tale che
. Infatti sia
, dato che
è una
partizione di
, si ha che esiste un unico
tale che
. Ma ora
se e solo se
(per definizione di
classe d'equivalenza) e dato che
è un isomorfismo, per la proposizione
precedente, questo equivale a dire che
ovvero che
, ovvero
. D'altra parte se
allora
, quindi, dato che
è un isomorfismo
e quindi
. Questo prova quindi che
.
Per ogni
, indichiamo con
l'unico
con la proprietà
precedente.
Proviamo che per ogni
esiste un unico
tale che
,
ossia
è bigettiva. Dato
, sia
, dato che
è
bigettiva, esiste un unico
tale che
. Esiste allora un unico
tale che
, e questo è quindi l'unico tale che
.
Per concludere proviamo che
induce un isomorfismo tra
e
. Ma chiaramente, dato che
è bigettiva e
, anche
è
bigettiva. Inoltre, se
, per definizione di sottografo
indotto,
se e solo se
e questo, per la proprietà di
isomorfism di
equivale a dire che
e dato che
, questo è a sua volta equivalente a dire che
. E questa è la tesi.
Esercizio 16.1
Si provi che se
![$ G$](img3.gif)
è un grafo e
![$ \{G_i\}_{i\in I}$](img1408.gif)
sono le sue componenti
connesse, allora
![$ E(G)=\bigcup_{i\in I}E(G_i)$](img1440.gif)
.
Soluzione
Esercizio 16.2
Se
![$ G$](img3.gif)
è un grafo finito e
![$ G_1,\dots,G_k$](img1441.gif)
sono le sue componenti connesse,
allora
![$ \sum_{i=1}^k\left\vert V(G_i)\right\vert=\left\vert V(G)\right\vert$](img1442.gif)
e
![$ \sum_{i=1}^k\left\vert E(G_i)\right\vert=\left\vert E(G)\right\vert$](img1443.gif)
.
Soluzione
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$](img3.gif)
è connesso se e solo se per ogni
![$ v$](img1216.gif)
e
![$ w$](img1244.gif)
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$](img3.gif)
è un grafo e
![$ G'$](img1219.gif)
è un sottografo di
![$ G$](img3.gif)
connesso e
che contiene tutti i vertici (i.e.
![$ V(G')=V(G)$](img1444.gif)
), allora anche
![$ G$](img3.gif)
è
connesso.
Soluzione
Definizione 16.8
Sia
![$ G$](img3.gif)
un grafo finito e siano
![$ v_1,\dots,v_n$](img1445.gif)
i sui vertici. Si chiama
matrice di adiacenza di
![$ G$](img3.gif)
la matrice
![$ A_G$](img1446.gif)
, che al posto
![$ i,j$](img1447.gif)
ha
![$ 1$](img567.gif)
se
![$ \{v_i,v_j\}\in E{G}$](img1448.gif)
e ha 0 altrimenti.
Proposizione 16.9
Sia
![$ A$](img10.gif)
la matrice di adiacenza del grafo
![$ G$](img3.gif)
, allora l'elemeto di posto
![$ i,j$](img1447.gif)
della matrice
![$ A^k$](img1449.gif)
è pari al numero di passeggiate lunghe
![$ k$](img1.gif)
dal
vertice
![$ v_i$](img1450.gif)
al vertice
![$ v_j$](img1451.gif)
.
Esercizio 16.4
Si provi che un grafo finito
![$ G$](img3.gif)
ha
![$ 3$](img1452.gif)
-cicli se e solo se la matrice
![$ A_G^3$](img1453.gif)
ha elementi non nulli sulla diagonale.
Soluzione
Esercizio 16.5
Si provi che il numero di
![$ 3$](img1452.gif)
-cicli di un grafo finito
![$ G$](img3.gif)
è pari a
![$ \mathop{\rm tr}\nolimits (A_G^3)/6$](img1454.gif)
.
Soluzione
Next: Lezione 17
Up: Matematica Discreta (II modulo)
Previous: Lezione 15
Domenico Luminati
2004-03-18