The following lectures will talk about some algorithms on graphs. This blog is about Max flow and Min cut problem, and how can they transfer to each other.

Considering directed graphs, we define following concepts

• Capacity: We define “capacity” on an edge, indicating the maximum load this edge can carry.

• Source node: Generates the traffic (only have leaving edge)

• Sink node: Absorbs the traffic (only have incoming edge)

Min ${ s-t }$ Cut

Given

• Digraph ${ G= (V,E) }$

• Source node ${ s }$, sink node ${ t }$

• Capacity function: ${ c:E \rightarrow \mathbb{Z},\forall e \in E, c(e) \in \mathbb{Z} }$

Now, we give the definition of "CUT"

An ${ s-t }$ cut is a partition of the vertex set ${ V }$ into two sets ${ S,T }$ such that

$$ s \in S, t\in T $$

Then we give the definition of Capacity of ${ s-t }$ Cut.

$$ Cap (S,T) = \sum_{e \in \delta^+(S)} c(e) $$

Here, we use ${ \delta(S) }$ denotes the edges with nodes in vertex set ${ S }$, and ${ \delta^+(S),\delta^-(S) }$ represent the edges leaving from /coming into vertex set ${ S }$.

So, the Min ${ s-t }$ Cut problem is finding the ${ s-t}$ cut with minimum capacity.

Max ${ s-t }$ Flow

An ${ s-t }$ flow is a function ${ f: E\rightarrow \mathbb{Z}}$ satisifying the following constraints:

1. ${ \forall e \in E, 0\leq f(e)\leq c(e) }$

2. ${ \forall v \in V\setminus {s,t}, \sum_{e\in \delta^-(v) f(e) = \sum_{e \in \delta^+(v)} f(e)} }$

Now, we can define the value of flow ${ f }$ as

$$ val(f) = \sum_{e \in \delta^+(s)} f(e) $$

So, the Max ${ s-t }$ flow problem is finding the ${ s-t}$ flow with maximum value.

Flow and Cut

• Lemma 1: Let ${ f }$ be a flow and ${ (S,T) }$ be any ${ s-t }$ cut. Then the net flow accross the ${ (S,T) }$ cut is equal to the value of flow.

Proof. Because the flow ${ f }$ in each vetex satisfy the second rule, we have

$$ \begin{equation} \begin{aligned} val(f) &= \sum_{e\in \delta^+(s)} f(e) - \sum_{e\in \delta^-(s)} f(e), \text{ here }\delta^-(s) = \emptyset \\ &= \sum_{v\in S} \left( \sum_{e\in \delta^+(v)} f(e) - \sum_{e\in \delta^-(v)} f(e) \right), \text{ use #2 rule} \\ &=\sum_{v\in S} \sum_{e\in \delta^+(v)} f(e) - \sum_{v\in S} \sum_{e\in \delta^-(v)} f(e) \\ & = \sum_{e\in \delta^+(S)} f(e) - \sum_{e\in \delta^-(S)} f(e), \text{all the edges in S are canceled} \\ & = Cap(S,T) \end{aligned} \end{equation} $$

• Lemma 2: Let ${ f }$ be any flow ${ f }$ and let ${ (S,T) }$ be any ${ s-t }$ cut. Then the value of flow is at most the capacity of the ${ (S,T) }$ cut, that is

$$ val(f) \leq Cap(S,t) $$

Proof. By Lemma 1,

$$ \begin{equation} \begin{aligned} val(f) &= \sum_{e\in \delta^+(S)} f(e) - \sum_{e\in \delta^-(S)} f(e), \text{ By Lemma 1 }\\ & \leq \sum_{e\in \delta^+(S)} f(e) \\ & \leq \sum_{e\in \delta^+(S)} f(e), \text{ use #1 rule} \\ &= Cap(S,T) \end{aligned} \end{equation} $$

• Lemma 3: Let ${ f }$ be any flow and ${ (S,T) }$ be any ${ s-t }$ cut. If ${ val(f) = Cap(S,T) }$, ${ f }$ is a maximum flow and ${ (S,T) }$ is a min cut.

Proof. We assume the conclusion is not correct to deduce contradiction

1. ${ (S,T) }$ is not a min cut, let ${ (S’,T’) }$ be the min cut, so

$$ Cap(S',T') < Cap(S,T) = val(f) $$

which contradicts to Lemma 2. All the value of flow can not greater than the capacity of cut.

1. flow ${ f }$ is not a maximum flow, let ${ f’ }$ be the maximum flow

$$ val(f') > val(f) = Cap(S,T) $$

which contradicts to Lemma 2.

Max Flow-Min Cut Thorem

Max Flow-Min Cut Thorem

: In any network the value of max flow equals the capacity of the min cut.

In the following part, we will give a way to transform the max-flow as a cut. By Lemma 3, we will prove the Thorem.