Teoria dei grafi

5. TERMINO L’ALGORITMO QUANDO TUTTI GLI ELEMENTI CHE HO NELLA

LISTA NON HANNO PIU’ ARCHI AMMISSIBILI

STEP 0

Prendo il primo nodo nella colonna di sinistra della lista d’adiacenza: 1.

LIST = { 1 }

pred(1) = null

next = 1

order(1) = 1

LIST = { 1 }

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

58

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

STEP 1

LIST = { 1 }

esistono archi ammissibili dal nodo 1? Si, prendo il primo della lista cioè 2.

pred(2) = 1

next = 2

order(2) = 2

LIST= { 1,2 }

STEP 2

LIST= { 1,2 }

esistono ancora archi ammissibili dal nodo 1? Si, prendo il successivo della lista cioè 3.

pred(3) = 1

next = 3

order(3) = 3

LIST= { 1,2,3 }

STEP 3

LIST= { 1,2,3 }

esistono ancora archi ammissibili dal nodo 1? No, cancello il nodo 1 dalla lista.

next = 4

LIST= { 2,3 }

STEP 4

LIST= { 2,3 }

Scelgo l’ultimo nodo in LIST (Last In First Out): 3.

Esistono archi ammissibili dal nodo 3? Si, prendo il primo della lista cioè 2, ma è stato già

esaminato, dunque scelgo il successivo della lista d’adiacenza: 5.

pred(5) = 3

next = 5

order(5) = 5

LIST= { 2,3,5 }

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

59

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

STEP 5

LIST= { 2,3,5 }

esistono ancora archi ammissibili dal nodo 3? No, cancello il nodo 3 dalla lista.

next = 6

LIST= { 2,5 }

STEP 6

LIST= { 2,5 }

Scelgo l’ultimo nodo in LIST: 5.

Esistono archi ammissibili dal nodo 5? Si, prendo l’unico della lista cioè 6.

pred(6) = 5

next = 7

order(6) = 7

LIST= { 2,5,6 }

STEP 7

LIST= { 2,6 }

esistono ancora archi ammissibili dal nodo 5? No, cancello il nodo 5 dalla lista.

next = 8

LIST= { 2,6 }

STEP 8

LIST= { 2,6 }

Scelgo l’ultimo nodo in LIST: 6.

Esistono archi ammissibili dal nodo 6? No, cancello il nodo 5 dalla lista.

next = 9

LIST= { 2 }

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

60

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

STEP 9

LIST= { 2 }

Scelgo l’unico nodo in LIST: 2.

Esistono archi ammissibili dal nodo 2? Si, prendo il primo della lista cioè 4.

pred(4) = 2

next = 10

order(4) = 10

LIST= { 2,4 }

STEP 10

LIST= { 2,4 }

Esistono ancora archi ammissibili dal nodo 2? No, cancello il nodo 2 dalla lista.

marcabili e dunque lo cancello dalla lista.

next = 11

LIST= { 4 }

STEP 11

LIST= { 4 }

Scelgo l’unico nodo in LIST: 4.

Esistono archi ammissibili dal nodo 4? Si, ma li ho già esaminati dunque l’algoritmo ha termine ed

elimino il nodo 4 dalla lista.

next = 12

LIST= { }

La lista dei predecessori è la seguente:

• pred(4) = 2 STEP 9

• pred(6) = 5 STEP 6

• pred(5) = 3 STEP 4

• pred(3) = 1 STEP 2

• pred(2) = 1 STEP 1

• pred(1) = NULL STEP 0

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

61

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

E questo è l’albero ottenuto:

Ordinamento topologico

In un grafo aciclico connesso ed orientato è possibile stabilire un ordine di precedenza tra due

qualsiasi nodi i e j ovvero, è possibile maggiorare l’ordine di uno dei due nodi rispetto all’altro.

Inoltre, per ogni grafo aciclico connesso potrà esistere più d’un ordinamento topologico.

L’algoritmo dell’ordinamento topologico ci permette di posizionare lungo una retta i nodi del grafo

e dare una sola direzione univoca a tutti gli archi orientati (in genere destra).

Faccio notare due cose:

• se un grafo è aciclico, esiste almeno un ordinamento topologico

• se un grafo è aciclico, esiste almeno un nodo che ha grado d’ingresso pari a zero

ALGORITMO

• seleziono i nodi nel grafo che non hanno archi entranti

• cancello i loro archi uscenti e costruisco l’ordine dei nodi dell’ordinamento topologico

L’algoritmo va ovviamente iterato fino a quando non verifico più la prima condizione, ma vediamo

come funziona l’ordinamento topologico su questo grafo d’esempio:

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

62

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

Esempio 8.2

STEP 1

• seleziono i nodi che non hanno archi entranti: solo il nodo 1.

• cancello i suoi archi uscenti e lo metto nell’ordine topologico: { 1 }

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

63

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

STEP 2

• seleziono i nodi che non hanno archi entranti: solo il nodo 3.

• cancello i suoi archi uscenti e lo metto nell’ordine topologico: { 1,3 }

STEP 3

• seleziono i nodi che non hanno archi entranti: solo il nodo 2.

• cancello i suoi archi uscenti e lo metto nell’ordine topologico: { 1,3,2 }

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

64

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

STEP 4

• seleziono i nodi che non hanno archi entranti: solo il nodo 5.

• cancello i suoi archi uscenti e lo metto nell’ordine topologico: { 1,3,2,5 }

STEP 5

• seleziono i nodi che non hanno archi entranti: è rimasto solo 4 fuori dalla lista.

• lo metto nell’ordine topologico: { 1,3,2,5,6,4 }

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

65

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

Visualizziamo a questo punto l’ordinamento topologico appena costruito:

Come si vede dal grafo, sono verificate tutte le condizioni suddette:

• abbiamo dato un ordine di precedenza tra tutte le possibili coppie di nodi (i,j)

• abbiamo posizionato lungo una retta tutti i nodi del grafo dando loro una direzione univoca

• l’ordinamento topologico esiste

• il nodo 1 ha grado d’ingresso pari a zero

MINIMUM SPANNING TREE

(minimo albero ricoprente)

Come abbiamo visto con gli algoritmi FIFO e LIFO, è possibile creare su di un grafo connesso

orientato e non, un albero che copra tutti i nodi del grafo stesso.

Quando diamo ad ogni arco un peso o un valore di costo, esisterà tra tutti gli “spanning trees” un

“minimum spanning tree” tale che la somma di tutti i pesi degli archi che lo compongono sia la

minima possibile.

Vedremo tra breve algoritmi atti alla ricerca del minimum spanning tree.

Taglio

Per taglio s’intende quell’arco che crea due componenti connesse.

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

66

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

Esempio 8.3

Formalmente, indichiamo questo taglio nel seguente modo:

• (i,j) є [S,S’]

dove S è la prima componente ed S’ la seconda.

TEOREMA 8.1

Un albero G si dice minimo ricoprente se e solo se soddisfa la condizione di ottimalità del taglio.

Questa condizione è la seguente:

• ≤ C

per ogni (i,j) є G si ha che C

ij kl

• ogni C sia contenuto nel taglio [S,S’]

kl

ovvero, scelto un generico arco C del grafo G possiamo sempre trovare un arco C del grafo

ij kl

originario (del quale abbiamo trovato l’albero minimo ricoprente) che pesi più di C e che ogni arco

ij

non appartenente all’albero faccia parte dell’opportuno taglio [S,S’].

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

67

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

ALGORITMO DI KRUSKAL (1950)

Quest’algoritmo è ancora più semplice di quello topologico e ci permette di trovare il Minimum

Spanning Tree con un semplice criterio d’ordinamento.

Ma vediamo come funziona.

1. ordino in modo crescente i pesi degli archi e li cancello dal grafo lasciando solo i nodi

2. scelgo via via l’arco più ‘leggero’ e lo posiziono nella sua locazione originaria

3. se nel fare il passo 2 ottengo un ciclo, non metto quest’ultimo arco e passo al successivo

Testiamolo con un esempio.

Esempio 8.4

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

68

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

PASSO 1 0

1 0

2 0

3 1

4 2

5 2

6 4

7 5

8 5

9 6

10 7

11 8

12 9

13 11

14 12

15 15

16 18

17 18

18 18

19 21

20 23

21 23

22 31

23 32

24 34

25 43

26 45

27 54

28 58

29 65

30 67

31 71

32 91

33 239

34 341

35 567

36 567

37 1872

38

PASSO 2

Evidenzierò in rosso gli archi riposizionati, supponendo che chi non sia evidenziato non si trovi al

momento sul grafo.

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

69

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

Eseguiamo l’algoritmo sui primi 11 archi:

0

1 0

2 0

3 1

4 2

5 2

6 4

7 5

8 5

9 6

10 7

11

Come si può vedere, fino a questo punto non si è venuto a creare nessun ciclo, ma al passo

successivo e cioè, con la scelta del dodicesimo arco che ha peso pari a 8 siamo, saremo costretti a

non rimetterlo nel grafo ed ad andare oltre. L’arco di peso 8 mi crea infatti il ciclo { 8,6,5 }.

8

12

Appunti di Teoria dei Grafi Capitolo 8

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

70

Appunti di Teoria dei Grafi – Alcuni algoritmi in dettaglio Capitolo 8

Continui