Matematica Discreta Lezione del giorno 25 gennaio 2011 Teoria dei grafi

Matematica Discreta

Lezione del giorno 25 gennaio 2011 Teoria dei grafi

L’origine storica della teoria dei grafi si fa risalire al problema dei 7 ponti di Könisberg (Eulero, 1736). La città di Könisberg (a quel tempo in Prussia, oggi in Russia e rinominata Kaliningrad) era attraversata dal fiume Pregel, nel quale vi erano 2 piccole isole; le 4 zone di terraferma (le 2 sponde del fiume e le 2 isole nel fiume) erano collegate da 7 ponti.

Ecco una mappa dell’epoca (dove in verde sono indicati i 7 ponti):

La situazione si può schematizzare come segue:

Sponda a

1 2 6

Fiume Isola 5 Pregel

3 4 7

Sponda c

dove i ponti sono indicati con 1,2,3,4,5,6,7 e le zone di terra (2 isole + 2 sponde) sono indicate con a,b,c,d.

Gli abitanti della città di Könisberg si chiedevano:

Problema: è possibile partire da una delle 4 zone di terra, percorrere tutti i 7 ponti ognuno una ed una sola volta e tornare al punto di partenza ?

Isola b

Isola d

Nel piano si può disegnare geometricamente la situazione, rappresentando le zone di terra a,b,c,d come punti ed i ponti come archi di curva, ognuno dei quali unisce 2 di tali punti:

a 6 1 2

b

5 d

3 4

c 7

Questo è già un primo modello di quello che chiameremo grafo: è una struttura geometrica nel piano composta da punti (detti vertici o nodi) e da archi di curva (detti archi o lati) ognuno dei quali unisce 2 vertici.

Però tale definizione di grafo non è univoca, in quanto dipende dalla scelta delle posizioni dei vertici nel piano e dal modo di tracciare gli archi che li uniscono.

Per esempio potremmo disegnare nel piano il grafo dei ponti di Konisberg in questo altro modo:

1

a 6 d 5 b

7 3

4 c

Una definizione più astratta di grafo, ma più precisa ed univoca, è la seguente:

un grafo è una struttura costituita da 2 insiemi A, V (l’insieme A è detto insieme degli archi o lati del grafo, l’insieme V è detto insieme dei vertici o nodi del grafo), e da una funzione f: A → V

(dove V

indica l’insieme di tutti i sottoinsiemi di V che hanno cardinalità 2) detta funzione di adiacenza. La funzione di adiacenza f associa ad ogni arco aA un insieme f(a)={v,w} di 2 vertici dell’insieme V: in questo caso si dice anche che i vertici v,w sono gli estremi dell’arco a.

Da notare che, in questa definizione così astratta, si prescinde dalla reale natura dei “vertici” e degli

“archi” perché gli insiemi A, V sono insiemi assolutamente astratti.

A priori in un grafo sia l’insieme V dei vertici che l’insieme A degli archi possono essere insiemi infiniti, ma da ora in poi tutti i grafi considerati avranno sempre un numero finito di archi e di vertici.

Una rappresentazione planare di un grafo si ottiene appunto rappresentando ogni vertice con un punto del piano e ogni arco con un arco di curva che unisce i due vertici estremi dell’arco (questa rappresentazione, come già notato, può essere fatta in diversi modi).

Nell’esempio del grafo dei ponti di Konisberg, l’insieme dei vertici è V={a,b,c,d}, l’insieme degli archi è A={1,2,3,4,5,6,7}, e la funzione di adiacenza f: A  V

è definita ponendo:

f(1)={a,b}, f(2)={a,b}, f(3)={b,c}, f(4)={b,c}, f(5)={b,d}, f(6)={a,d}, f(7)={c,d}.

Se in un grafo l’arco a ha come estremi i vertici v,w, indicheremo spesso l’arco a con il simbolo

vw

. Ovviamente, essendo l’arco a associato all’insieme {v,w} dei suoi estremi, l’ordine in cui sono elencati gli stessi estremi non ha alcuna importanza, quindi il simbolo

è equivalente al simbolo

.

Osservazione: nella nostra definizione di grafo, un arco ha sempre due vertici estremi distinti, quindi non sono ammessi i cappi, cioè non sono ammessi archi che uniscono un vertice con sé stesso.

Dati due vertici distinti v,w in un grafo, diremo che v,w sono adiacenti se esiste almeno un arco che ha v,w come estremi.

Nell’esempio del grafo dei ponti, i vertici a,b sono adiacenti, ma i vertici a,c non sono adiacenti.

Poiché nel problema dei ponti si parlava di percorrere i ponti, tale concetto si formalizza nella definizione di cammino.

Un cammino in un grafo è una successione finita di archi del grafo della forma:

a

= v

v

, a

= v

v

,….. a

= v

v

(notare che il secondo estremo di ogni arco coincide con il primo estremo dell’arco seguente, in modo che gli archi siano percorsi di seguito, senza “salti”). Si dice anche che il cammino unisce il vertice v

(primo vertice del primo arco) con il vertice v

(secondo vertice dell’ultimo arco).

Il numero n è detto lunghezza del cammino. Notiamo che nella definizione di cammino, è consentito che un arco sia percorso più volte, quindi il numero n può essere maggiore del numero di archi distinti percorsi nel cammino.

Nel grafo dei ponti, un esempio di cammino di lunghezza n=6 può essere il seguente:

1=

, 2=

, 1=

, 5=

, 5=

, 4=

(la lunghezza è n=6, ma sono in tutto 4 gli archi distinti, perché gli archi 1 e 5 sono percorsi ognuno 2 volte)

Dato un cammino in un grafo:

a

= v

v

, a

= v

v

,….. a

= v

v

tale cammino è detto ciclico se il primo vertice v

del primo arco coincide con il secondo vertice v

dell’ultimo arco (questo corrisponde praticamente a percorrere un cammino tornando al vertice da cui si è partiti).

Nel grafo dei ponti, un esempio di cammino ciclico può essere il seguente:

1=

, 2=

, 6=

, 5=

, 2=

(si parte dal vertice a e si ritorna alla fine del cammino sullo stesso vertice).

Un cammino in un grafo è detto Euleriano se percorre tutti gli archi del grafo ognuno 1 sola volta.

Il problema dei ponti di Könisberg si traduce, nel linguaggio dei grafi, nel seguente quesito: esiste nel grafo dei ponti un cammino Euleriano ciclico ?

Eulero cercò di rispondere ad un quesito più generale: sotto quali condizioni esiste in un grafo un cammino ciclico Euleriano ?

Per rispondere a tali domande, introduciamo il concetto di grado di un vertice e di grafo connesso.

Dato un grafo, il grado di un vertice w è il numero di archi che hanno w come estremo. Se il grado di w è 0 (cioè se nessun arco ha w come estremo) si dice che w è un vertice isolato.

Esempio: nel grafo dei ponti i vertici a, d, c hanno grado 3, il vertice b ha grado 5 e nessun vertice è isolato.

Un grafo è detto connesso, se, comunque dati 2 vertici distinti v, w, esiste sempre almeno un cammino che unisce v e w.

Esempio: il grafo dei ponti è connesso (infatti dati comunque 2 vertici distinti esiste sempre un cammino che li unisce: in particolare i vertici a, c sono uniti da un cammino di lunghezza 2, mentre per ogni altra coppia di vertici, esiste un cammino di lunghezza 1, cioè un singolo arco, che li unisce).

Il seguente grafo con 6 vertici e 5 archi non é connesso:

a b c d x z

perché, per esempio, non esiste nessun cammino che unisce il vertice a con il vertice c.

Il prossimo Teorema (di cui fra poco daremo la dimostrazione) fornisce una condizione necessaria e sufficiente per l’esistenza in un grafo di un cammino ciclico Euleriano.

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.

Osservazione: Possiamo già notare che il grafo dei ponti, pur essendo connesso, non ha tutti i vertici di grado pari, dunque il problema dei ponti di Könisberg ha risposta negativa.

Premessa : Durante le prossime dimostrazioni, 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

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 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 esistente per ipotesi). 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.

Dimostreremo nella prossima lezione l’implicazione inversa ().