Next: Lezione 17
Up: Matematica Discreta (II modulo)
Previous: Lezione 15
Subsections
Definizione 16.1
Sia

un grafo e siano

le classi d'equivalenza di

rispetto alla relazione di congiungibilità. I grafi
![$ G[V_i]$](img1401.gif)
, indotti da

sui

, vengono detti le
componenti connesse di

.
Proposizione 16.2
Sia

un morfismo di grafi e

.

e

sono
congiungibili allora anche

e

lo sono.
Dimostrazione.
Se
è una passeggiata, allora, per
definizione di morfismo, anche
lo è.
Proposizione 16.3
Sia

un isomorfismo di grafi e

.

e

sono
congiungibili se e solo se lo sono

e

.
Dimostrazione.
Segue immediatamente dalla proposizione precedente applicata ad
e ad
.
Teorema 16.4
Siano

e

grafi isomorfi, allora hanno componenti connesse isomorfe.
Più precisamente, se

e

sono gli
insiemi delle componenti connesse di

e

rispettivamente, allora
esiste una bigezione

tale che

.
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

è un grafo e

sono le sue componenti
connesse, allora

.
Soluzione
Esercizio 16.2
Se

è un grafo finito e

sono le sue componenti connesse,
allora

e

.
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

è connesso se e solo se per ogni

e

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

è un grafo e

è un sottografo di

connesso e
che contiene tutti i vertici (i.e.

), allora anche

è
connesso.
Soluzione
Definizione 16.8
Sia

un grafo finito e siano

i sui vertici. Si chiama
matrice di adiacenza di

la matrice

, che al posto

ha

se

e ha 0 altrimenti.
Proposizione 16.9
Sia

la matrice di adiacenza del grafo

, allora l'elemeto di posto

della matrice

è pari al numero di passeggiate lunghe

dal
vertice

al vertice

.
Esercizio 16.4
Si provi che un grafo finito

ha

-cicli se e solo se la matrice

ha elementi non nulli sulla diagonale.
Soluzione
Esercizio 16.5
Si provi che il numero di

-cicli di un grafo finito

è pari a

.
Soluzione
Next: Lezione 17
Up: Matematica Discreta (II modulo)
Previous: Lezione 15
Domenico Luminati
2004-03-18