Matematica Discreta I
Lezione del giorno 10 dicembre 2007
Esempio: consideriamo il seguente grafo con 6 vertici a,b,c,d,e,f, e 9 archi (numerati da 1 a 9), connesso, e con tutti i vertici che hanno grado pari:
1
2
a 3 b
c d 4 5 6 7 8
e 9 f
Seguiamo il procedimento indicato nella dimostrazione del Teorema di Eulero per costruire un cammino ciclico Euleriano.
Partiamo da un vertice, per esempio il vertice b, e cominciamo a costruire un cammino che parte da b e percorre ogni volta archi non ancora percorsi, fin quando é possibile iterare il procedimento; per esempio potremmo costruire il seguente cammino:
b 6 f 9 e 4 a
3
Come previsto dalla dimostrazione, arrivati ad un vertice da cui non si può proseguire (il vertice b) siamo tornati al vertice di partenza, ottenendo un cammino ciclico.
Esistono però archi non ancora percorsi: prendiamo uno che ha come estremo uno dei vertici toccati dal cammino costruito (per esempio l’arco 1 che ha il vertice a come estremo) e partendo da tale arco costruiamo, con lo stesso metodo, un secondo cammino ciclico:
b 6 f 9 e 4 a 1 c 2 d 8 c 7 f
3 5
Ora “tagliamo” all’altezza del vertice a, ottenendo un unico cammino ciclico:
b 6 f 9 e 4 a 1 c 2 d 8 c 7 f
a
3 5
Tale cammino tocca tutti i 9 archi del grafo, ognuno 1 sola volta, quindi é quello cercato.
Problema: Qual è la condizione per l’esistenza in un grafo di un cammino Euleriano non ciclico ? Supponiamo che nel grafo esista un tale cammino Euleriano non ciclico, schematizzato come segue:
v ……… w
(dove i vertici estremi v,w sono diversi, ma sono percorsi nel cammino tutti gli archi del grafo, ognuno 1 sola volta). Costruiamo un nuovo grafo ottenuto dal precedente aggiungendo un arco che colleghi i vertici v,w: otteniamo un grafo in cui esiste un cammino ciclico Euleriano, e possiamo applicare il Teorema di Eulero ottenendo in particolare che questo nuovo grafo è connesso e tutti i suoi vertici hanno grado pari. E’ ovvio che (togliendo l’arco supplementare fra v e w) e tornando al grafo originario, quest’ultimo resta connesso, ma tutti i suoi vertici hanno grado pari, tranne i vertici v,w che hanno grado dispari (perché il loro grado, con l’abolizione dell’arco, diminuisce di 1).
Abbiamo quindi in pratica dimostrato che la condizione per l’esistenza di un cammino Euleriano non ciclico in un grafo è la seguente: il grafo é connesso e tutti i vertici hanno grado pari, tranne esattamente 2 vertici che hanno grado dispari (che sono proprio i vertici estremi del cammino).
Da notare che nel grafo dei ponti i 4 vertici hanno tutti grado dispari, dunque non esiste in tale grafo un cammino Euleriano non ciclico (e neanche uno ciclico).
Esempio: consideriamo il seguente grafo con 6 vertici a,b,c,d,e,f, e 8 archi (numerati da 1 a 8), connesso, e con tutti i vertici che hanno grado pari, tranne i vertici e, f che hanno grado dispari:
1
2
a 3 b
c d 4 5 6 7 8
e f
Esisterà allora un cammino Euleriano non ciclico, che avrà estremi esattamente nei vertici e,f.
Un esempio di tale cammino si può avere considerando gli archi:
4, 1, 2, 8, 7 ,5 ,3, 6 .
Componenti connesse di un grafo
Anche se un grafo non è connesso, esso può essere suddiviso in grafi connessi più piccoli, come vedremo definendo le componenti connesse di un grafo.
Prima, fissato un vertice w del grafo, definiamo per convenzione il cammino vuoto (di lunghezza zero) che unisce il vertice w con sé stesso senza percorrere alcun arco.
Sia dato un grafo qualunque. Definiamo una relazione R nell’insieme dei vertici V mediante il predicato P(x,y)=”esiste almeno un cammino da x a y”.
Si verifica facilmente che tale relazione è di equivalenza.
La proprietà riflessiva deriva dall’esistenza dei cammini vuoti da un vertice in sé stesso.
La simmetrica deriva dalla possibilità di percorrere un cammino da v a w in senso inverso, ottenendo un cammino da w a v.
Infine la transitiva dall’osservazione che percorrendo di seguito 2 cammini da v a w e da w a z, si ottiene un cammino da v a z.
Ogni classe di equivalenza della relazione R è detta componente connessa del grafo.
Essendo classi di equivalenza, le componenti connesse di un grafo formano una partizione dell’insieme dei vertici V.
Dati 2 vertici v,w, e ricordando un teorema sulle classi di equivalenza, si ha [v]=[w] vRw, dunque fra vertici della stessa componente connessa esiste sempre almeno un cammino, mentre fra vertici di componenti diverse non esiste nessun cammino (e quindi anche nessun arco). In particolare ogni componente, considerata come grafo a sé stante (nel senso che si considerano i suoi vertici e solo gli archi che li collegano) è un grafo connesso.
Ovviamente un grafo connesso ha 1 sola componente connessa, coincidente con l’intero grafo.
Esempio: il grafo seguente ha 3 componenti connesse:
1 2 3
a b c d e f 4 5 6 7 g h i
formate rispettivamente dai vertici {a,b} (e dall’arco 1), dai vertici {c,d,g} (e dagli archi 2,4), dai vertici {e,f,h,i} (e dagli archi 2,5,6,7).
