bdsarebbe la seguente: a 1 b 2 a 1 b 5 d

Matematica Discreta

Lezione del giorno 19 gennaio 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=

, 2=

, 1=

, 5=

sarebbe la seguente:

a 1 b 2 a 1 b 5 d

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 vertici hanno grado pari.

Dimostrazione:

(): 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:

Affermiamo che si ha necessariamente v

=v

. Se infatti per assurdo fosse v

≠v

, calcoliamo 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 più lungo 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 ancora più lungo. 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 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.

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, 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 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 . .Colorazione di un grafo

Nell’800 fu posto il seguente problema: qual è il minimo numero di colori necessario per colorare le regioni di una qualunque mappa geografica, con la condizione che regioni confinanti abbiano colori diversi ?

Tale problema fu risolto nel 1977 da Appel e Haken, con la dimostrazione del “teorema dei 4 colori”, il quale afferma che 4 colori bastano per qualunque mappa geografica.

Si può interpretare tale problema nel linguaggio della teoria dei grafi: infatti a una mappa geografica si può associare un grafo in cui ogni vertice rappresenta una regione, e due vertici sono collegati da un arco se le regioni corrispondenti sono confinanti.

Per esempio alla seguente mappa geografica con 6 regioni:

si può associare il seguente grafo con 6 vertici:

a b c

d e f a b c

d e f