Algoritmi & Laboratorio

(1)

Algoritmi & Laboratorio

Grafi, minimo albero ricoprente

Grafi, minimo albero ricoprente Algoritmi & Laboratorio

a.a. 2006-2007 Andr´as Horv´ath

Acknowledgement Lucidi da

• F. Damiani, a.a. 2004-2005

• C. Demetrescu et al, Algoritmi e strutture dati, McGraw-Hill

• M. Zacchi, a.a. 2003-2004 I lucidi

• non sono un sostituto per il libro di testo

• non contengono un discorso completo Non limitate il vostro studio ai lucidi!

Albero ricoprente

• sia dato un grafo connesso e non orientato

• un albero ricoprente `e un sottografo che – contiene tutti nodi

– `e aciclico – `e connesso

Grafi, minimo albero ricoprente

Algoritmi & Laboratorio 3 a.a. 2006-2007

Andr´as Horv´ath

Peso di un grafo

• dato un grafoG= (V, E) non orientato e pesato con funziona pesoW

• il peso del grafo `eW(G) =P

e∈EW(e) 4

5 5

3 8 2 2

7 5

4 8

12 3

2

• W(G) = 70

(2)

Minimo albero ricoprente

• dato un grafo G= (V, E) non orientato e pesato trovare un suo albero ricoprenteT che abbia peso minimo

4 5

5

3 8 2 2

7 5

4 8

12 3

2

• W(T) = 32

Andr´as Horv´ath

Minimo albero ricoprente

• minimo albero ricoprente non `e unico 4

5 5

3 8 2 2

7 5

4 8

12 3

2

4 5

5

3 8 2 2

7 5

4 8

12 3

2

W(T) = 32 W(T) = 32

Algoritmo generico

• sia dato un grafoG= (V, E)

• MINIMO ALBERO RICOPRENTE(G) A← ∅

whileAnon `e un albero ricoprente do trova un arco (u, v) che sia “sicuro” per A A←A∪(u, v)

• (u, v) `e un arco “sicuro” per A: A∪(u, v) `e un sottoinsieme degli archi di un minimo albero di copertura diG

• al termine dell’algoritmoT = (V, A) `e un minimo albero di copertura

Andr´as Horv´ath

Tagli

• taglio di un grafoG(V, E): `e una partizione diV in due insiemi,X eV −X

A

B

D

C

E F

• (X ={A, C, E}, V −X ={B, D, F})

• un arco (u, v) attraversa il tagli (X, V −X) se u∈X, v∈V −X

• l’arco (B, C) `e un arco che attraversa il taglio (X ={A, C, E}, V −X ={B, D, F})

(3)

Tagli

• un taglio rispetta un insieme di archiAse nessun arco diA attraversa il taglio

• un arco che attraversa un taglio `e un arco leggero se `e un arco di peso minimo tra quelli che attraversano il taglio

A

B

D

C

E

F 5 5

6 2

8

10 7

2 6

10

• il taglio (X ={A, C, E}, V −X) rispetta l’insieme di archi {(C, E),(B, D)} ma non rispetta{(A, F),(B, D)}

• l’arco (A, F) `e leggero per il taglio (X ={A, C, E},V −X)

Andr´as Horv´ath

Criterio per riconoscere archi “sicuri”

• teorema I:

– sia G= (V, E) un grafo non orientato, connesso e pesato – sia Aun sottoinsieme diE contenuto in un qualche albero

di copertura

– sia (X, V −X) un qualunque taglio che rispettaA – sia (u, v) un arco leggero che attraversa (X, V −X) – allora l’arco (u, v) `e sicuro perA

Dimostrazione di teorema I

• siaT un albero di copertura minimo che contiene A

• seT contiene l’arco (u, v) allora l’arco `e sicuro perA

• assumiamo allora cheT non contenga l’arco (u, v)

• mostreremo che (u, v) `e sicuro perAcostruendo un altro albero di copertura minimoT^′che contenga A∪(u, v)

Andr´as Horv´ath

• T `e un albero di copertura

• inT deve esserci un cammino dauav

• tale cammino deve contenere almeno un arco (x, y) con x∈X, y ∈V −X

u v

x

y

X V-X

(4)

• consideriamo l’alberoT^′ con archi E(T^′) = (E(T)−(x, y))∪(u, v)

u v

x

y

X V-X

Andr´as Horv´ath

• W(T^′) =W(T)−W(x, y) +W(u, v)

• (u, v) `e un arco leggero che attraversa il taglio (X, V −X)

• anche (x, y) attraversa il taglio (X, V −X)

• per cuiW(u, v)≤W(x, y) e quindiW(T^′)≤W(T)

• T `e per ipotesi un albero di copertura minimo

• per cuiW(T^′) =W(T)

• T^′`e un albero di copertura minimo eA∪(u, v)⊆E(T)

• corollario I:

– siaG= (V, E) un grafo non orientato, connesso e pesato – siaAun sottoinsieme di E contenuto in un albero di

copertura minimo

– siaC una componente connessa (un albero) nella foresta G(A) = (V, A)

– sia (u, v) `e un arco leggero che connetteC a una qualche altra componente connessa diG(A)

– allora l’arco (u, v) `e sicuro perA

Andr´as Horv´ath

• dimostrazione:

– sianoX i vertici diC

– il taglio (X, V −X) rispettaA

– segue dal teorema I che l’arco (u, v) `e sicuro perA

(5)

Algoritmi concreti

• due algoritmi:

– di Kruskal – di Prim

• possono essere descritti come specializzazioni dell’algoritmo generico

• si basano sul precedente corollario

• algoritmi greedy: un arco sicuro `e un arco di peso minimo, quindi il pi`u appetibile

Andr´as Horv´ath

Algoritmo di Kruskal

• mantiene un sottografo non necessariamente connesso (V, A) di un MST (minimal spanning tree, minimo albero ricoprente)

• all’inizio: tutti i vertici del grafo e nessun arco

• per ogni arco, in ordine non decrescente di costo:

– se l’arco ha entrambi gli estremi nella stessa componente connessa di (V, A) escludilo dalla soluzione

– altrimenti, basandoti sul corollario I, includilo nella soluzione (fondendo due componenti connesse)

Algoritmo di Kruskal applicando la schema generale

• MST Kruskal(G) A← ∅

ordina gli archi in ordine non decrescente di peso for ∀(u, v) nell’ordinedo

if(u, v) `e “sicuro” perAthen A←A∪(u, v)

• che cosa significa “sicuro” per Kruskal?

Andr´as Horv´ath

Algoritmo di Kruskal

• obiettivo: la costruzione di un particolare albero, ossia un grafo connesso senza cicli

• MST Kruskal(G) A← ∅

ordina gli archi in ordine non decrescente di peso for ∀(u, v) nell’ordinedo

if(u, v) non crea ciclo inG(A) = (V, A)then A←A∪(u, v)

(6)

Complessit`a dell’algoritmo di Kruskal

• non pu`o essere valutata se non si conosce la struttura dati usata per rispondere alla domanda di esistenza del ciclo

• bisogna memorizzare i vertici delle componenti connesse del sottoinsieme dell albero di copertura in costruzione

• una struttura dati per insiemi disgiunti

– collezioneS di insiemi dinamici disgiunti (di vertici) – ogni insieme identificato da un rappresentante

Andr´as Horv´ath

Struttura dati che rappresenta insiemi disgiunti: operazioni

• tre operazioni

– creazione di un nuovo insieme il cui unico elemento `ex:

Make set(x)

– unione di due insiemi che contengono xey: Union(x, y) – trovare il rappresentante dell insieme contenentex:

Find set(x)

• una sequenza din+moperazioni Make set, Find set e Union, di cui

– n sono operazioni di Make set – msono operazioni di union e/o find

pu`o essere eseguita su una UnionFind in tempo O((n+m) logn) nel caso peggiore

Algoritmo di Kruskal con insiemi disgiunti MST Kruskal(G)

A← ∅

for∀v∈V do Make set(v)

ordina gli archi in ordine non decrescente di peso for∀(u, v)∈E nell’ordinedo

ifFind(u)6=Find(v)then A←A∪(u, v) Union(u, v)

Andr´as Horv´ath

Complessit`a nel caso peggiore

• ordinamento: O(|E|log|E|)

• operazioni sulla foresta di insiemi disgiunti:

O((|V|+|E|) log|V|)

• il grafo `e connesso: O((|V|+|E|) log|V|) =O(|E|log|V|)

• totale: O(|E|log|V|)

(7)

Esempio

A

B

D

C

E F G

15 20

1

7 12 7

11

10

6 3 4

• gli archi in ordine per peso non decrescente: (a, f), (c, g), (e, g), (c, e), (a, d), (d, f), (f, g), (d, e), (b, d), (a, b), (b, c)

Andr´as Horv´ath

Esempio

A

B

D

C

E F G

15 20

1

7 12

7 11

10

6 3 4

• MST non `e unico: dipende dal ordine in cui gli archi di peso uguale si considerano

Correttezza dell’algoritmo di Kruskal

• invariante del ciclo: A`e un sottoinsieme degli archi di un MST diG:

– l’invariante viene reso vero dall inizializzazione diAcome insieme vuoto

– corpo del ciclofor mantiene l’invariante:

∗ se l’arco crea un ciclo non viene aggiunto

∗ se non crea un ciclo allora per corollario I l’arco `e

“sicuro” e l’invariante viene mantenuto

• all’termine del algoritmo (V, A) `e connesso (si pu`o dimostrare per assurdo)

Andr´as Horv´ath

Algoritmo di Prim

• mantiene un sottografo connesso (V −Q, A) di un MST

• all’inizio consiste di un nodo arbitrario:

– Qcontiene tutti i nodi tranne questo nodo iniziale – A`e vuoto

• applican−1 volte il seguente passo

• scegli un arco (u, v) di peso minimo incidente su (V −Q, A) – aggiungilo adA

– togli daQ il vertice a cui porta l’arco

(8)

Algoritmo di Prim applicando la schema generale

• MST Prim(G, s) A← ∅

Q←V − {s}

whileQ6=∅ do

scegli un arco (u, v) “sicuro” per A A←A∪(u, v)

Q←Q−v

• che cosa significa “sicuro” per Prim?

Andr´as Horv´ath

Algoritmo di Prim

• strategia di Prim: mantenere un sottografo connesso

• MST Prim(G, s) A← ∅

Q←V − {s}

whileQ6=∅ do

scegli l’arco (u, v) con peso minimo eu∈V −Q, v∈Q A←A∪(u, v)

Q←Q−v

Algoritmo di Prim MST Prim(G, s)

Q←V

for∀v∈V dod[v]← ∞ d[s]←0

π[s]←nil whileQ6=∅ do

u←nodo con d minimo inQ for∀v∈adj[u]do

ifv∈Qe W(u, v)<d[v]then d[v] ←W(u, v)

π[v]←u

Andr´as Horv´ath

Esempio

A

B

D

C

E F G

15 20

1

7 12

7 11

10 6

3 4

A

B

D

C

E F G

15 20

1

7 12

7 11

10 6

3 4

(9)

Complessit`a dell’algoritmo di Prim

• Q pu`o essere implementata come coda di priorit`a usando o un heap binario o un heap di Fibonacci

• le priorit`a sono date dall attributo d

• il costo dell algoritmo di Prim `e limitato da – costo inizializzazione: O(|V|)

– costo delle estrazioni del minimo: O(|V|log|V|) – costo di risistemazione dello heap binario oppure di

fibonacci dopo il decremento eventuale delle chiavi:

O(|E|log|V|) oppureO(|E|)

• complessit`a dell algoritmo con

– heap binario: O((|V|+|E|) log|V|) =O(|E|log|V|) – heap di Fibonacci: O(|V|log|V|+|E|)

Andr´as Horv´ath

Correttezza dell’algoritmo di Prim

• due invarianti del ciclo:

– invariante I: ∀t∈Q:π[t]6=nil⇒π[t]∈V −Q

– invariante II: ∀t∈Q: (π[t], t) un arco di peso minimo trat e un vertice diV −Q

• si dimostrano facilmente esaminando l’inizializzazione e il corpo del ciclo

Correttezza dell’algoritmo di Prim

• dimostriamo il seguente invariante:

(V −Q,{(π[t], t) :t6=s, t∈V −Q}) `e un sottografo di un MST:

– inizialmente vero

– il corpo del ciclo mantiene l’invariante:

∗ sia uil vertice estratto da Q

∗ per invariante I e II, l’arco (π[u], u) `e un arco leggero che unisce le componenti connesse (V −Q, A) e ({u},∅)

∗ allora, per il Corollario 1, `e un arco sicuro per A

Andr´as Horv´ath