Matematica Discreta Lezione del giorno 16 gennaio 2009 Teoria dei grafi

(1)

Matematica Discreta

Lezione del giorno 16 gennaio 2009 Teoria dei grafi

L’origine storica della teoria dei grafi si fa risalire al problema dei 7 ponti di Könisberg (Eulero, 1736). Il problema posto era relativo al fiume Pregel attraversato da 7 ponti che collegavano 4 zone di terra (2 sponde e 2 isole):

Sponda a

1 2 6

Fiume Isola 5 Pregel

3 4 7 Sponda c

Ponti: 1,2,3,4,5,6,7 Zone di terra: 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 ?

Schematizzando la situazione, si possono rappresentare le zone di terra a,b,c,d come punti nel piano ed i ponti come archi di curva che li uniscono:

a 6 1 2

b

5 d

3 4

C 7

Questo è già un primo modello di quello che chiameremo grafo, ma tale rappresentazione visiva (con punti e archi che uniscono coppie di punti) non è univoca, in quanto dipende dalla scelta delle posizioni dei punti e dal modo di tracciare gli archi di curva che li uniscono.

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

Isola b

Isola d

(2)

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

2

(dove V

2

indica l’insieme di tutti i sottoinsiemi di V che hanno cardinalità 2) detta funzione di adiacenza. Dunque la funzione f associa ad ogni arco aA un insieme f(a)={v,w} di 2 vertici: in questo caso si dice 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.

Una rappresentazione grafica 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.

Nell’esempio del grafo dei ponti, 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

2

è 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, scriveremo anche a=

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 a=

^vw

ma anche a=

^wv

.

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

1

= v

₁

v

₂

, a

2

= v

2

v

3

,….. a

n

= v

_n

v

_n_₁

(in modo 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

1

(primo vertice del primo arco) con il vertice v

n+1

(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=

ab

, 2=

ba

, 1=

ab

, 5=

bd

, 5=

db

, 4=

bc

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

Dato un cammino in un grafo:

a

1

= v

₁

v

₂

, a

2

= v

2

v

3

,….. a

n

= v

_n

v

_n_₁

tale cammino è detto ciclico se il primo vertice v

1

del primo arco coincide con il secondo vertice v

n+1

dell’ultimo arco (ciò 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=

ab

, 2=

ba

, 6=

ad

, 5=

db

, 2=

ba

(3)

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

Nota: da ora in poi tutti i grafi considerati avranno sempre un numero finito di archi e di vertici.

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 ?

Più in 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 (che dimostreremo in seguito) fornisce una condizione necessaria e sufficiente per l’esistenza in un grafo di un cammino ciclico Euleriano.