Gomory-Hu Tree is a representation of graph and it is mainly used for analyzing Max-Flow or Min-Cut problems.
For a undirected graph , we say tree is a gomory-hu tree of G if
- (flow equivalence) For every pair , value of max flow in G is equal to in T.
- (Cut property) Suppose is the minimum weight among all edges on path from s to t, then we find a min cut of the original graph where is connected component in T after removing edge (u,v).
Existence and related theorems:
Basically, we construct a algorithm which gives desirable tree. Details could be found here.
Gomory-Hu tree is a beautiful and powerful representation of a graph. Many problems related to min cut or max flow could be solved perfectly by it.
- Find global minimum cut set, namely min cut set with smallest value among all possible min cut sets.
- Given a matrix , determine if there exists a graph such that value of min cut is .
- Minimum k-cut problem (Gomory-Hu tree induces an approximated solution).