2.3 La proprietà del taglio e la proprietà del ciclo¶
Parte 2 · Alberi e cammini · Capitolo 2 · Capitolo 2: Alberi ricoprenti · Dispensa, volume 2 (PDF) · Slide · Esercizi: Alberi ricoprenti · App: Alberi ricoprenti minimi: Kruskal e Prim
Teorema 2.6: proprietà del taglio
Sia \(G=(V,E)\) un grafo connesso con pesi \(w_e\), e sia \(F \subseteq E\) contenuto in qualche albero ricoprente di costo minimo. Sia \(\delta(S)\) un taglio con \(F \cap \delta(S)=\emptyset\), e sia \(e\) uno spigolo di peso minimo in \(\delta(S)\).
-
(a) \(F \cup \{e\}\) è contenuto in qualche albero ricoprente di costo minimo.
-
(b) Se \(w_e<w_f\) per ogni \(f \in \delta(S) \setminus \{e\}\), allora \(e\) appartiene a ogni albero ricoprente di costo minimo.
Dimostrazione
Sia \(T^\star\) un albero ricoprente di costo minimo con \(F \subseteq T^\star\); per (b), sia \(T^\star\) un qualsiasi albero ricoprente di costo minimo e \(F=\emptyset\). Se \(e \in T^\star\) non c'è niente da dimostrare; sia \(e \notin T^\star\).
-
Il ciclo fondamentale \(C(T^\star,e)\) contiene lo spigolo \(e\) di \(\delta(S)\), quindi contiene un altro spigolo \(f \in \delta(S)\), \(f \neq e\) (Lemma 2.3). Tutti i suoi spigoli diversi da \(e\) stanno in \(T^\star\), quindi \(f \in T^\star\); e \(f \notin F\), perché \(F \cap \delta(S)=\emptyset\).
-
Per il Lemma 2.5, \(T'=T^\star \cup \{e\} \setminus \{f\}\) è un albero ricoprente, con \(w(T')=w(T^\star)+w_e-w_f\).
-
(a) \(e\) ha peso minimo in \(\delta(S)\), quindi \(w_e \le w_f\) e \(w(T') \le w(T^\star)\): \(T'\) è un albero ricoprente di costo minimo che contiene \(F \cup \{e\}\).
-
(b) Qui \(w_e<w_f\) e \(w(T')<w(T^\star)\), contro l'ottimalità di \(T^\star\): quindi \(e \in T^\star\). □
Teorema 2.7: proprietà del ciclo
Sia \(G=(V,E)\) un grafo connesso con pesi \(w_e\), sia \(C\) un ciclo di \(G\) ed \(e\) uno spigolo di peso massimo in \(C\).
-
(a) Qualche albero ricoprente di costo minimo non contiene \(e\).
-
(b) Se \(w_e>w_f\) per ogni \(f \in C \setminus \{e\}\), allora nessun albero ricoprente di costo minimo contiene \(e\).
Dimostrazione
Sia \(T^\star\) un albero ricoprente di costo minimo con \(e \in T^\star\) (se non ce n'è nessuno, entrambe le affermazioni valgono), e sia \(\delta(S_e)\) il taglio fondamentale di \(e\) in \(T^\star\).
-
Il ciclo \(C\) contiene lo spigolo \(e\) di \(\delta(S_e)\), quindi contiene un altro spigolo \(f \in \delta(S_e)\) (Lemma 2.3); \(f \notin T^\star\), perché \(e\) è l'unico spigolo di \(T^\star\) nel suo taglio fondamentale.
-
Per il Lemma 2.5(2), \(T'=T^\star \cup \{f\} \setminus \{e\}\) è un albero ricoprente, con \(w(T')=w(T^\star)+w_f-w_e\).
-
(a) \(w_f \le w_e\), quindi \(T'\) è un albero ricoprente di costo minimo senza \(e\). (b) \(w_f<w_e\) darebbe \(w(T')<w(T^\star)\), una contraddizione: nessun albero ricoprente di costo minimo contiene \(e\). □
Esempio 2.4: le due proprietà sul grafo di riferimento
-
Proprietà del taglio. Lo spigolo \(\{3,4\}\), di peso \(5\), è l'unico spigolo più leggero di \(\delta(\{1,2,3\})=\{\{2,4\},\{3,4\},\{3,5\}\}\), con pesi \(6,5,8\): appartiene a ogni albero ricoprente di costo minimo. Allo stesso modo, \(\{5,6\}\) è l'unico spigolo più leggero di \(\delta(\{6\})\).
-
Proprietà del ciclo. Lo spigolo \(\{1,2\}\) è l'unico spigolo più pesante del ciclo \(1,2,3\) (pesi \(4,3,1\)), e \(\{3,5\}\) è l'unico spigolo più pesante del ciclo \(3,4,5\) (pesi \(5,2,8\)): nessun albero ricoprente di costo minimo li contiene. I cicli \(2,3,4\) e \(4,5,6\) escludono \(\{2,4\}\) e \(\{4,6\}\).
-
I quattro spigoli esclusi lasciano esattamente i \(5\) spigoli di \(\tilde{F}\): le due proprietà da sole dimostrano che \(\tilde{F}\) è l'unico albero ricoprente di costo minimo.
2.3.1 Condizioni di ottimalità¶
Teorema 2.8: condizioni di ottimalità
Sia \(T\) un albero ricoprente di un grafo connesso \(G=(V,E)\) con pesi \(w_e\). Le seguenti affermazioni sono equivalenti:
-
(i) \(T\) è un albero ricoprente di costo minimo;
-
(ii) condizione del ciclo: per ogni \(e \notin T\), \(w_e \ge w_f\) per ogni spigolo \(f\) di \(C(T,e)\);
-
(iii) condizione del taglio: per ogni \(e \in T\), \(w_e \le w_f\) per ogni spigolo \(f\) del taglio fondamentale di \(e\).
Dimostrazione
Dimostriamo (i)\(\Rightarrow\)(iii)\(\Rightarrow\)(ii)\(\Rightarrow\)(i).
-
(i)\(\Rightarrow\)(iii). Se \(f\) attraversa il taglio fondamentale di \(e \in T\) con \(w_f<w_e\), allora \(T \cup \{f\} \setminus \{e\}\) è un albero ricoprente (Lemma 2.5(2)) più leggero di \(T\).
-
(iii)\(\Rightarrow\)(ii). Siano \(e \notin T\) e \(f \in C(T,e)\), \(f \neq e\). Il cammino di \(T\) fra gli estremi di \(e\) usa \(f\), ed è unico, quindi togliere \(f\) li separa: \(e\) attraversa il taglio fondamentale di \(f\), e \(w_f \le w_e\) per (iii).
(ii)\(\Rightarrow\)(i). Fra gli alberi ricoprenti di costo minimo, sia \(T^\star\) uno con il massimo numero di spigoli in comune con \(T\), e supponiamo \(T^\star \neq T\).
-
Prendiamo \(e \in T^\star \setminus T\), e sia \(\delta(S_e)\) il suo taglio fondamentale in \(T^\star\). Il ciclo \(C(T,e)\) contiene \(e\), quindi contiene un altro spigolo \(f \in \delta(S_e)\) (Lemma 2.3), con \(f \in T\) e \(f \notin T^\star\).
-
Per il Lemma 2.5(2), \(T'=T^\star \cup \{f\} \setminus \{e\}\) è un albero ricoprente, e \(w_f \le w_e\) per (ii) applicata a \(e \notin T\). Quindi \(w(T') \le w(T^\star)\).
-
\(T'\) è un albero ricoprente di costo minimo con uno spigolo in più in comune con \(T\): una contraddizione. Quindi \(T=T^\star\). □
Esempio 2.5: certificare l'albero ottimo
Per l'albero \(\tilde{F}\) dell'Esempio 2.2, i quattro spigoli fuori dall'albero e i loro cicli fondamentali sono:
| spigolo \(e \notin \tilde{F}\) | \(C(\tilde{F},e)\) | pesi degli spigoli dell'albero nel ciclo |
|---|---|---|
| \(\{1,2\}\), \(w=4\) | \(1,3,2,1\) | \(1,~3\) |
| \(\{2,4\}\), \(w=6\) | \(2,3,4,2\) | \(3,~5\) |
| \(\{3,5\}\), \(w=8\) | \(3,4,5,3\) | \(5,~2\) |
| \(\{4,6\}\), \(w=9\) | \(4,5,6,4\) | \(2,~7\) |
Ogni spigolo fuori dall'albero è pesante almeno quanto gli spigoli dell'albero del suo ciclo: per il Teorema 2.8 l'albero è ottimo, senza enumerare i \(55\) alberi ricoprenti.
Esempio 2.6: migliorare un albero che non è ottimo
L'albero della visita in ampiezza \(T=\{\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,6\}\}\), di peso \(28\), viola la condizione del ciclo. Per \(e=\{4,5\}\), di peso \(2\), il ciclo fondamentale \(4,2,1,3,5,4\) contiene \(\{2,4\}\), \(\{1,2\}\) e \(\{3,5\}\), di pesi \(6,4,8\).
-
Togliendo il più pesante dei tre, \(\{3,5\}\), e aggiungendo \(\{4,5\}\) si ottiene un albero ricoprente di peso \(28+2-8=22\).
-
La dimostrazione del Teorema 2.8 diventa un algoritmo: ripetere lo scambio finché uno spigolo viola la condizione. Gli algoritmi delle prossime sezioni sono più veloci.
Lo spigolo più leggero di un taglio appartiene a qualche albero ricoprente di costo minimo, e lo spigolo più pesante di un ciclo si può lasciare fuori. Un albero ricoprente è ottimo se e solo se ogni spigolo fuori dall'albero è il più pesante del suo ciclo fondamentale.
Avanti: 2.4 L'algoritmo greedy generico