Английская Википедия:Gomory–Hu tree
In combinatorial optimization, the Gomory–Hu tree[1] 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 Шаблон:Math maximum flow computations. It is named for Ralph E. Gomory and T. C. Hu.
Definition
Let <math>G = (V_G, E_G, c)</math> be an undirected graph with <math>c(u,v)</math> being the capacity of the edge <math>(u,v)</math> respectively.
- Denote the minimum capacity of an Шаблон:Mvar-Шаблон:Mvar cut by <math>\lambda_{st}</math> for each <math> s, t \in V_G </math>.
- Let <math> T = (V_G, E_T) </math> be a tree, and denote the set of edges in an Шаблон:Mvar-Шаблон:Mvar path by <math>P_{st}</math> for each <math>s,t \in V_G</math>.
Then Шаблон:Mvar is said to be a Gomory–Hu tree of Шаблон:Mvar, if for each <math>s, t \in V_G</math>
- <math style="display">\lambda_{st} = \min_{e\in P_{st}} c(S_e, T_e),</math>
where
- <math>S_e, T_e \subseteq V_G</math> are the two connected components of <math>T \setminus \{e\}</math>, and thus <math>(S_e, T_e)</math> forms an Шаблон:Mvar-Шаблон:Mvar cut in Шаблон:Mvar.
- <math>c(S_e, T_e)</math> is the capacity of the <math>(S_e,T_e)</math> cut in Шаблон:Mvar.
Algorithm
Gomory–Hu Algorithm
- Input: A weighted undirected graph <math>G = ((V_G,E_G), c)</math>
- Output: A Gomory–Hu Tree <math>T = (V_T, E_T).</math>
- Set <math>V_T = \{V_G\}, \ E_T = \empty.</math>
- Choose some <math>X \in V_T</math> with Шаблон:Math if such Шаблон:Mvar exists. Otherwise, go to step 6.
- For each connected component <math>C = (V_C,E_C) \in T \setminus X,</math> let <math display=inline>S_C = \bigcup_{v_T \in V_C} v_T.</math>
- Let <math>
S = \{ S_C \mid C \text{ is a connected component in } T \setminus X \}. </math>
- Contract the components to form <math>G' = ((V_{G'}, E_{G'}), c'),</math> where:<math display=block>
\begin{align}
V_{G'} &= X \cup S \\[2pt]
E_{G'} &= E_G|_{X \times X} \cup \{(u, S_C) \in X \times S \mid (u,v) \in E_G \text{ for some } v \in S_C \} \\[2pt]
& \qquad \qquad \quad\! \cup \{(S_{C1}, S_{C2}) \in S \times S \mid (u,v) \in E_G \text{ for some } u \in S_{C1} \text{ and } v \in S_{C2} \}
\end{align}</math>
- <math>c':V_{G'} \times V_{G'} \to R^+</math> is the capacity function, defined as:<math display=block>
\begin{align}
&\text{if }\ (u,S_C) \in E_G|_{X \times S}: &&c'(u,S_C) = \!\!\! \sum_{\begin{smallmatrix} v \in S_C : \\ (u,v) \in E_G \end{smallmatrix}} \!\!\! c(u,v) \\[4pt]
&\text{if }\ (S_{C1},S_{C2}) \in E_G|_{S \times S}: &&c'(S_{C1},S_{C2}) = \!\!\!\!\!\!\! \sum_{\begin{smallmatrix} (u,v) \in E_G : \\ u \in S_{C1} \, \land \, v \in S_{C2} \end{smallmatrix}} \!\!\!\!\! c(u,v) \\[4pt]
&\text{otherwise}: &&c'(u,v) = c(u,v)
\end{align}</math>
- Choose two vertices Шаблон:Math and find a minimum Шаблон:Math cut Шаблон:Math in Шаблон:Mvar.
- Set <math>A = \Biggl(\bigcup_{S_C \in A' \cap S} \!\!\! S_C \! \Biggr) \cup (A' \cap X),\ </math><math>B = \Biggl(\bigcup_{S_C \in B' \cap S} \!\!\! S_C \! \Biggr) \cup (B' \cap X).</math>
- Set <math>V_T = (V_T \setminus X) \cup \{A \cap X, B \cap X \}.
</math>
- For each <math>e = (X, Y) \in E_T</math> do:
- Set <math> e' = (A \cap X,Y)</math> if <math> Y \subset A, </math> otherwise set <math>e' = (B \cap X,Y).</math>
- Set <math>E_T = (E_T \setminus \{e\}) \cup \{e'\}.</math>
- Set <math>w(e') = w(e).</math>
- Set <math>E_T = E_T \cup \{(A \cap X,\ B \cap X) \}.</math>
- Set <math>w((A \cap X, B \cap X)) = c'(A', B').</math>
- Go to step 2.
- For each <math>e = (X, Y) \in E_T</math> do:
- Replace each <math>\{v\} \in V_T</math> by Шаблон:Mvar and each <math>(\{u\},\{v\}) \in E_T</math> by Шаблон:Math. Output Шаблон:Mvar.
Analysis
Using the submodular property of the capacity function Шаблон:Mvar, one has <math display=block>c(X) + c(Y) \ge c(X \cap Y) + c(X \cup Y).</math> Then it can be shown that the minimum Шаблон:Math cut in Шаблон:Mvar is also a minimum Шаблон:Math cut in Шаблон:Mvar for any Шаблон:Math.
To show that for all <math>(P,Q) \in E_T,</math> <math>w(P,Q) = \lambda_{pq}</math> for some Шаблон:Math, Шаблон:Math throughout the algorithm, one makes use of the following Lemma,
- For any Шаблон:Mvar in Шаблон:Mvar, <math>\lambda_{ik} \ge \min(\lambda_{ij}, \lambda_{jk}).</math>
The Lemma can be used again repeatedly to show that the output Шаблон:Mvar satisfies the properties of a Gomory–Hu Tree.
Example
The following is a simulation of the Gomory–Hu's algorithm, where
- green circles are vertices of T.
- red and blue circles are the vertices in G'.
- grey vertices are the chosen s and t.
- red and blue coloring represents the s-t cut.
- dashed edges are the s-t cut-set.
- A is the set of vertices circled in red and B is the set of vertices circled in blue.
| G' | T | |
|---|---|---|
| Файл:Gomory–Hu G.svg | Файл:Gomory–Hu T.svg | |
| ||
| 1. | Файл:Gomory–Hu Gp1.svg | Файл:Gomory–Hu T1.svg |
| ||
| 2. | Файл:Gomory–Hu Gp2.svg | Файл:Gomory–Hu T2.svg |
| ||
| 3. | Файл:Gomory–Hu Gp3.svg | Файл:Gomory–Hu T3.svg |
| ||
| 4. | Файл:Gomory–Hu Gp4.svg | Файл:Gomory–Hu T4.svg |
| ||
| 5. | Файл:Gomory–Hu Gp5.svg | Файл:Gomory–Hu T5.svg |
| ||
| 6. | ||
| ||
Implementations: Sequential and Parallel
Gusfield's algorithm can be used to find a Gomory–Hu tree without any vertex contraction in the same running time-complexity, which simplifies the implementation of constructing a Gomory–Hu Tree.[2]
Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm, and performed an experimental evaluation and comparison.[3]
Cohen et al. report results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively.[4]
Related concepts
In planar graphs, the Gomory–Hu tree is dual to the minimum weight cycle basis, in the sense that the cuts of the Gomory–Hu tree are dual to a collection of cycles in the dual graph that form a minimum-weight cycle basis.[5]
See also
References
