Matematica Discreta Lezione del giorno 1 febbraio 2011

Matematica Discreta

Lezione del giorno 1 febbraio 2011

Completiamo la dimostrazione del Teorema di Eulero sull’esistenza in un grafo di cammini Euleriano ciclici.

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

. 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 uno di questi archi (con scelta casuale), 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

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

=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 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), 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 (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).

Componenti connesse di un grafo.

Dato un grafo, definiamo componente connessa un grafo (contenuto in quello originario) ottenuto considerando come vertici tutti quelli del grafo che sono fra loro uniti da qualche cammino, e come archi tutti quelli del grafo che uniscono tali vertici.

Esempio: dato il seguente grafo con 9 vertici a,b,c,d,e,f,g,h,i, e 7 archi 1,2,3,4,5,6,7:

1 2 3

a b c d e f 4 5 6 7

g h i

esso ha 3 componenti connesse 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 3,5,6,7).

E’ ovvio che ognuna delle componenti connesse di un grafo, considerata come grafo a sé stante, è un grafo connesso, anche se il grafo originario non è connesso: infatti per costruzione fra 2 vertici qualunque della stessa componente connessa esiste sempre almeno un cammino.

E’ ovvio anche che un grafo connesso ha 1 sola componente connessa, coincidente con l’intero grafo.

Infine notiamo che v,w sono vertici del grafo in componenti connesse diverse allora non esiste un cammino che li unisce (altrimenti apparterrebbero alla stessa componente) e in particolare non esiste un arco che ha v,w come estremi (un arco è un cammino di lunghezza 1) dunque v,w non sono adiacenti.

Colorazione di una mappa geografica e 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

a b c

d e f

d e f

E’ bene mettere in evidenza che con tale procedimento, al variare delle diverse mappe geografiche, non si ottengono tutti i possibili grafi, ma solo grafi con proprietà particolari (detti “grafi planari”).

Dal problema della colorazione delle mappe nasce in modo naturale la definizione di colorazione di un grafo.

Dato un grafo qualunque (non necessariamente un grafo associato ad una mappa geografica), se V è l’insieme dei vertici del grafo e se C è un insieme astratto, una colorazione del grafo con colori in C è una funzione f: V  C che associa ad ogni vertice del grafo un elemento dell’insieme (quindi un “colore”) tale che a vertici adiacenti (cioè collegati da un arco) siano associati colori diversi.

Il numero cromatico di un grafo è il minimo numero di colori che servono per ottenere una colorazione del grafo, quindi è la minima cardinalità di un insieme C tale che esista una colorazione del grafo con colori in C.

Con questo linguaggio il “teorema dei 4 colori” afferma che: il numero cromatico del grafo associato ad una qualunque carta geografica è  4.

Esempio: nel seguente grafo con 5 vertici e

a b

c d

si può ottenere per esempio una colorazione con 5 colori (con C={1,2,3,4,5}) associando al vertice a il colore 1, al vertice b il colore 2, al vertice c il colore 3, al vertice d il colore 4, al vertice e il colore 5.

Ma si può ottenere anche una colorazione con 4 colori (con C={1,2,3,4}) associando al vertice a il colore 1, al vertice b il colore 2, al vertice c il colore 3, al vertice d il colore 4, al vertice e il colore 2.

Possiamo ancora risparmiare sul numero di colori, ed ottenere una colorazione con 3 colori (con C={1,2,3}) associando al vertice a il colore 1, al vertice b il colore 2, al vertice c il colore 3, al vertice d il colore 1, al vertice e il colore 2.

D’altra parte è impossibile ottenere una colorazione con 2 colori perché i 3 vertici b,c,d (essendo a 2

a 2 adiacenti fra loro) necessitano di 3 colori differenti. Dunque si conclude che il numero

cromatico di questo grafo è 3.