ab vw

Matematica Discreta

Lezione del giorno 26 gennaio 2009 Grafi orientati

Nei grafi fino ad ora considerati, gli archi non hanno un “verso” di percorrenza: tali grafi sono anche detti grafi non orientati.. Daremo ora la definizione di una categoria differente di grafi, i cosiddetti grafi orientati, in cui invece gli archi che uniscono i vertici sono “orientati”, quindi hanno un verso di percorrenza.

Formalmente un grafo orientato è una struttura formata da 2 insiemi: V (detto insieme dei vertici), A (detto insieme degli archi), e da una funzione (detta di adiacenza) f: A  VxV che associa ad ogni arco aA una coppia ordinata di vertici (v,w) appartenente al prodotto cartesiano VxV.

Se l’arco aA è associato da f alla coppia di vertici (v,w)VxV, si dice che v è la coda dell’arco a, e w è la testa dell’arco a; si dice anche che l’arco a va dal vertice v al vertice w, e che v,w sono gli estremi dell’arco (si distinguono il primo estremo v e il secondo estremo w).

Notiamo che nella definizione di grafo orientato è consentito che ad un arco sia associata una coppia ordinata (v,v) di 2 vertici coincidenti, nel qual caso l’arco è un cappio, in cui coda e testa coincidono (ricordiamo che nella nostra definizione di grafo non orientato ad ogni arco è associato un insieme {v,w} di 2 vertici distinti, dunque i cappi non sono consentiti).

La rappresentazione di un grafo orientato nel piano si ottiene rappresentando ogni vertice con un punto del piano e ogni arco con un arco orientato (freccia) che va dalla coda verso la testa dell’arco (tale rappresentazione non è univoca, perché dipende dalle scelte delle posizioni dei punti che rappresentano i vertici e dal modo in cui si tracciano gli archi).

Per esempio, dato il grafo orientato con insieme dei vertici V={a,b,c,d}, insieme degli archi A={1,2,3,4,5,6}, funzione di adiacenza f definita da f(1)=(a,a), f(2)=(a,b), f(3)=(b,c), f(4)=(c,b), f(5)=(c,d), f(6)=(d,d), una sua possibile rappresentazione nel piano é.

1 6

a d 2 3 5

b c

4

Se, in un grafo orientato, l’arco a ha come primo estremo il vertice v e come secondo estremo il vertice w, scriveremo anche a=

vw

.

Nel grafo precedente si ha 1=

^aa

, 2=

ab

etc….

Anche nei grafi orientati ci limiteremo a studiare il caso di grafi in cui sia l’insieme V dei vertici che l’insieme A degli archi sono insiemi finiti.

Dati due vertici distinti v,w in un grafo orientato, diremo che v è adiacente a w se esiste almeno un arco da v a w (ossia un arco che v come coda , w come testa). Al contrario che nel caso dei grafi non orientati, la relazione di adiacenza fra vertici non sempre soddisfa la proprietà simmetrica.

Nel grafo dell’esempio precedente il vertice a è adiacente al vertice b, ma il vertice b non è adiacente al vertice a.

Un cammino in un grafo orientato è una successione di n archi della forma:

a

1

=

v₁v₂

, a

2

=

v2v3

, a

3

=

v3v4

,……., a

n

=

vnvn_1

(quindi la testa di ogni arco coincide con la coda dell’arco successivo): in pratica la definizione è uguale a quella data per i grafi non orientati, ma con il rispetto del verso di percorrenza degli archi.

Si dice anche che il cammino va dal vertice v

1

(vertice di partenza) al vertice v

n+1

(vertice di arrivo).

Il numero n di archi percorsi nel cammino è detto lunghezza del cammino.

Nel grafo precedente un esempio di cammino di lunghezza 6 dal vertice a al vertice d è:

1=

^aa

, 2=

ab

, 3=

bc

, 4=

cb

, 3=

bc

, 5=

cd

Cammini Hamiltoniani

I cammini Hamiltoniani nei grafi (orientati o non orientati) sono un concetto speculare di quello di cammino Euleriano.

L’origine storica del concetto di cammino Hamiltoniano si fa risalire al matematico Hamilton che propose un gioco in cui, dato un dodecaedro (solido con 12 facce pentagonali) si doveva partire da uno dei vertici e percorrere alcuni spigoli toccando tutti i vertici ognuno una sola volta.

Rappresentando il dodecaedro in 2 dimensioni (nel piano), una possibile soluzione era:

Interpretando nella teoria dei grafi tale problema si arriva alla seguente definizione: dato un qualunque grafo (orientato o no) un cammino Hamiltoniano è un cammino che tocca tutti i vertici del grafo, ognuno una sola volta (notare che un cammino Hamiltoniano percorre certamente archi tutti diversi fra loro, ma non è detto che percorra tutti gli archi del grafo, quindi non è detto che sia un cammino Euleriano).

Fino ad ora i matematici non sono riusciti a trovare per i cammini Hamiltoniani l’analogo del Teorema di Eulero per i cammini Euleriani, quindi non è ancora nota una condizione necessaria e sufficiente per l’esistenza di un cammino Hamiltoniano in un grafo.

Ma si può essere certi dell’esistenza di un cammino Hamiltoniano in certe categorie particolari di

grafi, per esempio nei grafi completi.

Un grafo (orientato o non orientato) è detto completo se, comunque dati 2 vertici distinti v, w, esiste sempre almeno un arco che ha v,w come estremi (dunque, nel caso orientato, se esiste almeno un arco dal vertice v al vertice w oppure un arco dal vertice w al vertice v).

Esempio: il seguente grafo orientato con 4 vertici è completo a b

c d

Teorema. In un grafo completo esiste sempre almeno un cammino Hamiltoniano.

Dimostrazione:

Nel caso non orientato è banale: se v

1

, v

2

,…., v

n

sono i vertici distinti del grafo, per ipotesi esiste un arco a

1

che ha v

1

,v

2

come estremi, esiste un arco a

2

che ha v

2

,v

3

come estremi, etc.., esiste un arco a

n- 1

che ha v

n-1

,v

n

come estremi, egli archi a

1

, a

2

,…., a

n-1

formano un cammino Hamiltoniano.

Nel caso orientato: scegliamo a piacere due vertici distinti v

1

, v

2

: essendo il grafo completo, esiste almeno un arco da v

1

a v

2

o un arco da v

2

a v

1

. Supponiamo per esempio che esista un arco da v

1

a v

2

v

1

v

2

Se il numero totale dei vertici è 2, abbiamo già costruito un cammino Hamiltoniano, che passa per tutti i vertici, ognuno una sola volta.

Poniamoci quindi nel caso in cui il numero dei vertici sia >2.

Illustreremo un procedimento con cui, supponendo di avere già costruito un cammino che passi per k vertici distinti, riusciamo sempre, se esiste un ulteriore vertice nel grafo, ad inserirlo nel cammino, costruendone uno più lungo. Applicando tale procedimento più volte, potremo, da un cammino che passa per 2 vertici distinti, costruirne uno che passa per 3 vertici distinti; da questo potremo costruirne uno che passa per 4 vertici distinti, finché otterremo un cammino che passa per tutti i vertici del grafo, ognuno una sola volta, ossia un cammino Hamiltoniano.

Supponiamo quindi di avere già costruito un cammino che passi per k vertici distinti:

v

1

v

2

v

3

………….v

k-1

v

k

Sia dato un ulteriore vertice v

k+1

, distinto dai k vertici già toccati: vogliamo inserire tale vertice nel cammino.

Confrontiamo v

k+1

con v

1

: essendo il grafo completo, esisterà un arco da v

k+1

a v

1

o un arco da v

1

a v

k+1

.

Nel caso esista un arco da v

k+1

a v

1

, possiamo inserire il vertice v

k+1

nel cammino in prima posizione, sfruttando appunto tale arco:

v

k+1

v

1

v

2

………….v

k-1

v

k

Poniamo invece il caso che esista un arco da v

1

a v

k+1

:

v

k+1

v

1

v

2

v

3

………….v

k-1

v

k

In questo caso confrontiamo v

k+1

con v

2

: essendo il grafo completo, esisterà un arco da v

k+1

a v

2

o un arco da v

2

a v

k+1

.

Nel caso esista un arco da v

k+1

a v

2

, possiamo inserire il vertice v

k+1

nel cammino in seconda posizione, sfruttando appunto tale arco, e cancellando l’arco da v

1

a

v

2

del cammino iniziale:

v

k+1

v

1

v

2

v

3

………….v

k-1

v

k

Poniamo invece il caso che esista un arco da v

2

a v

k+1

: v

k+1

v

1

v

2

v

3

………….v

k-1

v

k

In questo caso confrontiamo v

k+1

con v

3

etc. etc.

Il procedimento può continuare: se non riusciamo mai ad inserire il vertice v

k+1

nel cammino, alla fine avremo il caso di un arco da v

k

a v

k+1

, e in tale caso potremo inserire v

k+1

in ultima posizione, sfruttando appunto tale arco:

v

1

v

2

v

3

………….v

k-1

v

k

v

k+1

Una applicazione del precedente teorema è la seguente:

Paradosso del torneo sportivo. Supponiamo che si svolga un torneo sportivo (in uno sport dove non siano previsti pareggi, per esempio la pallacanestro) a cui partecipino n squadre, che si incontrano a coppie in varie partite .

Supponiamo anche che alla fine del torneo ogni squadra abbia incontrato ogni altra squadra almeno una volta.

Possiamo rappresentare il torneo con un grafo orientato, in cui ogni vertice è una delle n squadre, e in cui ogni partita è rappresentata da un arco orientato che ha la coda sulla squadra vincente e la testa sulla perdente.

Poiché per ipotesi ogni squadra ha incontrato ogni altra squadra almeno una volta, il grafo è completo. Per il teorema precedente esiste nel grafo un cammino Hamiltoniano, che tocca tutte le n squadre ognuna una sola volta.

Una rappresentazione lineare di tale cammino Hamiltoniano sia per esempio:

A

1

A

2

A

3

………….A

n-1

A

n

(dove A

1

,A

2

,….,A

n

sono tutte le squadre distinte del torneo, disposte in un certo ordine).

Abbiamo in pratica dimostrato che è sempre possibile disporre le squadre del torneo in successione

in un opportuno ordine:

A

1

, A

2

, …….., A

n

in modo ch:

A

1

abbia sconfitto almeno una volta la squadra A

2

; A

2

abbia sconfitto almeno una volta la squadra A

3

; etc…

cioè in modo che ogni squadra sconfitto almeno una volta la squadra che la segue nella successione.