bd bc

Matematica Discreta

Lezione del giorno 22 novembre 2011

Nell’ultima lezione abbiamo enunciato il seguente Teorema:

Teorema di Eulero (sull’esistenza di cammini ciclici Euleriani).

Sia dato un grafo senza vertici isolati.

Allora:

esiste nel grafo un cammino ciclico Euleriano  il grafo è connesso e tutti i suoi vertici hanno grado pari.

Prima di dare la dimostrazione, facciamo alcune premesse sulla rappresentazione dei cammini in un grafo.

Dato un cammino in un grafo:

a

=

, a

=

,….. a

=

per rappresentarlo useremo spesso la cosiddetta rappresentazione lineare del cammino, nella quale gli archi percorsi a

, a

a

si disegnano di seguito:

v

v

v

v

v

………

a

a

a

Esempio: Nel grafo dei ponti:

a 6 1 2

b

5 d

3 4

c 7

la rappresentazione lineare del seguente cammino di lunghezza 6:

1=

, 2=

, 1=

, 5=

, 5=

, 4=

sarà:

a b a b d b c 1 2 1 5 5 4

Se il cammino è ciclico, nella sua rappresentazione lineare l’ultimo arco avrà come secondo vertice

il vertice iniziale del cammino.

Esempio: Nel grafo dei ponti, la rappresentazione lineare del seguente cammino ciclico:

1=

, 2=

, 6=

, 5=

, 2=

sarà:

a b a d b 1 2 6 5

2

Dimostrazione del Teorema di Eulero (sull’esistenza di cammini ciclici Euleriani):

(): Per ipotesi esiste nel grafo un cammino ciclico Euleriano, che percorre tutti gli archi del grafo, ognuno 1 sola volta, e ritorna al vertice di partenza. Se gli archi percorsi in ordine da tale cammino sono a

, a

, …. , a

, una rappresentazione lineare del cammino è per esempio la seguente:

v

a

v

a

v

a

v

………… v

a

v

a

In tale rappresentazione (per definizione di cammino Euleriano) sono presenti tutti gli archi del grafo, ognuno 1 sola volta, e poiché non esistono per ipotesi vertici isolati, sono presenti certamente anche tutti i vertici del grafo (ognuno eventualmente ripetuto più volte). E’ ovvio allora che il grafo è connesso: infatti, comunque presi 2 vertici distinti, li ritroviamo fra i vertici v

,v

,…..v

(che sono tutti i vertici del grafo), quindi esiste un cammino che li unisce (basta prendere una parte opportuna del cammino ciclico Euleriano). Inoltre, fissato un vertice qualunque v, per calcolare il suo grado basta moltiplicare per 2 il numero di “presenze” del vertice v fra i vertici v

,v

,…,v

(ogni vertice infatti si presenta con una coppia di archi, uno di “ingresso” e uno di “uscita”) quindi il grado di ogni vertice è pari.

(): Costruiamo un algoritmo che ci permetta di trovare un cammino ciclico Euleriano. Partiamo da un vertice a piacere v

Poiché non esistono vertici isolati, possiamo trovare qualche arco a

che unisce v

con un altro vertice v

. A questo punto l’algoritmo per la costruzione del cammino procede nel modo seguente: ogni volta che nel nostro cammino arriviamo su un vertice w

- se esistono archi che hanno estremo in tale vertice w e che non è ancora stato percorso, percorriamo uno di questi archi (scelto a piacere), allungando il cammino

- se tutti gli archi che hanno estremo in quel vertice sono stati da noi già percorsi, ci fermiamo, concludendo l’algoritmo.

Notiamo che, essendo il numero di archi finito e poiché percorriamo archi sempre diversi, certamente dopo un numero finito di passi l’algoritmo avrà termine, quindi, attraverso un ultimo arco a

, arriveremo su un vertice v

tale che tutti gli archi che hanno v

come estremo sono stati già da noi percorsi, e questo pone termine alla nostra procedura.

Una rappresentazione lineare del cammino fino ad ora costruito è la seguente:

v

a

v

a

v

a

a

v

a

v

……….

Affermiamo che si ha necessariamente v

=v

. Se infatti per assurdo fosse v

≠v

, potremmo calcolare il grado del vertice v

nel modo seguente: se k è il numero di volte (tranne l’ultima) che si è incontrato v

nel cammino percorso, il grado di v

é la somma di 2k più 1 (2 archi per ogni coppia di archi ingresso-uscita più 1 per l’ultimo arco finale di solo ingresso), quindi il grado di v

sarebbe dispari, in contraddizione con una delle ipotesi. Quindi è vero che v

= v

, e abbiamo costruito con la nostra procedura un cammino ciclico, schematizzato come segue:

v

a

v

a

v

a

a

v

……….

a

In tale cammino, per costruzione, ogni arco è stato percorso 1 sola volta, ma non è detto che siano stati percorsi tutti gli archi del grafo.

Se in tale cammino sono presenti tutti gli archi del grafo, abbiamo costruito il cammino ciclico Euleriano cercato e ottenuto la tesi.

Supponiamo quindi che invece esista nel grafo qualche arco ancora non percorso nel cammino costruito. Allora certamente, essendo il grafo connesso, qualcuno di questi archi non percorsi avrà uno degli estremi coincidente con uno dei vertici v

del cammino ciclico già costruito:

(arco non ancora percorso)

v

a

v

a

v

a

v

a

v

……… ………..

a

Partendo allora dall’arco (non percorso) che ha come estremo v

, e ripetendo il ragionamento precedente, costruiremo un nuovo cammino ciclico che ha inizio e fine in v

, sempre percorrendo nuovi archi non ancora percorsi:

………

(nuovo cammino ciclico)

v

v

v

v

v

………. ………. ………….

Se “tagliamo“ all’altezza del vertice v

(duplicando tale vertice), otteniamo un unico cammino

ciclico di lunghezza maggiore di quello costruito all’inizio del procedimento

………

(cammino ciclico ottenuto dai 2 precedenti)

v

v

v

v

v

v

……. ………

Se in tale cammino sono presenti tutti gli archi del grafo, abbiamo costruito il cammino ciclico Euleriano cercato, altrimenti iteriamo il procedimento, ottenendo un cammino ciclico di lunghezza ancora maggiore. Poiché il numero di archi del grafo è finito, dopo un numero finito di iterazioni avremo costruito il cammino ciclico Euleriano cercato, che percorre tutti gli archi del grafo, ognuno una sola volta.

Esempio: il grafo dei ponti di Könisberg, pur essendo connesso, non ha tutti i vertici di grado pari, quindi in tale grafo non esiste un cammino ciclico Euleriano, e il quesito posto dagli abitanti ha riposta negativa.

Esempio: consideriamo il seguente grafo (il cosiddetto “grafo della busta con doppia apertura”) con 7 vertici a,b,c,d,e,f,g e 12 archi (numerati da 1 a 12).

a

1 2 3

b c

5 6 4 d 7

8 9

e 10 f

11 12 g

Notiamo che il grafo è connesso e tutti i vertici hanno grado pari (sono tutti di grado 4 tranne a,g di grado 2): per il Teorema di Eulero esiste in tale grafo un cammino ciclico Euleriano.

Seguiamo l’algoritmo indicato nella dimostrazione del Teorema di Eulero per costruire un tale cammino ciclico Euleriano.

Partiamo da un vertice, per esempio il vertice a, e cominciamo a costruire un cammino che parte da a e percorre ogni volta archi non ancora percorsi, fin quando é possibile iterare il procedimento; per esempio potremmo costruire il seguente cammino:

a 2 c 6 d 8 e 4 b

1

Come previsto dalla dimostrazione, arrivati ad un vertice da cui non si può proseguire (il vertice a) 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 3 che ha il vertice b come estremo) e partendo da tale arco costruiamo, con lo stesso metodo, un secondo cammino ciclico:

a 2 c 6 d 8 e 4 b 3 c 7 f 10 e 11 g 12 f 9 d

1 5

Ora “tagliamo” all’altezza del vertice b (duplicandolo), e otteniamo un unico cammino ciclico:

a 2 c 6 d 8 e 4 b 3 c 7 f 10 e 11 g 12 f 9 d

1 b 5

Tale cammino tocca tutti i 9 archi del grafo, ognuno 1 sola volta, quindi é il cammino ciclico Euleriano 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, con rappresentazione lineare seguente:

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 concludendo 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 (il cosiddetto “grafo della busta con singola apertura”) con 6 vertici a,b,c,d,e,f, e 10 archi (numerati da 1 a 10). Esso è connesso, e tutti i vertici hanno grado pari, tranne i vertici e,f che hanno grado dispari:

a

1 2 3

b c

5 6 4 d 7

8 9

e 10 f

Per le considerazioni precedenti, esisterà nel grafo un cammino Euleriano non ciclico, che avrà estremi nei due vertici e,f (un esempio di tale cammino si ha considerando gli archi 4,1,2,3,5,6,7,9,8,10).