Gomory–Hu-träd

I kombinatorisk optimering är Gomory -Hu-trädet för en oriktad graf med kapacitet ett viktat träd som representerar minsta s - t - snitt för alla s - t -par i grafen. Gomory–Hu-trädet kan konstrueras i | V | − 1 maximalt flödesberäkningar.

Definition

Låt G = (( V G , E G ), c ​​) vara en oriktad graf där c ( u , v ) är kapaciteten för kanten ( u , v ) respektive.

Ange den minsta kapaciteten för en s - t skär med λ st för varje s , t ∈ V G.
Låt T = ( V G , E T ) vara ett träd, beteckna uppsättningen av kanter i en st - t bana med P st för varje s , t ∈ V G .

Då sägs T vara ett Gomory–Hu-träd av G , om för varje s , t ∈ V G

λ st = min e∈P st c ( S e , T e ),

var

  1. S e , T e ⊆ V G är de två sammankopplade komponenterna i T ∖{ e } och bildar således ( S e , T e ) ett s - t snitt i G .
  2. c ( S e , T e ) är kapaciteten för snittet i G.

Algoritm

Gomory–Hu Algoritm

Ingång : En viktad oriktad graf G = (( V G , E G ), c ​​)
Utdata : A Gomory–Hu-träd T = ( V T , E T ).
1. Ställ in V T = { V G } och E T = ∅.
2. Välj några X ∈ V T med | X | ≥ 2 om ett sådant X finns. Gå annars till steg 6.
3. För varje ansluten komponent C = ( V C , E C ) i T ∖ X . Låt S C = ∪ v T ∈V C v T . Låt S = { SC | C är en ansluten komponent i T ∖ X }.
Dra ihop komponenterna så att de bildar G ' = (( V G' , E G' ), c ​​'), där
VG ' = X ∪ S .
E G' = E G | X×X ∪ {( u , S C ) ∈ X × S | ( u , v )∈ E G för vissa v ∈ S C } ∪ {( S C1 , S C2 ) ∈ S× S | ( u , v )∈ E G för vissa u∈ S C1 och v ∈ S C2 }.
c ' : V G' × V G' → R + är kapacitetsfunktionen definierad som,
  1. om ( u , S C )∈ E G | X×S , c '( u , S C ) = Σ v∈S C :(u,v)∈E Gc ( u , v ),
  2. om ( S C1 , S C2 )∈ E G | S×S , c '( S C1 , S C2 ) = Σ (u,v)∈E G :u∈S C1 ∧v∈S C2c ( u , v ) ,
  3. c '( u , v ) = c ( u , v ) annars.
4. Välj två hörn s , t ∈ X och hitta ett minimum s - t cut ( A ', B ') i G '.
Set A = (∪ S C ∈ A '∩ S S C ) ∪ ( A ' ∩ X ) och B = (∪ S C ∈ B '∩ S S C ) ∪ ( B ' ∩ X ).
5. Ställ in V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X }.
För varje e = ( X , Y ) ∈ E T do
Om Y ⊂ A , sätt e ' = ( A ∩ X , Y ), annars sätt e ' = ( B ∩ X , Y ).
Ställ E T = ( E T ∖{ e }) ∪ { e '} och w ( e ') = w ( e ).
Ställ in E T = E T ∪ {( A ∩ X , B ∩ X )}.
Ställ in w (( A ∩ X , B ∩ X )) = c '( A ', B ').
Gå till steg 2.
6. Ersätt varje { v } ∈ V T med v och varje ({ u },{ v }) ∈ E T med ( u , v ). Utgång T .

Analys

Genom att använda den submodulära egenskapen för kapacitetsfunktionen c har man

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

Då kan det visas att det minsta s - t- snittet i G ' också är ett minsta s - t -snittet i G för alla s , t ∈ X.

För att visa att för alla ( P , Q ) ∈ E T , w ( P , Q ) = λ pq för vissa p ∈ P , q ∈ Q genom hela algoritmen, använder man sig av följande Lemma,

För varje i , j , k i VG , λ ik ≥ min(λ ij , λ jk ) .

Lemma kan användas igen upprepade gånger för att visa att utgången T uppfyller egenskaperna hos ett Gomory-Hu-träd.

Exempel

Följande är en simulering av Gomory–Hu:s algoritm, där

  1. gröna cirklar är hörn på T .
  2. röda och blå cirklar är hörn i G '.
  3. grå hörn är de valda s och t .
  4. röd och blå färg representerar s - t cut.
  5. streckade kanter är s - t cut-set.
  6. A är uppsättningen av hörn inringade i rött och B är uppsättningen av hörn inringade i blått .
G ' T
Gomory–Hu G.svg Gomory–Hu T.svg
1. Ställ in V T = { V G } = { {0, 1, 2, 3, 4, 5} } och E T = ∅.
2. Eftersom V T bara har en vertex, välj X = V G = {0, 1, 2, 3, 4, 5}. Observera att | X | = 6 ≥ 2.
1. Gomory–Hu Gp1.svg Gomory–Hu T1.svg
3. Eftersom T ∖ X = ∅ finns ingen kontraktion och därför G ' = G .
4. Välj s = 1 och t = 5. Minsta s - t cut ( A ', B ') är ({0, 1, 2, 4}, {3, 5}) med c '( A ', B ') = 6.
Ange A = {0, 1, 2, 4} och B = {3, 5}.
5. Ställ in V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X } = { {0, 1, 2, 4}, {3, 5} }.
Ställ in E T = { ({0, 1, 2, 4}, {3, 5}) }.
Ställ in w ( ({0, 1, 2, 4}, {3, 5}) ) = c '( A ', B ') = 6.
Gå till steg 2.
2. Välj X = {3, 5}. Observera att | X | = 2 ≥ 2.
2. Gomory–Hu Gp2.svg Gomory–Hu T2.svg
3. {0, 1, 2, 4} är ​​den anslutna komponenten i T ∖ X och alltså S = { {0, 1, 2, 4} }.
Dra ihop {0, 1, 2, 4} för att bilda G ', där
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. Välj s = 3, t = 5. Minsta s - t cut ( A ', B ') i G ' är ( {{0, 1, 2, 4}, 3}, {5} ) med c '( A ', B ') = 8.
Set A = {0, 1, 2, 3, 4} och B = {5}.
5. Ställ in V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X } = { {0, 1, 2, 4}, {3}, {5} }.
Eftersom ( X , {0, 1, 2, 4}) ∈ E T och {0, 1, 2, 4} ⊂ A , ersätt det med ( A ∩ X , Y ) = ({3}, {0, 1 2,4}).
Ställ in E T = { ({3}, {0, 1, 2 ,4}), ({3}, {5}) } med w
( ({3}, {0, 1, 2 ,4})) = w (( X , {0, 1, 2, 4})) = 6.
w (({3}, {5})) = c '( A ', B ') = 8.
Gå till steg 2.
2. Välj X = {0, 1, 2, 4}. Observera att | X | = 4 ≥ 2.
3. Gomory–Hu Gp3.svg Gomory–Hu T3.svg
3. { {3}, {5} } är den anslutna komponenten i T ∖ X och därmed S = { {3, 5} }.
Dra ihop {3, 5} för att bilda G ', där
c '( (1, {3, 5}) ) = c ( (1, 3) ) = 3.
c '( (4, {3, 5}) ) = c ( (4, 3) ) + c ( (4, 5) ) = 3.
c '( u , v ) = c ( u , v ) för alla u , v ∈ X .
4. Välj s = 1, t = 2. Minsta s - t cut ( A ', B ') i G ' är ( {1, {3, 5}, 4}, {0, 2} ) med c ' ( A ', B ') = 6.
Set A = {1, 3, 4, 5} och B = {0, 2}.
5. Ställ in V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X } = { {3}, {5}, {1, 4}, {0, 2} }.
Eftersom ( X , {3}) ∈ E T och {3} ⊂ A , ersätt det med ( A ∩ X , Y ) = ({1, 4}, {3}).
Ställ in E T = { ({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4}) } med w (({1,
4 } , {3})) = w (( X , {3})) = 6.
w (({0, 2}, {1, 4})) = c '( A ', B ') = 6.
Gå till steg 2.
2. Välj X = {1, 4}. Observera att | X | = 2 ≥ 2.
4. Gomory–Hu Gp4.svg Gomory–Hu T4.svg
3. { {3}, {5} }, { {0, 2} } är de anslutna komponenterna i T ∖ X och därmed S = { {0, 2}, {3, 5} }
Dra ihop {0, 2} och {3, 5} för att bilda G ', där
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 , v ) = c ( u , v ) för alla u , v ∈ X .
4. Välj s = 1, t = 4. Minsta s - t cut ( A ', B ') i G ' är ( {1, {3, 5}}, {{0, 2}, 4} ) med c '( A ', B ') = 7.
Set A = {1, 3, 5} och B = {0, 2, 4}.
5. Ställ in V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X } = { {3}, {5}, {0, 2}, {1}, {4} }.
Eftersom ( X , {3}) ∈ E T och {3} ⊂ A , ersätt det med ( A ∩ X , Y ) = ({1}, {3}).
Eftersom ( X , {0, 2}) ∈ E T och {0, 2} ⊂ B , ersätt det med ( B ∩ X , Y ) = ({4}, {0, 2}).
Ställ in E T = { ({1}, {3}), ({3}, {5}), ({4}, {0, 2}), ({1}, {4}) } med
w ( ({1}, {3})) = w (( X , {3})) = 6.
w (({4}, {0, 2})) = w (( X , {0, 2}) ) = 6.
w (({1}, {4})) = c '( A ', B ') = 7.
Gå till steg 2.
2. Välj X = {0, 2}. Observera att | X | = 2 ≥ 2.
5. Gomory–Hu Gp5.svg Gomory–Hu T5.svg
3. { {1}, {3}, {4}, {5} } är den anslutna komponenten i T ∖ X och alltså S = { {1, 3, 4, 5} }.
Dra ihop {1, 3, 4, 5} för att bilda G ', där
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. Välj s = 0, t = 2. Minsta s - t- snitt ( A ', B ') i G ' är ( {0}, {2, {1, 3, 4, 5}} ) med c '( A ', B ') = 8.
Set A = {0} och B = {1, 2, 3 ,4 ,5}.
5. Ställ in V T = ( V T ∖ X ) ∪ { A ∩ X , B ∩ X } = { {3}, {5}, {1}, {4}, {0}, {2} }.
Eftersom ( X , {4}) ∈ E T och {4} ⊂ B , ersätt det med ( B ∩ X , Y ) = ({2}, {4}).
Ange E T = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } med
w (({2}, {4})) = w (( X , {4})) = 6.
w (({0}, {2})) = c '( A ' , B ') = 8.
Gå till steg 2.
2. Det finns inte X ∈ V T med | X | ≥ 2. Gå därför till steg 6.
6.

Gomory–Hu output.svg

6. Byt ut V T = { {3}, {5}, {1}, {4}, {0}, {2} } med {3, 5, 1 , 4, 0, 2}.
Ersätt E T = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } av { (1, 3), (3, 5), (2, 4), (1, 4), (0, 2) }.
Utgång T . Observera att exakt | V | − 1 = 6 − 1 = 5 gånger min-cut beräkning utförs.

Implementeringar: Sekventiella och parallella

Gusfields algoritm kan användas för att hitta ett Gomory-Hu-träd utan någon vertexkontraktion i samma löpande tidskomplexitet, vilket förenklar implementeringen av att konstruera ett Gomory-Hu-träd.

Andrew V. Goldberg och K. Tsioutsiouliklis implementerade Gomory-Hu-algoritmen och Gusfield-algoritmen och utförde en experimentell utvärdering och jämförelse.

Cohen et al. rapportera resultat om två parallella implementeringar av Gusfields algoritm med OpenMP respektive MPI.

Relaterade begrepp

I plana grafer är Gomory-Hu-trädet dubbla till minimiviktscykelbasen, i den meningen att snitten av Gomory-Hu-trädet är dubbla till en samling cykler i den dubbla grafen som bildar en minimiviktcykelbas.

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=Gomory–Hu_tree&oldid=1097322015 "