testing Latex

Gomory-Hu Tree is a representation of graph and it is mainly used for analyzing Max-Flow or Min-Cut problems.

Definition:

For a undirected graph G(V, E), we say tree T(V, E_{gh}) is a gomory-hu tree of G if

  1. (flow equivalence) For every pair u,v \in V, value of max flow f_G(u,v) in G is equal to f_T(u,v) in T.
  2. (Cut property) Suppose w_T(u,v) is the minimum weight among all edges on path from s to t, then we find a min cut (X, \bar{X}) of the original graph where X 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.

Application:

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.

  1. Find global minimum cut set, namely min cut set with smallest value among all possible min cut sets.
  2. Given a n\times n matrix M, determine if there exists a graph such that value of min i-j cut is M_{ij}.
  3. Minimum k-cut problem (Gomory-Hu tree induces an approximated solution).