Gomory–Hu tree
Introduction 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  maximum flow computations. It is named for Ralph E. Gomory and T. C. Hu.
Definition Let  be an undirected graph with  being the capacity of the edge  respectively. : Denote the minimum capacity of an - cut by  for each . : Let  be a tree, and denote the set of edges in an - path by  for each .Then  is said to be a '''Gomory–Hu tree''' of , if for each : where#  are the two connected components of , and thus  forms an - cut in .#  is the capacity of the  cut in .
Algorithm '''Gomory–Hu Algorithm''':''Input'': A weighted undirected graph : ''Output'': A Gomory–Hu Tree # Set # Choose some  with  if such  exists. Otherwise, go to step 6.# For each connected component  let  #:Let  #: Contract the components to form  where:#:: is the capacity function, defined as:# Choose two vertices  and find a minimum  cut  in .#:Set # Set  #:For each  do:#:#Set  if  otherwise set #:#Set #:#Set  #:Set #:Set #:Go to step 2.# Replace each  by  and each  by . Output .
Analysis Using the submodular property of the capacity function , one hasThen it can be shown that the minimum  cut in  is also a minimum  cut in  for any .To show that for all   for some ,  throughout the algorithm, one makes use of the following Lemma,: For any  in , The Lemma can be used again repeatedly to show that the output  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'' 300px 300px:1.Set ''V''T = {''V''G} = { {0, 1, 2, 3, 4, 5} } and ''E''T = ∅. :2.Since ''V''T has only one vertex, choose ''X'' = ''V''G = {0, 1, 2, 3, 4, 5}. Note that | ''X'' | = 6 ≥ 2.1.300px 300px: 3.Since ''T''\''X'' = ∅, there is no contraction and therefore ''G'' = ''G''. : 4.Choose ''s'' = 1 and ''t'' = 5.The minimum ''s''-''t'' cut (''A'', ''B'') is ({0, 1, 2, 4}, {3, 5}) with ''c''(''A'', ''B'') = 6.:    Set ''A'' = {0, 1, 2, 4} and ''B'' = {3, 5}. : 5.Set ''V''T = (''V''T\''X'') ∪ {''A'' ∩ ''X'', ''B'' ∩ ''X''} = { {0, 1, 2, 4}, {3, 5} }. :    Set ''E''T = { ({0, 1, 2, 4}, {3, 5}) }. :    Set ''w''( ({0, 1, 2, 4}, {3, 5}) ) = ''c''(''A'', ''B'') = 6.:    Go to step 2.: 2.Choose ''X'' = {3, 5}. Note that | ''X'' | = 2 ≥ 2.2.300px 300px: 3. {0, 1, 2, 4} is the connected component in ''T''\''X'' and thus ''S'' = { {0, 1, 2, 4} }. :    Contract {0, 1, 2, 4} to form ''G'', where:: ''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.Choose ''s'' = 3, ''t'' = 5.The minimum ''s''-''t'' cut (''A'', ''B'') in ''G'' is (  with ''c''(''A'', ''B'') = 8.:    Set ''A'' = {0, 1, 2, 3, 4} and ''B'' = {5}. : 5.Set ''V''T = (''V''T\''X'') ∪ {''A'' ∩ ''X'', ''B'' ∩ ''X''} = . :    Since (''X'', {0, 1, 2, 4}) ∈ ''E''T and {0, 1, 2, 4} ⊂ ''A'', replace it with (''A'' ∩ ''X'', ''Y'') = ({3}, {0, 1, 2 ,4}). :    Set ''E''T = { ({3}, {0, 1, 2 ,4}), ({3}, {5}) } with:: ''w''(({3}, {0, 1, 2 ,4})) = ''w''((''X'', {0, 1, 2, 4})) = 6.:: ''w''(({3}, {5})) = ''c''(''A'', ''B'') = 8.:    Go to step 2.: 2.Choose ''X'' = {0, 1, 2, 4}. Note that | ''X'' | = 4 ≥ 2.3.300px 300px: 3. { {3}, {5} } is the connected component in ''T''\''X'' and thus ''S'' = { {3, 5} }. :    Contract {3, 5} to form ''G'', where:: ''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'') for all ''u'',''v'' ∈ ''X''. : 4.Choose ''s'' = 1, ''t'' = 2.The minimum ''s''-''t'' cut (''A'', ''B'') in ''G'' is ( {1, {3, 5}, 4}, {0, 2} ) with ''c''(''A'', ''B'') = 6.:    Set ''A'' = {1, 3, 4, 5} and ''B'' = {0, 2}. : 5.Set ''V''T = (''V''T\''X'') ∪ {''A'' ∩ ''X'', ''B'' ∩ ''X''} = { {3}, {5}, {1, 4}, {0, 2} }. :    Since (''X'', {3}) ∈ ''E''T and {3} ⊂ ''A'', replace it with (''A'' ∩ ''X'', ''Y'') = ({1, 4}, {3}). :    Set ''E''T = { ({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4}) } with:: ''w''(({1, 4}, {3})) = ''w''((''X'', {3})) = 6.:: ''w''(({0, 2}, {1, 4})) = ''c''(''A'', ''B'') = 6.:    Go to step 2.: 2.Choose ''X'' = {1, 4}. Note that | ''X'' | = 2 ≥ 2.4.300px 300px: 3. { {3}, {5} }, { {0, 2} } are the connected components in ''T''\''X'' and thus ''S'' = { {0, 2}, {3, 5} }:    Contract {0, 2} and {3, 5} to form ''G'', where:: ''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'') for all ''u'',''v'' ∈ ''X''. : 4.Choose ''s'' = 1, ''t'' = 4.The minimum ''s''-''t'' cut (''A'', ''B'') in ''G'' is (  ) with ''c''(''A'', ''B'') = 7.:    Set ''A'' = {1, 3, 5} and ''B'' = {0, 2, 4}. : 5.Set ''V''T = (''V''T\''X'') ∪ {''A'' ∩ ''X'', ''B'' ∩ ''X''} = { {3}, {5}, {0, 2}, {1}, {4} }. :    Since (''X'', {3}) ∈ ''E''T and {3} ⊂ ''A'', replace it with (''A'' ∩ ''X'', ''Y'') = ({1}, {3}). :    Since (''X'', {0, 2}) ∈ ''E''T and {0, 2} ⊂ ''B'', replace it with (''B'' ∩ ''X'', ''Y'') = ({4}, {0, 2}). :    Set ''E''T = { ({1}, {3}), ({3}, {5}), ({4}, {0, 2}), ({1}, {4}) } with:: ''w''(({1}, {3})) = ''w''((''X'', {3})) = 6.:: ''w''(({4}, {0, 2})) = ''w''((''X'', {0, 2})) = 6.:: ''w''(({1}, {4})) = ''c''(''A'', ''B'') = 7.:    Go to step 2.: 2.Choose ''X'' = {0, 2}. Note that | ''X'' | = 2 ≥ 2.5.300px 300px: 3. { {1}, {3}, {4}, {5} } is the connected component in ''T''\''X'' and thus ''S'' = { {1, 3, 4, 5} }. :    Contract {1, 3, 4, 5} to form ''G'', where:: ''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.Choose ''s'' = 0, ''t'' = 2.The minimum ''s''-''t'' cut (''A'', ''B'') in ''G'' is (  ) with ''c''(''A'', ''B'') = 8.:    Set ''A'' = {0} and ''B'' = {1, 2, 3 ,4 ,5}. : 5.Set ''V''T = (''V''T\''X'') ∪ {''A'' ∩ ''X'', ''B'' ∩ ''X''} = { {3}, {5}, {1}, {4}, {0}, {2} }. :    Since (''X'', {4}) ∈ ''E''T and {4} ⊂ ''B'', replace it with (''B'' ∩ ''X'', ''Y'') = ({2}, {4}). :    Set ''E''T = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } with:: ''w''(({2}, {4})) = ''w''((''X'', {4})) = 6.:: ''w''(({0}, {2})) = ''c''(''A'', ''B'') = 8.:    Go to step 2.: 2.There does not exist ''X''∈''V''T with | ''X'' | ≥ 2.Hence, go to step 6.6.300px: 6.Replace ''V''T = { {3}, {5}, {1}, {4}, {0}, {2} } by {3, 5, 1, 4, 0, 2}. :    Replace ''E''T = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } by { (1, 3), (3, 5), (2, 4), (1, 4), (0, 2) }. :    Output ''T''. Note that exactly | ''V'' | − 1 = 6 − 1 = 5 times min-cut computation is performed.
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 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.
See also * Cut (graph theory)* Max-flow min-cut theorem* Maximum flow problem
References *