Un grafo è una struttura costituita da 2 insiemi:

(1)

Matematica Discreta

Lezione del giorno 16 novembre 2011

Nella lezione precedente abbiamo dato una definizione formale del concetto di grafo.

Un grafo è una struttura costituita da 2 insiemi:

- l’insieme A (detto insieme degli archi o spigoli 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)

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.

La funzione f: A → V

2

è detta funzione di adiacenza del grafo.

La funzione di adiacenza in pratica associa ad ogni arco aA un insieme f(a)={v,w} di 2 vertici distinti dell’insieme V: tali vertici v,w sono detti estremi dell’arco a.

Poiché la definizione di grafo è precisa ma molto astratta, abbiamo anche definito la rappresentazione piana di un grafo: essa si ottiene 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).

Quando daremo esempi di grafi, per motivi pratici preferiremo spesso usare una loro rappresentazione piana (anche se non è univoca) e non la loro definizione “formale”.

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 (mediante la funzione di adiacenza) all’insieme {v,w}

dei suoi estremi, l’ordine in cui sono elencati gli stessi estremi non ha alcuna importanza, quindi il simbolo

^vw

è equivalente al simbolo

^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 hanno estremi coincidenti.

Poiché nel problema dei ponti si parlava di “percorrere” i ponti, tale concetto si formalizza nella definizione “di cammino” in un grafo.

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

a

1

=

v1v2

, a

2

=

v2v3

,….. a

n

=

vnvn_1

(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

1

(primo vertice del primo arco) con il vertice v

n+1

(secondo vertice dell’ultimo arco).

Il numero n degli archi del cammino è detto lunghezza del cammino (notiamo che il numero di

vertici “toccati” dal cammino di lunghezza n è uguale ad (n+1)). Notiamo anche 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.

(2)

Esempio: Nel grafo dei ponti:

a 6 1 2

b

5 d

3 4

c 7

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é gli archi 1 e 5 sono percorsi ognuno 2 volte)

Dato un cammino in un grafo:

a

1

=

v1v2

, a

2

=

v2v3

,….. a

n

=

vnvn_1

tale cammino è detto ciclico se il primo vertice v

1

del primo arco coincide con il secondo vertice v

n+1

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

Esempio: Nel grafo dei ponti un esempio di cammino ciclico di lunghezza n=4 può essere il seguente:

1=

^ab

, 3= bc , 4= cb , 2= ba

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

(3)

per ogni altra coppia di vertici, esiste un cammino di lunghezza 1, cioè un singolo arco, che li unisce).

Invece il seguente grafo con 6 vertici {a,b,c,d,x,z} e con 5 archi {1,2,3,4,5} non é connesso:

1 5 a b c d 2 3 4

x z

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

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