Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... ·...

F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)

Grafi (non orientati e connessi): minimo albero ricoprente

Una presentazione alternativa (con ulteriori dettagli)

……………………………………………………………………..


Dato un grafo pesato non orientato e connesso trovare un suoalbero di copertura che abbia peso minimo.

Il peso di un grafo pesato la somma dei pesi dei suoi archi:

W (G) = Σe∈E W (e)

Un grafo pesato è una coppia: 1. grafo G = <V, E>2. funzione peso W: E →ℜ (insieme dei numeri reali)

Problema: calcolo del minimo albero di copertura (M.S.T.)


ab

cd

e

fg

1

7

15

7

11

1220

6

3410

G

ab

cd

e

fg

17 12

34

10

T W(T) = 37

Esempio


Un algoritmo “generico”


MST-generic (G, W)A ←Φ

while A non è un albero di copertura dotrova un arco (u,v) che sia sicuro per A A ← A ∪ {(u, v)}

return A{<V, A> e` un MST di G}

{G connesso, non orientato & W: E[G] →ℜ}

{A è un sottinsieme degli archi di un MST di G}

dove:• “un arco (u,v) è sicuro per A” significa che

“A ∪ {(u, v) } è un sottoinsieme degli archi di un MST di G”

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Tagli e cicli

• Dato un grafo non orientato G=(V,E), un taglio in G è una partizione dei vertici V in due insiemi: X e V-X.

• Un arco e=(u,v) attraversa il taglio (X, V-X) se u∈X e v∈V-X

• Un ciclo è un cammino in cui il primo e l’ultimo vertice coincidono


• Un taglio rispetta un insieme di archi A se nessun arco di A attraversa il taglio.

• Un arco che attraversa un taglio è un arco leggero se è un arco di peso minimo tra quelli che attraversano il taglio.

Teorema 1. Sia G = (V,E) un grafo non orientato e connesso con una funzione peso W a valori reali definita su E. Sia A un sottoinsieme di E contenuto in un qualche albero di copertura minimo per G, sia (X, V-X) un qualunque taglio che rispetta A, e sia (u,v) un arco leggero che attraversa (X, V-X). Allora l’arco (u,v) è sicuro per A.

Dimostrazione. Sia T l’albero di copertura minimo che contiene A. Se T contiene l’arco (u,v) allora l’arco è sicuro per A. Assumiamo allora che T non contenga l’arco (u,v).

Un “criterio” per riconoscere gli archi sicuri


Mostreremo che (u,v) è sicuro per A costruendo un altroalbero di copertura minimo T’ che contenga A ∪ {(u, v)}.

Poichè T è un albero di copertura, in T vi sarà un cammino da u a v e tale cammino dovrà contenere almeno un arco: (x, y) con x in X e y in V-X.

Cosideriamo l’albero T’ con archi ET’ = ET - {(x, y)} ∪ {(u, v)}

u

v

X

V-X

x

y


ET’ = ET - {(x, y)} ∪ {(u, v)} W(T’) = W(T) - W(x, y) + W(u, v)

Ma (u, v) è un arco leggero che attraversa il taglio (X,V-X) che è attaversato anche da (x, y), per cui W(u, v) ≤ W(x, y).

Poichè T è per ipotesi un MST, W(T’) deve essere uguale a W(T)

• T’ è un albero di copertura di G minimo e A ∪ {(u, v)} ⊆ ET’

W(T’) ≤ W(T)

• T’ è un albero di copertura di G

A ∪ {(u, v)} è un sottinsieme degli archi di un MST di G


Corollario 1. Sia G = (V,E) un grafo non orientato e connesso con una funzione peso W a valori reali definita su E. Sia A un sottoinsieme di E contenuto in un albero di copertura minimo per G, e sia C una componente connessa (un albero) nella foresta GA=(V,A). Se (u,v) è un arco leggero (cioè un arco di peso minimo) che connette C a una qualche altra componente connessa di G, allora l’arco (u,v) è sicuro per A.

Dimostrazione. Siano X i vertici di C. Il taglio (X, V-X) rispetta A quindi l’arco (u,v) è sicuro per A.

Osservazione. Gli algoritmi di Kruskal e di Prim possono essere descritti come “specializzazioni” dell’algoritmo “generico” che, per scegliere un arco sicuro, si basano sul precedente corollario. Si tratta ovviamente di algoritmi greedy (un arco sicuro è un arco di peso minimo, quindi il più appetibile).


Algoritmo di Kruskal


Strategia

• Mantiene un sottografo non necessariamente connesso (V,A) di un MST [in [Dem]: una foresta di alberi blu], all’inizio: tutti i vertici del grafo e nessun arco

• Per ogni arco, in ordine non decrescente di costo, applica il seguente passo: se l’arco ha entrambi gli estremi nella stessa componente connessa di (V,A) [in [Dem]: nello stesso albero blu], escludilo dalla soluzione [in [Dem]: applica la regola del ciclo e coloralo rosso], altrimenti, basandoti sul Corollario 1, includilo nella soluzione (fondendo due componenti connesse) [in [Dem]: applica la regola del taglio e coloralo blu (fondendo quindi due alberi blu)]


Questa soluzione del problema MST può essere descrittacome una applicazione dello “schema generale 1” degli algoritmi greedy.

MST-Kruskal (G, W)A ←Φ“ ordina gli archi in ordine non decrescente di peso”for ogni arco (u, v) nell’ordine do

if “ (u, v) può essere aggiunto a A”then A ← A ∪ {(u, v)}

return A


MST-Kruskal (G, W)A ←Φ“ ordina gli archi in ordine non decrescente di peso”for ogni arco (u, v) nell’ordine do

if “ (u, v) non crea un ciclo ”then A ← A ∪ {(u, v)}

return A

DOMANDA: Che cosa significa, per questo problema,“ (u, v) può essere aggiunto a A” ?

RISPOSTA: L’obiettivo è la costruzione di un particolare albero, ossia di un particolare grafo connesso senza cicli!


La complessità dell’algoritmo non può essere valutatase non si conosce la struttura dati usata per rispondere alla domanda di esistenza del ciclo.

Potremmo usare una struttura dati per insiemi disgiunti(per memorizzare i vertivi delle componenti connesse del sottoinsieme dell’albero di copertura in costruzione):

• collezione S di insiemi dinamici disgiunti (di vertici)• ogni insieme identificato da un rappresentante


Operazioni sulla struttura dati che rappresenta gli insiemi disgiunti

• Creazione di un nuovo insieme il cui unico elemento è x:Make-set (x)

• Unione di due insiemi che contengono x e y:Union (x, y)

• Trovare il rappresentante dell’insieme contenente x:Find-set (x)

Ricordiamo che:

una sequenza di n+m operazioni Make-set, Find-set e Union, di cui n sono operazioni di Make-set e m sono operazioni diunion e/o find può essere eseguita su una UnionFind in tempo O((n+m) log*n) nel caso peggiore.


Riscriviamo l’algoritmo di Kruskal usando una foresta di insiemi disgiunti per memorizzare (i verici de) le componenti connesse della foresta <V, A>

MST-Kruskal (G, W)A ←Φ{crea la foresta}for ogni vertice v ∈ V[G] do

Make-set (v)“ ordina gli archi in ordine non decrescente di peso”for ogni arco (u, v) ∈ E[G] nell’ordine do

{se (u, v) non crea un ciclo aggiungi l’arco ad A}if Find-set (u) ≠ Find-set (v)

then A ← A ∪ {(u, v)}Union (u, v)

return A


Complessità nel caso peggioreMST-Kruskal (G, W)

A ←Φfor ogni vertice v ∈ V[G] do

Make-set (v)“ ordina gli archi in ordine non decrescente di peso”for ogni arco (u, v) ∈ E[G] nell’ordine do

if Find-set (u) ≠ Find-set (v) then A ← A ∪ {(u, v)}

Union (u, v) return A

O(E lgE)Ordinamento: Operazioni sulla foresta di insiemi disgiunti:

O((V+E) lgV) =(siccome il grafo è connesso) O(E lgV) Si ottiene pertanto: O(E lgE) + O(E lgV) = O(E lgE)


ab

cd

e

fg

1

7

15

7

11

1220

6

3410

G

Ordiniamo gli archi 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) >

Esempio


< (a,f), (c,g), (e,g), (c,e), (a,d), (d,f), (f,g), (d,e), (b,d), (a,b), (b,c) >

ab

cd

e

fg

1

7 12

3410

N.B. l’albero di copertura minimo non è unico, in generale; si ottengono alberi diversi a seconda dell’ordine in cui si considerano gli archi di peso uguale.


MST-Kruskal (G, W)A ←Φfor ogni vertice v ∈ V[G] do

Make-set (v)“ ordina gli archi in ordine non decrescente di peso”

for ogni arco (u, v) ∈ E[G] nell’ordine doif Find-set (u) ≠ Find-set (v)

then A ← A ∪ {(u, v)}Union (u, v)

return A{<V, A> e` un MST di G}


{A è un sottoinsieme degli archi di un MST di G}

Correttezza dell’algoritmo di Kruskal


a) L’invariante viene reso vero dall’inizializzazione di A come insieme vuoto.

b) Supponiamo che A sia un sottinsieme degli archi T di un MST di G, <V, T> e dimostriamo che l’esecuzione del corpo del while mantiene vero l’invariante.Sia (u, v) l’arco da considerare nell’ordinamento.

• Se (u, v) crea un ciclo A non viene modificato.

• Se (u, v) non crea un ciclo allora è un arco di peso minimo che unisce due componenti connesse della foresta GA= (V,A). Quindi, per il Corollario 1, è un arco sicuro per A.


Algoritmo di Prim


Strategia• Mantiene un sottografo connesso (V-Q,A) di un MST [in [Dem]: un

unico albero blu T], che all’inizio consiste di un vertice arbitrario • Applica per n-1 volte il seguente passo: scegli un arco (u,v) di costo

minimo incidente su (V-Q,A) e, basandoti sul Corollario 1, aggiungilo ad A togliendo da Q il vertice a cui porta l’arco, ovvero: fondi le componenti connesse (V-Q,A) e ({v}, Φ) [in [Dem]: T e coloralo blu (applica la regola del taglio), ovvero: aggiungilo all’albero]

• Definiamo arco candidato [in [Dem]: azzurro] un arco (u,v) tale che u∈V-Q, v∈ Q [in [Dem]: u∈T, v∉T], (u,v) ha il costo minimo tra tutti gli archi che connettono v ad un vertice in V-Q [in [Dem]: T]: l’algoritmo mantiene gli archi candidati [in [Dem]: azzurri] in una opportuna struttura dati e mantiene il loro costo associando, per mezzo di una opportuna struttura dati, ad ogni vertice in Q il costo dell’arco di peso minimo che collega tale vertice ad un vertice in V-Q (∞ se non esistono archi che collegano il vertice ad un vertice in V-Q)


Greedy2 ({a1, a2, …an})S ←Φ“valuta le appetibilità degli ai ”while “ci sono elementi da scegliere” do

“scegli l’ai più appetibile”if “ai può essere aggiunto a S”

then S ← S ∪ {ai}“aggiorna le appetibilità degli ai ”

return S

Questa soluzione del problema MST può essere descrittacome una applicazione dello “schema generale 2” degli algoritmi greedy.


MST-Prim (G, W, r)Q ← V[G]for ogni u ∈ Q do key[u] ←∞key[r] ← 0π[r] ← nilwhile Q ≠ Φ do

u ← Extract-min(Q)

for ogni v ∈ Adj[u] do

if v ∈ Q e W(u, v) < key[v] then key[v] ← W(u, v)

π[v] ← u

{valuta le appetibilitàdei vertici}

{scegli il vertice più appetibileda inserire nell’albero}

{aggiorna le appetibilità dei vertici}

{memorizziamo gli archi come coppie (π[v], v)}{ci sono vertici da scegliere}

{memorizza i vertici da scegliere}


ab

cd

e

fg

1

7

15

7

11

1220

6

3410

ab

cd

e

fg

20

6

3

12

71

410

11

15

Esempio


Q può essere implementata come coda di priorità, usando o un heap binario o un heap di Fibonacci, in cui le priorità sono date dall’attributo key.

Il costo dell’algoritmo di Prim è limitato da:costo inizializzazione O(V) +

costo delle estrazioni del minimo O(V logV) + costo di risistemazione dello heap binario oppure heap di fibonacci O(E logV) oppure O(E) dopo il decremento eventuale delle chiavi

Complessità dell’algoritmo con• coda realizzata con heap binario:

O((V+E)lgV) = (siccome il grafo è connesso) O(E logV)• coda realizzata con un heap di Fibonacci: O(V logV + E)


MST-Prim (G, W, r)Q ← V[G]for ogni u ∈ Q do key[u] ←∞key[r] ← 0π[r] ← nil

while Q ≠ Φ dou ← Extract-min(Q)for ogni v ∈ Adj[u] do

if v ∈ Q e W(u, v) < key[v] then key[v] ← W(u, v)

π[v] ← u

Correttezza dell’algoritmo di Prim

{<V, {(π[t], t) | t ≠ r}> e` un MST di G}


{<V-Q, {(π[t], t) | t ≠ r & t ∈ V-Q}>e` un sottoalbero di un MST di G}


Per fare la dimostrazione di correttezza useremo la seguente proprietà:

La proprietà si dimostra facilmente esaminando l’inizializzazionee il corpo del while.

Le asserzioni :

sono invarianti del ciclo while

1. ∀t ∈ Q: π[t] ≠ nil ⇒ π[t] ∈ V-Q & 2. ∀t ∈ Q: π[t] ≠ nil ⇒ (π[t], t) è in G un arco di peso

minimo tra t e un vertice di V-Q.

Proprieta` 1


a) <V-Q, {(π[t], t) | t ≠ r & t ∈ V-Q}> è inizialmente vuoto,perciò è un sottoalbero di un MST di G

b) Supponiamo che <V-Q, {(π[t], t) | t ≠ r & t ∈ V-Q}> sia un sottoalbero di un MST di G, <V, T> e dimostriamo che l’esecuzione del corpo del while mantiene vero l’invariante.Sia u il vertice estratto da Q. Per la Proprietà 1, l’arco (π[u], u)è un arco leggero che unisce le componenti connesse (V-Q,A) e ({u},Φ) della foresta GA= (V,A). Allora, per il Corollario 1, è un arco sicuro per A.

Dimostriamo ora che il predicato:

è sempre vero e perciò invariante del while

<V-Q, {(π[t], t) | t ≠ r & t ∈ V-Q}> è un sottoalbero di un MST di G


u

v

rV-Q

Q


Esercizio

• Calcolare la complessita’ dell’algoritmo di Prim nel caso in cui la coda con priorita’ sia implementata:

con una lista linkata ordinata in base alla priorita’,con una lista linkata non ordinata,con un array ordinato,con un array non ordinato,con un array “circolare” ordinato,con un array “circolare” non ordinato.

Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... ·...

Documents

Transcript of Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... ·...