+ All Categories
Home > Documents > Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... ·...

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

Date post: 05-Sep-2020
Category:
Upload: others
View: 2 times
Download: 0 times
Share this document with a friend
33
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) ……………………………………………………………………..
Transcript
Page 1: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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)

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

Page 2: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 3: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 4: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

Un algoritmo “generico”

Page 5: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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”

Page 6: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

Page 7: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

• 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

Page 8: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 9: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 10: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 11: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

Algoritmo di Kruskal

Page 12: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 13: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 14: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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!

Page 15: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 16: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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.

Page 17: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 18: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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)

Page 19: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 20: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 21: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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}

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

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

Correttezza dell’algoritmo di Kruskal

Page 22: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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.

Page 23: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

Algoritmo di Prim

Page 24: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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)

Page 25: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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.

Page 26: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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}

Page 27: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 28: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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)

Page 29: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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}

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

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

Page 30: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 31: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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

Page 32: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

u

v

rV-Q

Q

Page 33: Grafi (non orientati e connessi): minimo albero ricoprentedamiani/DIDATTICA/aa0405/AlgELab/... · MST-Kruskal (G, W) A ←Φ “ ordina gli archi in ordine non decrescente di peso”

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

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.


Recommended