In
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
, the Gomory–Hu tree of an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
with capacities is a weighted
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
that represents the minimum
''s''-''t'' cuts for all ''s''-''t'' pairs in the graph. The Gomory–Hu tree can be constructed in
maximum flow
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
computations.
Definition
Let ''G'' = ((''V''
G, ''E''
G), ''c'') be an undirected graph with ''c''(''u'',''v'') being the capacity of the edge (''u'',''v'') respectively.
: Denote the minimum capacity of an ''s''-''t'' cut by λ
st for each ''s'', ''t'' ∈ ''V''
G.
: Let ''T'' = (''V''
G, ''E''
T) be a tree, denote the set of edges in an ''s''-''t'' path by ''P''
st for each ''s'', ''t'' ∈ ''V''
G.
Then ''T'' is said to be a Gomory–Hu tree of ''G'', if for each ''s'', ''t'' ∈ ''V''
G
: λ
st = min
e∈Pst ''c''(''S''
e, ''T''
e),
where
# ''S''
e, ''T''
e ⊆ ''V''
G are the two connected components of ''T''∖, and thus (''S''
e, ''T''
e) form an ''s''-''t'' cut in ''G''.
# ''c''(''S''
e, ''T''
e) is the capacity of the cut in ''G''.
Algorithm
Gomory–Hu Algorithm
:''Input'': A weighted undirected graph G = ((''V''
G, ''E''
G), ''c'')
: ''Output'': A Gomory–Hu Tree ''T'' = (''V''
T, ''E''
T).
:1. Set ''V''
T = and ''E''
T = ∅.
:2. Choose some ''X''∈''V''
T with , ''X'' , ≥ 2 if such ''X'' exists. Otherwise, go to step 6.
:3. For each connected component ''C'' = (''V''
C, ''E''
C) in ''T''∖''X''. Let ''S''
C = ∪
vT∈VC ''v''
T. Let ''S'' = .
: Contract the components to form ''G''
' = ((''V''
G', ''E''
G'), ''c''
'), where
:: ''V''
G' = ''X'' ∪ ''S''.
:: ''E''
G' = ''E''
G,
X×X ∪ ∪ .
:: ''c''
' : ''V''
G'×''V''
G'→''R''
+ is the capacity function defined as,
::# if (''u'',''S''
C)∈''E''
G,
X×S, ''c''
'(''u'',''S''
C) = Σ
v∈SC:(u,v)∈EG''c''(''u'',''v''),
::# if (''S''
C1,''S''
C2)∈''E''
G,
S×S, ''c''
'(''S''
C1,''S''
C2) = Σ
(u,v)∈EG:u∈SC1∧v∈SC2 ''c''(''u'',''v''),
::# ''c''
'(''u'',''v'') = ''c''(''u'',''v'') otherwise.
:4. Choose two vertices ''s'', ''t'' ∈ ''X'' and find a minimum ''s''-''t'' cut (''A''
',''B''
') in ''G''
'.
: Set ''A'' = (∪
SC∈''A'''∩''S'' ''S''
C) ∪ (''A''
' ∩ ''X'') and ''B'' = (∪
SC∈''B'''∩''S'' ''S''
C) ∪ (''B''
' ∩ ''X'').
: 5. Set ''V''
T = (''V''
T∖''X'') ∪ .
: For each ''e'' = (''X'', ''Y'') ∈ ''E''
T do
:: If ''Y'' ⊂ ''A'', set ''e''
' = (''A'' ∩ ''X'', ''Y''), else set ''e''
' = (''B'' ∩ ''X'', ''Y'').
:: Set ''E''
T = (''E''
T∖) ∪ and ''w''(''e''
') = ''w''(''e'').
: Set ''E''
T = ''E''
T ∪ .
: Set ''w''((''A''∩''X'', ''B''∩''X'')) = ''c''
'(''A''
', ''B''
').
: Go to step 2.
: 6. Replace each ∈ ''V''
T by ''v'' and each (,) ∈ ''E''
T by (''u'',''v''). Output ''T''.
Analysis
Using the
submodular property of the capacity function ''c'', one has
: ''c''(''X'') + ''c''(''Y'') ≥ ''c''(''X'' ∩ ''Y'') + ''c''(''X'' ∪ ''Y'').
Then it can be shown that the minimum ''s''-''t'' cut in ''G''
' is also a minimum ''s''-''t'' cut in ''G'' for any ''s'', ''t'' ∈ ''X''.
To show that for all (''P'', ''Q'') ∈ ''E''
T, ''w''(''P'',''Q'') = λ
''pq'' for some ''p'' ∈ ''P'', ''q'' ∈ ''Q'' throughout the algorithm, one makes use of the following Lemma,
: For any ''i'', ''j'', ''k'' in ''V''
G, λ
ik ≥ min(λ
ij, λ
jk).
The Lemma can be used again repeatedly to show that the output ''T'' 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''.
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.
Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm, and performed an experimental evaluation and comparison.
Cohen et al. report results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively.
Related concepts
In
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s, the Gomory–Hu tree is dual to the minimum weight
cycle basis
In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be exp ...
, in the sense that the cuts of the Gomory–Hu tree are dual to a collection of cycles in the
dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
that form a minimum-weight cycle basis.
[.]
See also
*
Cut (graph theory)
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connec ...
*
Max-flow min-cut theorem
In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in a minimum cut, i.e., the ...
*
Maximum flow problem
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
References
*
{{DEFAULTSORT:Gomory-Hu tree
Combinatorial optimization
Network flow problem
Graph algorithms