Matematica Discreta I Lezione del giorno 14 dicembre 2007 Grafi orientati

(1)

Matematica Discreta I

Lezione del giorno 14 dicembre 2007 Grafi orientati

Nei grafi fino ad ora considerati, gli archi non hanno un “verso” di percorrenza. Esistono però problemi in cui, nella rappresentazione sotto forma di grafo, è necessario “orientare” gli archi.

Se per esempio si svolge un torneo sportivo in cui si effettuano alcune partite (senza pareggi) fra un certo numero di squadre, la situazione del torneo potrebbe essere rappresentata con un grafo in cui ogni vertice è una delle squadre e in cui fra 2 vertici distinti tracciamo un numero di archi uguale al numero di partite intercorse fra le 2 squadre. In questo modo però non rappresentiamo l’informazione relativa alla squadra vincente in ogni partita: ciò può essere fatto “orientando” ogni arco, per esempio rappresentandolo come una freccia che va dalla squadra vincente verso la perdente.

Perveniamo così alla definizione di grafo orientato.

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

I grafi considerati in precedenza sono anche detti non orientati.

Notiamo che nella definizione di grafo orientato è consentito che ad un arco a sia associata una coppia ordinata (v,v) di 2 vertici coincidenti, nel qual caso l’arco a è un cappio, in cui coda e testa coincidono.

La rappresentazione grafica di un grafo orientato si ottiene rappresentando ogni vertice con un punto del piano e ogni arco con un arco orientato (freccia) che va dalla coda verso il dell’arco.

Per esempio, dato il grafo con V={a,b,c,d}, A={1,2,3,4,5,6}, 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 grafica é.

1 6

a d 2 3 5

b c

4

(2)

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 (n è detta lunghezza del cammino) della forma:

a

1

=

v1v2

, a

2

=

v2v3

, a

3

=

v3v4

,……., a

n

=

vnvn_1

(quindi la testa di ogni arco coincide con la coda dell’arco successivo). 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

Un grafo orientato è detto connesso se, comunque dati 2 vertici distinti v,w, esiste sempre almeno un cammino fra i due vertici (cioè un cammino che ha v come vertice di partenza, w come vertice di arrivo, o viceversa).

Il grafo dell’esempio precedente è connesso, come si verifica facilmente considerando in tutti i modi possibili 2 vertici distinti v,w e ogni volta costruendo un cammino da v a w oppure un cammino da w a v.

Un grafo orientato è detto fortemente connesso se, comunque dati 2 vertici distinti v,w, esiste sempre almeno un cammino da v a w ed anche un cammino da w a v.

Il grafo precedente, pur essendo connesso, non è fortemente connesso, perché per esempio, pur esistendo un cammino dal vertice a al vertice d, non esiste un cammino dal vertice d al vertice a.

Cammini Hamiltoniani

L’origine storica 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:

(3)

Interpretando nella teoria dei grafi 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.

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

Ma si può essere certi dell’esistenza di un cammino Hamiltoniano in certe categorie particolari di grafi, per esempio nei grafi completi.

Un grafo è detto completo

- nel caso non orientato se comunque dati 2 vertici distinti v, w, esiste sempre almeno un arco che ha v,w come estremi

- nel caso orientato se comunque dati 2 vertici distinti v, w, esiste sempre almeno un arco che ha v come coda e w come testa o viceversa

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

c d

Teorema. In un grafo orientato completo esiste 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

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

(4)

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

(5)

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:

A

1

A

2

A

3

………….A

n-1

A

n

Abbiamo in pratica dimostrato che è sempre possibile disporre le squadre in una opportuna successione:

A

1

, A

2

, …….., A

n

in modo che A

1

abbia sconfitto almeno una volta la squadra A

2

, che A

2

abbia sconfitto almeno una

volta la squadra A

3

e che in generale ogni squadra A

i

abbia sconfitto almeno una volta la squadra

A

i+1