Gomory – Hu strom - Gomory–Hu tree

v kombinatorická optimalizace, Gomory – Hu strom[1] neorientovaného grafu s kapacitami je vážený strom to představuje minimum s-t řezy pro všechny s-t páry v grafu. Strom Gomory – Hu může být sestaven v |PROTI | − 1 maximální průtok výpočty.

Definice

Nechat G = ((PROTIG, EG), C) být neorientovaný graf s C(u,proti) je kapacita okraje (u,proti).

Označte minimální kapacitu s-t snížit o λSvatý pro každého s, t ∈ PROTIG.
Nechat T = (PROTIG, ET) být strom, označit sadu hran v s-t cesta PSvatý pro každého s, t ∈ PROTIG.

Pak T se říká, že je Gomory – Hu strom z G, pokud pro každého s, t ∈ PROTIG

λSvatý = mine∈PSvatý C(SE, TE),

kde

  1. SE, TE ⊆ PROTIG jsou dvě spojené komponenty T∖{E}, a tudíž (SE, TE) pro muže s-t zastřihnout G.
  2. C(SE, TE) je kapacita výřezu G.

Algoritmus

Algoritmus Gomory – Hu

Vstup: Vážený neorientovaný graf G = ((PROTIG, EG), C)
Výstup: Strom Gomory – Hu T = (PROTIT, ET).
1 set PROTIT = {PROTIG} a ET = ∅.
2. Vyberte některé X∈PROTIT s | X | ≥ 2, pokud je X existuje. V opačném případě přejděte ke kroku 6.
3. Pro každou připojenou komponentu C = (PROTIC, EC) v T∖X. Nechat SC = ∪protiT∈VC protiT. Nechat S = { SC | C je připojená součást v T∖X}.
Smluvte komponenty, které chcete vytvořit G' = ((PROTIG', EG'), C'), kde
PROTIG' = X ∪ S.
EG' = EG|X × X ∪ {(u, SC) ∈ X×S | (u,proti)∈EG pro některé proti∈SC} ∪ {(SC1, SC2) ∈ S ×S | (u,proti)∈EG pro některé u∈SC1 a proti∈SC2}.
C' : PROTIG'×PROTIG'→R+ je kapacitní funkce definovaná jako,
  1. pokud (u,SC)∈EG|X × S., C'(u,SC) = Σv∈SC: (u, v) ∈EGC(u,proti),
  2. pokud (SC1,SC2)∈EG|S × S, C'(SC1,SC2) = Σ(u, v) ∈EG: u∈SC1∧v∈SC2 C(u,proti),
  3. C'(u,proti) = C(u,proti) v opačném případě.
4. Vyberte dva vrcholy s, t ∈ X a najít minimum s-t střih (A',B') v G'.
Soubor A = (∪SC∈A'∩S SC) ∪ (A' ∩ X) a B = (∪SC∈B'∩S SC) ∪ (B' ∩ X).
5. Nastavit PROTIT = (PROTIT∖X) ∪ {A ∩ X, B ∩ X}.
Pro každého E = (X, Y) ∈ ET dělat
Li Y ⊂ A, nastavit E' = (A ∩ X, Y), jinak nastaveno E' = (B ∩ X, Y).
Soubor ET = (ET∖{E}) ∪ {E'} a w(E') = w(E).
Soubor ET = ET ∪ {(A∩X, B∩X)}.
Soubor w((A∩X, B∩X)) = C'(A', B').
Přejděte na krok 2.
6. Vyměňte každý {proti} ∈ PROTIT podle proti a každý ({u},{proti}) ∈ ET od (u,proti). Výstup T.

Analýza

Za použití submodulární vlastnost kapacitní funkce C, jeden má

C(X) + C(Y) ≥ C(X ∩ Y) + C(X ∪ Y).

Pak je možné ukázat, že minimální s-t zastřihnout G„je také minimum s-t zastřihnout G pro všechny s, t ∈ X.

Ukázat to pro všechny (P, Q) ∈ ET, w(P,Q) = λpq pro některé p ∈ P, q ∈ Q v celém algoritmu využívá jeden následující lemma,

Pro všechny i, j, k v PROTIG, λik ≥ min (λij, λjk).

Lemma může být znovu použita opakovaně, aby se ukázalo, že výstup T uspokojuje vlastnosti stromu Gomory – Hu.

Příklad

Následuje simulace Gomoryho-Huova algoritmu, kde

  1. zelená kruhy jsou vrcholy T.
  2. Červené a modrý kruhy jsou vrcholy G'.
  3. Šedá jsou zvoleny vrcholy s a t.
  4. Červené a modrý zbarvení představuje s-t střih.
  5. přerušovaný hrany jsou s-t cut-set.
  6. A je množina vrcholů zakroužkovaných dovnitř Červené a B je množina vrcholů zakroužkovaných dovnitř modrý.
G'T
Gomory – Hu G. svGomory – Hu T.svg
1 set PROTIT = {PROTIG} = {{0, 1, 2, 3, 4, 5}} a ET = ∅.
2. Od té doby PROTIT má pouze jeden vrchol, vyberte X = PROTIG = {0, 1, 2, 3, 4, 5}. Všimněte si, že | X | = 6 ≥ 2.
1.Gomory – Hu Gp1.svgGomory – Hu T1.svg
3. Od té doby T∖X = ∅, neexistuje žádná kontrakce, a proto G' = G.
4. Vyberte s = 1 a t = 5. Minimum s-t střih (A', B') je ({0, 1, 2, 4}, {3, 5}) s C'(A', B') = 6.
Soubor A = {0, 1, 2, 4} a B = {3, 5}.
5. Nastavit PROTIT = (PROTIT∖X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3, 5} }.
Soubor ET = { ({0, 1, 2, 4}, {3, 5}) }.
Soubor w( ({0, 1, 2, 4}, {3, 5}) ) = C'(A', B') = 6.
Přejděte na krok 2.
2. Vyberte X = {3, 5}. Všimněte si, že | X | = 2 ≥ 2.
2.Gomory – Hu Gp2.svgGomory – Hu T2.svg
3. {0, 1, 2, 4} je připojená součást v T∖X a tudíž S = { {0, 1, 2, 4} }.
Smlouva {0, 1, 2, 4} k vytvoření G', kde
C'( (3, {0, 1, 2 ,4}) ) = C( (3, 1) ) + C( (3, 4) ) = 4.
C'( (5, {0, 1, 2, 4}) ) = C( (5, 4) ) = 2.
C'( (3, 5)) = C( (3, 5) ) = 6.
4. Vyberte s = 3, t = 5. Minimum s-t střih (A', B') v G'is ({{0, 1, 2, 4}, 3}, {5}) with C'(A', B') = 8.
Soubor A = {0, 1, 2, 3, 4} a B = {5}.
5. Nastavit PROTIT = (PROTIT∖X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3}, {5} }.
Od té doby (X, {0, 1, 2, 4}) ∈ ET a {0, 1, 2, 4} ⊂ A, nahraďte jej (A ∩ X, Y) = ({3}, {0, 1, 2 ,4}).
Soubor ET = {({3}, {0, 1, 2, 4}), ({3}, {5})} s
w(({3}, {0, 1, 2 ,4})) = w((X, {0, 1, 2, 4})) = 6.
w(({3}, {5})) = C'(A', B') = 8.
Přejděte na krok 2.
2. Vyberte X = {0, 1, 2, 4}. Všimněte si, že | X | = 4 ≥ 2.
3.Gomory – Hu Gp3.svgGomory – Hu T3.svg
3. {{3}, {5}} je připojená součást T∖X a tudíž S = { {3, 5} }.
Formální smlouva {3, 5} G', kde
C'( (1, {3, 5}) ) = C( (1, 3) ) = 3.
C'( (4, {3, 5}) ) = C( (4, 3) ) + C( (4, 5) ) = 3.
C'(u,proti) = C(u,proti) pro všechny u,proti ∈ X.
4. Vyberte s = 1, t = 2. Minimum s-t střih (A', B') v G'is ({1, {3, 5}, 4}, {0, 2}) with C'(A', B') = 6.
Soubor A = {1, 3, 4, 5} a B = {0, 2}.
5. Nastavit PROTIT = (PROTIT∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1, 4}, {0, 2} }.
Od té doby (X, {3}) ∈ ET a {3} ⊂ A, nahraďte jej (A ∩ X, Y) = ({1, 4}, {3}).
Soubor ET = {({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4})} s
w(({1, 4}, {3})) = w((X, {3})) = 6.
w(({0, 2}, {1, 4})) = C'(A', B') = 6.
Přejděte na krok 2.
2. Vyberte X = {1, 4}. Všimněte si, že | X | = 2 ≥ 2.
4.Gomory – Hu Gp4.svgGomory – Hu T4.svg
3. {{3}, {5}}, {{0, 2}} jsou připojené komponenty T∖X a tudíž S = { {0, 2}, {3, 5} }
Uzavřete smlouvu {0, 2} a {3, 5} G', kde
C'( (1, {3, 5}) ) = C( (1, 3) ) = 3.
C'( (4, {3, 5}) ) = C( (4, 3) ) + C( (4, 5) ) = 3.
C'( (1, {0, 2}) ) = C( (1, 0) ) + C( (1, 2) ) = 2.
C'( (4, {0, 2}) ) = C( (4, 2) ) = 4.
C'(u,proti) = C(u,proti) pro všechny u,proti ∈ X.
4. Vyberte s = 1, t = 4. Minimum s-t střih (A', B') v G'is ({1, {3, 5}}, {{0, 2}, 4}) with C'(A', B') = 7.
Soubor A = {1, 3, 5} a B = {0, 2, 4}.
5. Nastavit PROTIT = (PROTIT∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {0, 2}, {1}, {4} }.
Od té doby (X, {3}) ∈ ET a {3} ⊂ A, nahraďte jej (A ∩ X, Y) = ({1}, {3}).
Od té doby (X, {0, 2}) ∈ ET a {0, 2} ⊂ B, nahraďte jej (B ∩ X, Y) = ({4}, {0, 2}).
Soubor ET = {({1}, {3}), ({3}, {5}), ({4}, {0, 2}), ({1}, {4})} s
w(({1}, {3})) = w((X, {3})) = 6.
w(({4}, {0, 2})) = w((X, {0, 2})) = 6.
w(({1}, {4})) = C'(A', B') = 7.
Přejděte na krok 2.
2. Vyberte X = {0, 2}. Všimněte si, že | X | = 2 ≥ 2.
5.Gomory – Hu Gp5.svgGomory – Hu T5.svg
3. {{1}, {3}, {4}, {5}} je připojená součást T∖X a tudíž S = { {1, 3, 4, 5} }.
Formální smlouva {1, 3, 4, 5} G', kde
C'( (0, {1, 3, 4, 5}) ) = C( (0, 1) ) = 1.
C'( (2, {1, 3, 4, 5}) ) = C( (2, 1) ) + C( (2, 4) ) = 5.
C'( (0, 2) ) = C( (0, 2) ) = 7.
4. Vyberte s = 0, t = 2. Minimum s-t střih (A', B') v G'is ({0}, {2, {1, 3, 4, 5}}) with C'(A', B') = 8.
Soubor A = {0} a B = {1, 2, 3 ,4 ,5}.
5. Nastavit PROTIT = (PROTIT∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1}, {4}, {0}, {2} }.
Od té doby (X, {4}) ∈ ET a {4} ⊂ B, nahraďte jej (B ∩ X, Y) = ({2}, {4}).
Soubor ET = {({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2} )} s
w(({2}, {4})) = w((X, {4})) = 6.
w(({0}, {2})) = C'(A', B') = 8.
Přejděte na krok 2.
2. Neexistuje X∈PROTIT s | X | ≥ 2. Proto přejděte ke kroku 6.
6.

Gomory – Hu output.svg

6. Vyměňte PROTIT = {{3}, {5}, {1}, {4}, {0}, {2}} od {3, 5, 1, 4, 0, 2}.
Nahradit ET = {({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2} )} od {(1, 3), (3, 5), (2, 4), (1, 4), (0, 2)}.
Výstup T. Všimněte si, že přesně |PROTI | - 1 = 6 - 1 = provede se výpočet min. Řezu 5krát.

Implementace: Sekvenční a paralelní

Gusfieldův algoritmus lze použít k nalezení stromu Gomory-Hu bez jakékoli kontrakce vrcholů ve stejné složitosti běhového času, což zjednodušuje implementaci konstrukce stromu Gomory-Hu.[2]

Andrew V. Goldberg a K. Tsioutsiouliklis implementovali algoritmus Gomory-Hu a Gusfieldův algoritmus a provedli experimentální vyhodnocení a srovnání.[3]

Cohen a kol. reportovat výsledky dvou paralelních implementací Gusfieldova algoritmu pomocí OpenMP a MPI.[4]

Související pojmy

v rovinné grafy, strom Gomory – Hu je duální na minimální hmotnost základ cyklu, v tom smyslu, že řezy stromu Gomory – Hu jsou dvojí ve srovnání se sbírkou cyklů v duální graf které tvoří základ cyklu minimální hmotnosti.[5]

Viz také

Reference

  1. ^ Gomory, R. E.; Hu, T. C. (1961). "Toky více terminálových sítí". Časopis Společnosti pro průmyslovou a aplikovanou matematiku. 9 (4): 551–570. doi:10.1137/0109047.
  2. ^ Gusfield, Dan (1990). "Velmi jednoduché metody pro analýzu toku párů v síti". SIAM J. Comput. 19 (1): 143–155. doi:10.1137/0219009.
  3. ^ Goldberg, A. V .; Tsioutsiouliklis, K. (2001). "Algoritmy řezaných stromů: experimentální studie". Journal of Algorithms. 38 (1): 51–83. doi:10.1006 / jagm.2000.1136.
  4. ^ Cohen, J .; L. A. Rodrigues; F. Silva; R. Carmo; A. Guedes; E. P. Duarte Jr. (2011). "Paralelní implementace Gusfieldova algoritmu řezaného stromu". Přednášky v informatice (LNCS). 7016. Springer. 7016 (11. mezinárodní konference Algoritmy a architektury pro paralelní zpracování (ICA3PP)): 258–269. doi:10.1007/978-3-642-24650-0_22. ISBN  978-3-642-24649-4. ISSN  0302-9743.
  5. ^ Hartvigsen, D .; Mardon, R. (1994). "Problém min. Řezu všech párů a problém minimálního základu cyklu na rovinných grafech". SIAM J. Diskrétní matematika. 7 (3): 403–418. doi:10.1137 / S0895480190177042..