Grafi, Albero Minimo Ricoprente - Appunti PDF

Indice 1. Definizione 2. Algoritmo generico...

Indice 1. Definizione 2. Algoritmo generico Grafi, minimo albero ricoprente 3. Algoritmo di Kruskal 4. Algoritmo di Prim Corso di Algoritmi e strutture dati Corso di Laurea in Informatica Docenti: Ugo de’Liguoro, András Horváth Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 1/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 2/ 70 Sommario 1. Albero ricoprente Obiettivo: I sia dato un grafo connesso e non orientato I capire il concetto “minimo albero ricoprente” I un albero ricoprente è un sottografo che I sviluppare algoritmi per trovare un minimo albero ricoprente I contiene tutti nodi I è aciclico I è connesso Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 3/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 70  1. Peso di un grafo 1. Minimo albero ricoprente I dato un grafo G = (V , E) non orientato e pesato con funziona peso W I problema: dato un grafo G = (V , E) non orientato e pesato trovare un suo I il peso del grafo è W (G) = e∈E W (e) P albero ricoprente T che abbia peso minimo 5 4 5 4 3 2 3 2 8 8 5 5 8 2 8 2 4 4 2 2 3 3 5 5 7 7 12 12 I W (G) = 70 I T tale che W (T ) è minimo: W (T ) = 32 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 70 1. Minimo albero ricoprente 2. Algoritmo generico I minimo albero ricoprente non è unico I sia dato un grafo G = (V , E) 5 5 I MINIMO_ALBERO_RICOPRENTE(G) 4 4 A←∅ 2 3 2 3 while A non è un albero ricoprente do 8 5 8 5 trova un arco (u, v ) che sia “sicuro” per A 2 8 2 8 A ← A ∪ (u, v ) 4 2 4 2 I (u, v ) è un arco “sicuro” per A: A ∪ (u, v ) è un sottoinsieme degli archi di un 3 5 3 5 minimo albero di copertura di G 7 7 I al termine dell’algoritmo T = (V , A) è un minimo albero di copertura 12 12 I come si trova un arco “sicuro”? W (T ) = 32 W (T ) = 32 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 70  2. Tagli 2. Tagli I taglio di un grafo G(V , E): è una partizione di V in due insiemi, X e V − X I un taglio rispetta un insieme di archi A se nessun arco di A attraversa il taglio B I un arco che attraversa un taglio è C A un arco leggero se è un arco di peso minimo tra quelli che attraversano il taglio 5 B 8 F C A E 2 6 D 2 F 6 7 10 I (X = {A, C, E}, V − X = {B, D, F }) 5 D E I un arco (u, v ) attraversa il taglio (X , V − X ) se u ∈ X , v ∈ V − X 10 I l’arco (B, C) è un arco che attraversa il taglio I il taglio (X = {A, C, E}, V − X ) rispetta l’insieme di archi {(C, E), (B, D)} ma (X = {A, C, E}, V − X = {B, D, F }) non rispetta {(A, F ), (B, C)} I l’arco (A, F ) è leggero per il taglio (X = {A, C, E}, V − X ) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 9/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 70 2. Criterio per riconoscere archi “sicuri” 2. Dimostrazione di teorema I I teorema I: I sia T un albero di copertura minimo che contiene A I sia G = (V , E) un grafo non orientato, connesso e pesato I se T contiene l’arco (u, v ) allora l’arco è sicuro per A I sia A un sottoinsieme di E contenuto in un qualche albero di copertura minimo I sia (X , V − X ) un qualunque taglio che rispetta A I assumiamo allora che T non contenga l’arco (u, v ) I sia (u, v ) un arco leggero che attraversa (X , V − X ) I mostreremo che (u, v ) è sicuro per A costruendo un altro albero di copertura I allora l’arco (u, v ) è sicuro per A minimo T 0 che contenga A ∪ (u, v ) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 70  2. Dimostrazione di teorema I 2. Dimostrazione di teorema I I T è un albero di copertura I consideriamo l’albero T 0 con archi E(T 0 ) = (E(T ) − (x, y )) ∪ (u, v ) I in T deve esserci un cammino da u a v I tale cammino deve contenere almeno un arco (x, y ) con x ∈ X , y ∈ V − X x y x y u v X V-X u v X V-X Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 70 2. Dimostrazione di teorema I 2. Criterio per riconoscere archi “sicuri” I W (T 0 ) = W (T ) − W (x, y ) + W (u, v ) I corollario I: I (u, v ) è un arco leggero che attraversa il taglio (X , V − X ) I sia G = (V , E) un grafo non orientato, connesso e pesato I sia A un sottoinsieme di E contenuto in un albero di copertura minimo I anche (x, y ) attraversa il taglio (X , V − X ) I sia C una componente connessa (un albero) nella foresta G(A) = (V , A) I per cui W (u, v ) ≤ W (x, y ) e quindi W (T 0 ) ≤ W (T ) I sia (u, v ) è un arco leggero che connette C a una qualche altra componente I T è per ipotesi un albero di copertura minimo connessa di G(A) I allora l’arco (u, v ) è sicuro per A I per cui W (T 0 ) = W (T ) I T 0 è un albero di copertura minimo e A ∪ (u, v ) ⊆ E(T 0 ) I quindi abbiamo dimostrato che (u, v ) è un arco sicuro Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 70  2. Criterio per riconoscere archi “sicuri” 2. Algoritmi concreti I dimostrazione: I due algoritmi: I siano X i vertici di C I di Kruskal I il taglio (X , V − X ) rispetta A I di Prim I segue dal teorema I che l’arco (u, v ) è sicuro per A I possono essere descritti come specializzazioni dell’algoritmo generico I si basano sul precedente corollario I algoritmi greedy: un arco sicuro è un arco di peso minimo, quindi il più appetibile Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 70 3. Algoritmo di Kruskal 3. Algoritmo di Kruskal applicando la schema generale I mantiene un sottografo non necessariamente connesso (V , A) di un MST I MST_Kruskal(G) (minimal spanning tree, minimo albero ricoprente) A←∅ I all’inizio: tutti i vertici del grafo e nessun arco ordina gli archi in ordine non decrescente di peso I per ogni arco, in ordine non decrescente di costo: for ∀(u, v ) nell’ordine do I se l’arco ha entrambi gli estremi nella stessa componente connessa di (V , A) if (u, v ) è “sicuro” per A then escludilo dalla soluzione A ← A ∪ (u, v ) I altrimenti, basandoti sul corollario I, includilo nella soluzione (fondendo due I che cosa significa “sicuro” per Kruskal? componenti connesse) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 70  3. Algoritmo di Kruskal 3. Simulazione I obiettivo: la costruzione di un particolare albero, ossia un grafo connesso senza cicli I MST_Kruskal(G) A←∅ ordina gli archi in ordine non decrescente di peso for ∀(u, v ) nell’ordine do if (u, v ) non crea ciclo in G(A) = (V , A) then A ← A ∪ (u, v ) Grafo originale. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 21/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 70 3. Simulazione 3. Simulazione Non crea ciclo, incluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 24/ 70  3. Simulazione 3. Simulazione Non crea ciclo, incluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 70 3. Simulazione 3. Simulazione Non crea ciclo, incluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 27/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 28/ 70  3. Simulazione 3. Simulazione Non crea ciclo, incluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 70 3. Simulazione 3. Simulazione Non crea ciclo, incluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 32/ 70  3. Simulazione 3. Simulazione Non crea ciclo, incluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 33/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 34/ 70 3. Simulazione 3. Simulazione Crea ciclo, escluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 35/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 36/ 70  3. Simulazione 3. Simulazione Non crea ciclo, incluso. Crea ciclo, escluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 37/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 38/ 70 3. Simulazione 3. Simulazione Crea ciclo, escluso. Non crea ciclo, incluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 39/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 40/ 70  3. Simulazione 3. Simulazione Non crea ciclo, incluso. Crea ciclo, escluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 41/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 42/ 70 3. Simulazione 3. Simulazione Crea ciclo, escluso. Crea ciclo, escluso. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 43/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 44/ 70  3. Simulazione 3. Simulazione Non crea ciclo, incluso. Risultato finale. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 45/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 46/ 70 3. Complessità dell’algoritmo di Kruskal 3. Struttura dati che rappresenta insiemi disgiunti: operazioni I non può essere valutata se non si conosce la struttura dati usata per I tre operazioni rispondere alla domanda di esistenza del ciclo I creazione di un nuovo insieme il cui unico elemento è x: Make_set(x) I unione di due insiemi che contengono x e y : Union(x, y ) I bisogna memorizzare i vertici delle componenti connesse del sottoinsieme I trovare il rappresentante dell insieme contenente x: Find_set(x) dell albero di copertura in costruzione I una sequenza di n + m operazioni Make_set, Find_set e Union, di cui I una struttura dati per insiemi disgiunti I n sono operazioni di Make_set I collezione S di insiemi dinamici disgiunti (di vertici) I m sono operazioni di union e/o find I ogni insieme identificato da un rappresentante I può essere eseguita su una UnionFind in tempo O((n + m) log n) nel caso peggiore Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 47/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 48/ 70  3. Algoritmo di Kruskal con insiemi disgiunti 3. Complessità nel caso peggiore MST_Kruskal(G) I ordinamento: O(|E| log |E|) A←∅ I operazioni sulla foresta di insiemi disgiunti: O((|V | + |E|) log |V |) for ∀v ∈ V do I il grafo è connesso: O((|V | + |E|) log |V |) = O(|E| log |V |) Make_set(v ) ordina gli archi in ordine non decrescente di peso I totale: O(|E| log |V |) (dato che for ∀(u, v ) ∈ E nell’ordine do O(|E| log |E|) = O(|E| log |V |2 ) = O(|E|2 log |V |) = O(|E| log |V |)) if Find(u)6=Find(v ) then A ← A ∪ (u, v ) Union(u, v ) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 49/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 50/ 70 3. Esempio 3. Esempio 15 B 20 15 B 20 C C A A 7 12 6 7 12 6 D 11 3 D 11 3 1 7 E 1 7 E 4 4 F G F G 10 10 I gli archi in ordine per peso non decrescente: (a, f ), (c, g), (e, g), (c, e), (a, d), I MST non è unico: dipende dal ordine in cui gli archi di peso uguale si (d, f ), (f , g), (d, e), (b, d), (a, b), (b, c) considerano Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 51/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 52/ 70  3. Correttezza dell’algoritmo di Kruskal 4. Algoritmo di Prim I invariante del ciclo: A è un sottoinsieme degli archi di un MST di G: I mantiene un sottografo connesso (V − Q, A) di un MST I l’invariante viene reso vero dall inizializzazione di A come insieme vuoto I all’inizio consiste di un nodo arbitrario: I corpo del ciclo for mantiene l’invariante: I Q contiene tutti i nodi tranne questo nodo iniziale I se l’arco crea un ciclo non viene aggiunto I A è vuoto I se non crea un ciclo allora per corollario I l’arco è “sicuro” e l’invariante viene mantenuto I applica n − 1 volte il seguente passo I all’termine del algoritmo (V , A) è connesso (si può dimostrare per assurdo) I scegli un arco (u, v ) di peso minimo che collega un nodo in V − Q ad un nodo in Q I aggiungilo ad A I togli da Q il vertice a cui porta l’arco Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 53/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 54/ 70 4. Algoritmo di Prim applicando la schema generale 4. Algoritmo di Prim I MST_Prim(G, s) I strategia di Prim: mantenere un sottografo connesso A←∅ I MST_Prim(G, s) Q ← V − {s} A←∅ while Q 6= ∅ do Q ← V − {s} scegli un arco (u, v ) “sicuro” per A while Q 6= ∅ do A ← A ∪ (u, v ) scegli l’arco (u, v ) con peso minimo e u ∈ V − Q, v ∈ Q Q ← Q − {v } A ← A ∪ (u, v ) I che cosa significa “sicuro” per Prim? Q ← Q − {v } Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 55/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 56/ 70  4. Algoritmo di Prim 4. Simulazione I per facilitare la scelta dell’arco successivo memorizziamo per ogni nodo u ∈ Q l’arco più leggero fra V − Q e u I l’attributo π è l’estremità dell’arco in V − Q e d è il suo peso MST_Prim(G, s) Q←V Known: true for ∀v ∈ V do v.d← ∞ se non fa più s.d← 0 parte di Q s.π← nil Cost: d while Q 6= ∅ do Path: π (-1 al u ← nodo con d minimo in Q (tolto da Q) posto di nil) for ∀v ∈ adj[u] do if v ∈ Q e W (u, v ) < v.d then v.d ← W (u, v ) v.π← u Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 57/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 58/ 70 4. Simulazione 4. Simulazione Situazione prima di cominciare il Si sceglie il ciclo. nodo 3. Si Nel ciclo aggiornano si sceglie il nodi 5 e 7. nodo 0 e si aggiornano suoi adiacenti. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 59/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 60/ 70  4. Simulazione 4. Simulazione Si sceglie il Si sceglie il nodo 7. Si nodo 4. Non aggiorna nodo si aggiorna 4. nessun nodo. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 61/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 62/ 70 4. Simulazione 4. Simulazione Si sceglie il Si sceglie il nodo 2. Non nodo 1. Si si aggiorna aggiorna nodo nessun nodo. 5. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 63/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 64/ 70  4. Simulazione 4. Simulazione Si sceglie il nodo 5. Si Si sceglie il aggiorna nodo nodo 6. 6. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 65/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 66/ 70 4. Simulazione 4. Complessità dell’algoritmo di Prim I Q può essere implementata come coda di priorità usando un heap minimo I le priorità sono date dall attributo d I il costo dell algoritmo di Prim è limitato da I costo inizializzazione: O(|V |) I costo delle estrazioni del minimo: O(|V | log |V |) I costo di risistemazione dello heap binario dopo il decremento eventuale delle Situazione chiavi: O(|E| log |V |) finale. I complessità dell algoritmo con: O((|V | + |E|) log |V |) = O(|E| log |V |) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 67/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 68/ 70  4. Correttezza dell’algoritmo di Prim 4. Correttezza dell’algoritmo di Prim I due invarianti del ciclo: I dimostriamo il seguente invariante: (V − Q, {(t.π, t) : t 6= s, t ∈ V − Q}) è un I invariante I: ∀t ∈ Q : t.π 6= nil ⇒ t.π ∈ V − Q sottografo di un MST: I invariante II: ∀t ∈ Q : (t.π, t) un arco di peso minimo tra t e un vertice di V − Q I inizialmente vero I il corpo del ciclo mantiene l’invariante: I si dimostrano facilmente esaminando l’inizializzazione e il corpo del ciclo I sia u il vertice estratto da Q I per invariante I e II, l’arco (u.π, u) è un arco leggero che unisce le componenti connesse (V − Q, A) e ({u}, ∅) I allora, per il Corollario 1, è un arco sicuro per A Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 69/ 70 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 70/ 70