Vai al contenuto

2.4 L'algoritmo greedy generico

Parte 2 · Alberi e cammini · Capitolo 2 · Capitolo 2: Alberi ricoprenti · Dispensa, volume 2 (PDF) · Esercizi: Alberi ricoprenti · App: Alberi ricoprenti minimi: Kruskal e Prim

  • La proprietà cut suggerisce di costruire uno albero ricoprente minimo un lato alla volta: l'insieme corrente \(F\) è sempre contenuto in un albero di copertura minimo e il lato successivo è il lato più leggero di un taglio non attraversato da \(F\).

Algoritmo: Algoritmo greedy generico per MST

Input: un grafo connesso non orientato \(G=(V,E)\) con pesi \(w_e\)
Output: un albero di copertura minimo \(F\)
1Passaggio 0 (inizializzazione). Imposta \(F:=\emptyset\).
2Passaggio 1 (test di arresto). Se \(|F|=n-1\), STOP.
3Passaggio 2 (aumento). Scegli un taglio \(\delta(S)\) con \(F \cap \delta(S)=\emptyset\) e aggiungi a \(F\) un lato di peso minimo in \(\delta(S)\). Vai al passaggio 1.

Teorema 2.9: correttezza dell'algoritmo greedy generico

Ad ogni iterazione dell'algoritmo greedy generico esiste un taglio come nel passaggio 2 che non è vuoto e \(F\) è contenuto in un albero di copertura minimo. Alla fine, \(F\) è un albero ricoprente minimo.

Dimostrazione

Per induzione sulle iterazioni; \(F=\emptyset\) è contenuto in ogni albero ricoprente minimo.

  1. Se \(|F|<n-1\), il grafo \((V,F)\) è una foresta (un sottoinsieme di un albero) con componenti \(n-|F| \ge 2\). Lascia che \(S\) sia uno di essi: nessun lato di \(F\) attraversa \(\delta(S)\) e \(\delta(S) \neq \emptyset\) perché \(G\) è connesso.

  2. Per la proprietà di taglio (Teorema 2.6(a)), il nuovo insieme \(F \cup \{e\}\) è ancora contenuto in un albero di copertura minimo.

  3. Quando \(|F|=n-1\), \(F\) è contenuto in uno albero ricoprente minimo \(T^\star\) con lati \(n-1\), quindi \(F=T^\star\). □

  • Il lato aggiunto \(e=\{u,v\}\) ha \(u \in S\) e \(v \notin S\) e nessun lato di \(F\) incrocia \(\delta(S)\): \(u\) e \(v\) sono in diversi componenti di \((V,F)\), quindi \(e\) non chiude un ciclo.

  • Gli algoritmi di Kruskal e di Prim sono due modi per scegliere il taglio nello Step 2.

Aggiungendo, \(n-1\) volte, il lato più leggero di un taglio non attraversato dai lati correnti costruisce un albero ricoprente minimo.

Avanti: 2.5 Algoritmo di Kruskal