In combinatorial optimization, the Gomory–Hu tree of an undirected graph with capacities is a weighted tree that represents the minimum s-t cuts for all s-t pairs in the graph. The Gomory–Hu tree can be constructed in |V| − 1 maximum flow computations. It is named for Ralph E. Gomory and T. C. Hu.
Definition Let G = ( V G , E G , c ) {\displaystyle G=(V_{G},E_{G},c)} be an undirected graph with c ( u , v ) {\displaystyle c(u,v)} being the capacity of the edge ( u , v ) {\displaystyle (u,v)} respectively.
Denote the minimum capacity of an s-t cut by λ s t {\displaystyle \lambda _{st}} for each s , t ∈ V G {\displaystyle s,t\in V_{G}} . Let T = ( V G , E T ) {\displaystyle T=(V_{G},E_{T})} be a tree, and denote the set of edges in an s-t path by P s t {\displaystyle P_{st}} for each s , t ∈ V G {\displaystyle s,t\in V_{G}} . Then T is said to be a Gomory–Hu tree of G, if for each s , t ∈ V G {\displaystyle s,t\in V_{G}}
λ s t = min e ∈ P s t c ( S e , T e ) , {\displaystyle \lambda _{st}=\min _{e\in P_{st}}c(S_{e},T_{e}),}
where
S e , T e ⊆ V G {\displaystyle S_{e},T_{e}\subseteq V_{G}} are the two connected components of T ∖ { e } {\displaystyle T\setminus \{e\}} , and thus ( S e , T e ) {\displaystyle (S_{e},T_{e})} forms an s-t cut in G.
c ( S e , T e ) {\displaystyle c(S_{e},T_{e})} is the capacity of the ( S e , T e ) {\displaystyle (S_{e},T_{e})} cut in G.
Algorithm Gomory–Hu Algorithm
Input: A weighted undirected graph G = ( ( V G , E G ) , c ) {\displaystyle G=((V_{G},E_{G}),c)}
Output: A Gomory–Hu Tree T = ( V T , E T ) . {\displaystyle T=(V_{T},E_{T}).}
Set V T = { V G } , E T = ∅ . {\displaystyle V_{T}=\{V_{G}\},\ E_{T}=\emptyset .}
Choose some X ∈ V T {\displaystyle X\in V_{T}} with |X| ≥ 2 if such X exists. Otherwise, go to step 6. For each connected component C = ( V C , E C ) ∈ T ∖ X , {\displaystyle C=(V_{C},E_{C})\in T\setminus X,} let S C = ⋃ v T ∈ V C v T . {\textstyle S_{C}=\bigcup _{v_{T}\in V_{C}}v_{T}.}
Let S = { S C ∣ C is a connected component in T ∖ X } . {\displaystyle S=\{S_{C}\mid C{\text{ is a connected component in }}T\setminus X\}.}
… excerpt ends here. Continue reading the full article.
