bdsarebbe la seguente: a 1 b 2 a 1 b 5 d Siamo ora in grado di dimostrare il Teorema di Eulero.

Matematica Discreta

Lezione del giorno 16 dicembre 2009

Per schematizzare un cammino in un grafo, useremo una rappresentazione “lineare” in cui gli archi del cammino sono disegnati uno di seguito all’altro (eventualmente ripetendo i vertici che il cammino toccasse più volte).

Per esempio, nel grafo dei ponti, una rappresentazione lineare del cammino:

1= ^ab , 2= ^ba , 1= ^ab , 5= ^bd sarebbe la seguente:

a 1 b 2 a 1 b 5 d

Siamo ora in grado di dimostrare il Teorema di Eulero.

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 è la seguente:

v

a

v

a

v

a

v

………… v

a

v

a

In tale rappresentazione si suppone che siano presenti tutti gli archi del grafo, ognuno 1 sola volta (essendo il cammino Euleriano), e poiché non esistono per ipotesi vertici isolati, sono presenti 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 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 costruire un cammino ciclico Euleriano. Partiamo

da un vertice a caso v

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

che

unisce v

con un altro vertice v

. Poiché il grado di v

è >1 (perché per ipotesi tale grado é pari)

possiamo trovare un arco a

(diverso dal primo arco a

percorso) che unisce v

con un vertice v

. A

questo punto l’algoritmo per la costruzione del cammino procede nel modo seguente: ogni volta che

arriviamo su un vertice, se esiste qualche arco che ha estremo in quel vertice e che non è ancora

stato percorso, percorriamo questo arco, allungando il cammino, altrimenti ci fermiamo,

concludendo l’algoritmo. Notiamo che, essendo il numero di archi finito, 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

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 ottenuto un cammino ciclico, schematizzato come segue:

v

=v

v

v

v

………

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

=v

v

v

v

v

………

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

v

………. ………. … (cammino ciclico costruito in precedenza)

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

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 1 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), connesso, e con tutti i vertici che hanno grado pari:

a

1 2 3

b c

5 6 4 d 7

8 9

e 10 f

11 12 g

Seguiamo il procedimento indicato nella dimostrazione del Teorema di Eulero per costruire un

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, ottenendo 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 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 pari:

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