# 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).

# one more

line

line

line

line with p tags under

line with span under

line with br tag under

line

# Site Private, Post Public

can a8c followers see this?
can nona8c followers see this?

nose arch?

# OK Second Time Published Private

tersting tersting

# Did you get an email SAO?

check it check it