Matematica Discreta I Lezione del giorno 7 dicembre 2007 Teoria dei grafi

Matematica Discreta I

Lezione del giorno 7 dicembre 2007 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 se fosse possibile partire da una delle 4 zone di terra, percorrere tutti i 7 ponti una ed una sola volta e tornare al punto di partenza.

Schematizzando il problema, 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 li uniscono) 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:

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

Isola b

Isola d

(dove V

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

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

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

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

ma anche a=

.

Osservazione: nella nostra definizione di grafo, un arco ha sempre due vertici estremi distinti, quindi non sono ammessi i cappi, cioè gli 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

(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é 2 archi sono percorsi ognuno 2 volte)

Notiamo che, nella nostra definizione di grafo, non è detto che la funzione di adiacenza f sia iniettiva, cioè può avvenire che 2 archi diversi abbiano gli stessi vertici estremi (per esempio nel caso del grafo dei ponti, gli archi 1,2 hanno gli stessi estremi a,b). Se la funzione f è iniettiva si dice che il grafo è semplice: in un grafo semplice, comunque presi due vertici distinti, vi è al massimo 1 arco che li ha come estremi (in caso contrario il grafo è detto multiplo).

Un cammino in un grafo:

a

= v

v

, a

= v

v

,….. a

= v

v

è detto ciclico se il primo vertice v

del primo arco coincide con il secondo vertice v

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=

, 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 ?

Per determinare sotto quali condizioni esista in un grafo un cammino ciclico Euleriano, 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 (dati comunque 2 vertici distinti esiste sempre un cammino di lunghezza 1 , cioè un singolo arco, che li unisce, tranne che per i vertici a, c che sono collegati da un cammino di lunghezza 2).

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

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

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

, rappresentiamo schematicamente il cammino nel modo seguente:

a

v

a

v

a

v

………… a

v

a

In tale schema si suppone che siano presenti tutti gli archi del grafo, ognuno 1 sola volta, 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: comunque presi 2 vertici

distinti, li ritroviamo fra i vertici v

,v

,…..v

, quindi esiste un cammino che li unisce (una parte 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 fra 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 arco a

, arriveremo su un vertice v

tale che tutti gli archi che hanno v

come estremo sono stati da noi percorsi.

Schematizzando il cammino fino ad ora costruito:

v

a

v

a

v

v

a

v

………

Affermiamo che si ha necessariamente v

=v

. Se infatti per assurdo fosse v

≠v

, calcoliamo il grado del vertice v

: se k è il numero di volte (tranne l’ultima) che si è incontrato v

nel cammino percorso, il grado di v

sarebbe 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 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

………

Se “tagliamo“ all’altezza del vertice v

(duplicando tale vertice), otteniamo un unico cammino ciclico più lungo di quello costruito all’inizio del procedimento:

………

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