Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Gomory–Hu tree
open-in-new
<p>In <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a>, the Gomory–Hu tree of an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> with capacities is a weighted <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> that represents the minimum <a href="/facts/Cut_(graph_theory)/1lKf2IIW"><i>s</i>-<i>t</i> cuts</a> for all <i>s</i>-<i>t</i> pairs in the graph. The Gomory–Hu tree can be constructed in |<i>V</i>| − 1 <a href="/facts/Maximum_flow_problem/aSal0FGF">maximum flow</a> computations. It is named for <a href="/facts/Ralph_E._Gomory/03KCzwFW">Ralph E. Gomory</a> and <a href="/facts/T._C._Hu/yCoA0dXK">T. C. Hu</a>. </p>