# 组合数学 (Fall 2011)/Flow and matching

## Flow and Cut

### Flows

An instance of the maximum flow problem consists of:

• a directed graph ${\displaystyle G(V,E)}$;
• two distinguished vertices ${\displaystyle s}$ (the source) and ${\displaystyle t}$ (the sink), where the in-degree of ${\displaystyle s}$ and the out-degree of ${\displaystyle t}$ are both 0;
• the capacity function ${\displaystyle c:E\rightarrow \mathbb {R} ^{+}}$ which associates each directed edge ${\displaystyle (u,v)\in E}$ a nonnegative real number ${\displaystyle c_{uv}}$ called the capacity of the edge.

The quadruple ${\displaystyle (G,c,s,t)}$ is called a flow network.

A function ${\displaystyle f:E\rightarrow \mathbb {R} ^{+}}$ is called a flow (to be specific an ${\displaystyle s}$-${\displaystyle t}$ flow) in the network ${\displaystyle G(V,E)}$ if it satisfies:

• Capacity constraint: ${\displaystyle f_{uv}\leq c_{uv}}$ for all ${\displaystyle (u,v)\in E}$.
• Conservation constraint: ${\displaystyle \sum _{u:(u,v)\in E}f_{uv}=\sum _{w:(v,w)\in E}f_{vw}}$ for all ${\displaystyle v\in V\setminus \{s,t\}}$.

The value of the flow ${\displaystyle f}$ is ${\displaystyle \sum _{v:(s,v)\in E}f_{sv}}$.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.

{\displaystyle {\begin{aligned}{\text{maximize}}\quad &\sum _{v:(s,v)\in E}f_{sv}\\{\begin{aligned}{\text{subject to}}\\\\\\\\\end{aligned}}\quad &{\begin{aligned}f_{uv}&\leq c_{uv}&\quad &\forall (u,v)\in E\\\sum _{u:(u,v)\in E}f_{uv}-\sum _{w:(v,w)\in E}f_{vw}&=0&\quad &\forall v\in V\setminus \{s,t\}\\f_{uv}&\geq 0&\quad &\forall (u,v)\in E\end{aligned}}\end{aligned}}}

### Cuts

 Definition Let ${\displaystyle (G(V,E),c,s,t)}$ be a flow network. Let ${\displaystyle S\subset V}$. We call ${\displaystyle (S,{\bar {S}})}$ an ${\displaystyle s}$-${\displaystyle t}$ cut if ${\displaystyle s\in S}$ and ${\displaystyle t\not \in S}$. The value of the cut (also called the capacity of the cut) is defined as ${\displaystyle \sum _{u\in S,v\not \in S \atop (u,v)\in E}c_{uv}}$.

A fundamental fact in flow theory is that cuts always upper bound flows.

 Lemma Let ${\displaystyle (G(V,E),c,s,t)}$ be a flow network. Let ${\displaystyle f}$ be an arbitrary flow in ${\displaystyle G}$, and let ${\displaystyle (S,{\bar {S}})}$ be an arbitrary ${\displaystyle s}$-${\displaystyle t}$ cut. Then ${\displaystyle \sum _{v:(s,v)}f_{sv}\leq \sum _{u\in S,v\not \in S \atop (u,v)\in E}c_{uv}}$, that is, the value of any flow is no greater than the value of any cut.
Proof.
 By the definition of ${\displaystyle s}$-${\displaystyle t}$ cut, ${\displaystyle s\in S}$ and ${\displaystyle t\not \in S}$. Due to the conservation of flow, ${\displaystyle \sum _{u\in S}\left(\sum _{v:(u,v)\in E}f_{uv}-\sum _{v:(v,u)\in E}f_{vu}\right)=\sum _{v:(s,v)\in E}f_{sv}+\sum _{u\in S\setminus \{s\}}\left(\sum _{v:(u,v)\in E}f_{uv}-\sum _{v:(v,u)\in E}f_{vu}\right)=\sum _{v:(s,v)\in E}f_{sv}\,.}$ On the other hand, summing flow over edges, ${\displaystyle \sum _{v\in S}\left(\sum _{u:(u,v)\in E}f_{uv}-\sum _{u:(v,u)\in E}f_{vu}\right)=\sum _{u\in S,v\in S \atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum _{u\in S,v\not \in S \atop (u,v)\in E}f_{uv}-\sum _{u\in S,v\not \in S \atop (v,u)\in E}f_{vu}=\sum _{u\in S,v\not \in S \atop (u,v)\in E}f_{uv}-\sum _{u\in S,v\not \in S \atop (v,u)\in E}f_{vu}\,.}$ Therefore, ${\displaystyle \sum _{v:(s,v)\in E}f_{sv}=\sum _{u\in S,v\not \in S \atop (u,v)\in E}f_{uv}-\sum _{u\in S,v\not \in S \atop (v,u)\in E}f_{vu}\leq \sum _{u\in S,v\not \in S \atop (u,v)\in E}f_{uv}\leq \sum _{u\in S,v\not \in S \atop (u,v)\in E}c_{uv}\,,}$
${\displaystyle \square }$

### Augmenting paths

 Definition (Augmenting path) Let ${\displaystyle f}$ be a flow in ${\displaystyle G}$. An augmenting path to ${\displaystyle u_{k}}$ is a sequence of distinct vertices ${\displaystyle P=(u_{0},u_{1},\cdots ,u_{k})}$, such that ${\displaystyle u_{0}=s\,}$; and each pair of consecutive vertices ${\displaystyle u_{i}u_{i+1}\,}$ in ${\displaystyle P}$ corresponds to either a forward edge ${\displaystyle (u_{i},u_{i+1})\in E}$ or a reverse edge ${\displaystyle (u_{i+1},u_{i})\in E}$, and ${\displaystyle f(u_{i},u_{i+1}) when ${\displaystyle u_{i}u_{i+1}\,}$ corresponds to a forward edge ${\displaystyle (u_{i},u_{i+1})\in E}$, and ${\displaystyle f(u_{i+1},u_{i})>0\,}$ when ${\displaystyle u_{i}u_{i+1}\,}$ corresponds to a reverse edge ${\displaystyle (u_{i+1},u_{i})\in E}$. If ${\displaystyle u_{k}=t\,}$, we simply call ${\displaystyle P}$ an augmenting path.

Let ${\displaystyle f}$ be a flow in ${\displaystyle G}$. Suppose there is an augmenting path ${\displaystyle P=u_{0}u_{1}\cdots u_{k}}$, where ${\displaystyle u_{0}=s}$ and ${\displaystyle u_{k}=t}$. Let ${\displaystyle \epsilon >0}$ be a positive constant satisfying

• ${\displaystyle \epsilon \leq c(u_{i},u_{i+1})-f(u_{i},u_{i+1})}$ for all forward edges ${\displaystyle (u_{i},u_{i+1})\in E}$ in ${\displaystyle P}$;
• ${\displaystyle \epsilon \leq f(u_{i+1},u_{i})}$ for all reverse edges ${\displaystyle (u_{i+1},u_{i})\in E}$ in ${\displaystyle P}$.

Due to the definition of augmenting path, we can always find such a positive ${\displaystyle \epsilon }$.

Increase ${\displaystyle f(u_{i},u_{i+1})}$ by ${\displaystyle \epsilon }$ for all forward edges ${\displaystyle (u_{i},u_{i+1})\in E}$ in ${\displaystyle P}$ and decrease ${\displaystyle f(u_{i+1},u_{i})}$ by ${\displaystyle \epsilon }$ for all reverse edges ${\displaystyle (u_{i+1},u_{i})\in E}$ in ${\displaystyle P}$. Denote the modified flow by ${\displaystyle f'}$. It can be verified that ${\displaystyle f'}$ satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow ${\displaystyle f'}$

${\displaystyle \sum _{v:(s,v)\in E}f_{sv}'=\epsilon +\sum _{v:(s,v)\in E}f_{sv}>\sum _{v:(s,v)\in E}f_{sv}}$.

Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

 Lemma A flow ${\displaystyle f}$ is maximum if and only if there are no augmenting paths.
Proof.
 We have already proved the "only if" direction above. Now we prove the "if" direction. Let ${\displaystyle S=\{u\in V\mid \exists {\text{an augmenting path to }}u\}}$. Clearly ${\displaystyle s\in S}$, and since there is no augmenting path ${\displaystyle t\not \in S}$. Therefore, ${\displaystyle (S,{\bar {S}})}$ defines an ${\displaystyle s}$-${\displaystyle t}$ cut. We claim that ${\displaystyle \sum _{v:(s,v)}f_{sv}=\sum _{u\in S,v\not \in S \atop (u,v)\in E}c_{uv}}$, that is, the value of flow ${\displaystyle f}$ approach the value of the cut ${\displaystyle (S,{\bar {S}})}$ defined above. By the above lemma, this will imply that the current flow ${\displaystyle f}$ is maximum. To prove this claim, we first observe that ${\displaystyle \sum _{v:(s,v)}f_{sv}=\sum _{u\in S,v\not \in S \atop (u,v)\in E}f_{uv}-\sum _{u\in S,v\not \in S \atop (v,u)\in E}f_{vu}}$. This identity is implied by the flow conservation constraint, and holds for any ${\displaystyle s}$-${\displaystyle t}$ cut ${\displaystyle (S,{\bar {S}})}$. We then claim that ${\displaystyle f_{uv}=c_{uv}}$ for all ${\displaystyle u\in S,v\not \in S,(u,v)\in E}$; and ${\displaystyle f_{vu}=0}$ for all ${\displaystyle u\in S,v\not \in S,(v,u)\in E}$. If otherwise, then the augmenting path to ${\displaystyle u}$ apending ${\displaystyle uv}$ becomes a new augmenting path to ${\displaystyle v}$, which contradicts that ${\displaystyle S}$ includes all vertices to which there exist augmenting paths. Therefore, ${\displaystyle \sum _{v:(s,v)}f_{sv}=\sum _{u\in S,v\not \in S \atop (u,v)\in E}f_{uv}-\sum _{u\in S,v\not \in S \atop (v,u)\in E}f_{vu}=\sum _{u\in S,v\not \in S \atop (u,v)\in E}c_{uv}}$. As discussed above, this proves the theorem.
${\displaystyle \square }$

## Max-Flow Min-Cut

### The max-flow min-cut theorem

 Max-Flow Min-Cut Theorem In a flow network, the maximum value of any ${\displaystyle s}$-${\displaystyle t}$ flow equals the minimum value of any ${\displaystyle s}$-${\displaystyle t}$ cut.
Proof.
 Let ${\displaystyle f}$ be a flow with maximum value, so there is no augmenting path. Again, let ${\displaystyle S=\{u\in V\mid \exists {\text{an augmenting path to }}u\}}$. As proved above, ${\displaystyle (S,{\bar {S}})}$ forms an ${\displaystyle s}$-${\displaystyle t}$ cut, and ${\displaystyle \sum _{v:(s,v)}f_{sv}=\sum _{u\in S,v\not \in S \atop (u,v)\in E}c_{uv}}$, that is, the value of flow ${\displaystyle f}$ equals the value of cut ${\displaystyle (S,{\bar {S}})}$. Since we know that all ${\displaystyle s}$-${\displaystyle t}$ flows are not greater than any ${\displaystyle s}$-${\displaystyle t}$ cut, the value of flow ${\displaystyle f}$ equals the minimum value of any ${\displaystyle s}$-${\displaystyle t}$ cut.
${\displaystyle \square }$

### Flow Integrality Theorem

 Flow Integrality Theorem Let ${\displaystyle (G,c,s,t)}$ be a flow network with integral capacity ${\displaystyle c}$. There exists an integral flow which is maximum.
Proof.
 Let ${\displaystyle f}$ be an integral flow of maximum value. If there is an augmenting path, since both ${\displaystyle c}$ and ${\displaystyle f}$ are integral, a new flow can be constructed of value 1+the value of ${\displaystyle f}$, contradicting that ${\displaystyle f}$ is maximum over all integral flows. Therefore, there is no augmenting path, which means that ${\displaystyle f}$ is maximum over all flows, integral or not.
${\displaystyle \square }$

### Applications: Menger's theorem

Given an undirected graph ${\displaystyle G(V,E)}$ and two distinct vertices ${\displaystyle s,t\in V}$, a set of edges ${\displaystyle C\subseteq E}$ is called an ${\displaystyle s}$-${\displaystyle t}$ cut, if deleting edges in ${\displaystyle C}$ disconnects ${\displaystyle s}$ and ${\displaystyle t}$.

A simple path from ${\displaystyle s}$ to ${\displaystyle t}$ is called an ${\displaystyle s}$-${\displaystyle t}$ path. Two paths are said to be edge-disjoint if they do not share any edge.

 Theorem (Menger 1927) Let ${\displaystyle G(V,E)}$ be an arbitrary undirected graph and ${\displaystyle s,t\in V}$ be two distinct vertices. The minimum size of any ${\displaystyle s}$-${\displaystyle t}$ cut equals the maximum number of edge-disjoint ${\displaystyle s}$-${\displaystyle t}$ paths.
Proof.
 Construct a directed graph ${\displaystyle G'(V,E')}$ from ${\displaystyle G(V,E)}$ as follows: replace every undirected edge ${\displaystyle uv\in E}$ that ${\displaystyle s,t\not \in \{u,v\}}$ by two directed edges ${\displaystyle (u,v)}$ and ${\displaystyle (v,u)}$; replace every undirected edge ${\displaystyle sv\in E}$ by ${\displaystyle (s,v)}$, and very undirected edge ${\displaystyle vt\in E}$ by ${\displaystyle (v,t)}$. Then assign every directed edge with capacity 1. It is easy to verify that in the flow network constructed as above, the followings hold: An integral ${\displaystyle s}$-${\displaystyle t}$ flow corresponds to a set of ${\displaystyle s}$-${\displaystyle t}$ paths in the undirected graph ${\displaystyle G}$, where the value of the flow is the number of ${\displaystyle s}$-${\displaystyle t}$ paths. An ${\displaystyle s}$-${\displaystyle t}$ cut in the flow network corresponds to an ${\displaystyle s}$-${\displaystyle t}$ cut in the undirected graph ${\displaystyle G}$ with the same value. The Menger's theorem follows as a direct consequence of the max-flow min-cut theorem.
${\displaystyle \square }$

### Applications: König-Egerváry theorem

Let ${\displaystyle G(V,E)}$ be a graph. An edge set ${\displaystyle M\subseteq E}$ is called a matching if no edge in ${\displaystyle M}$ shares any vertex. A vertex set ${\displaystyle C\subseteq V}$ is called a vertex cover if for any edge ${\displaystyle uv\in E}$, either ${\displaystyle u\in C}$ or ${\displaystyle v\in C}$.

 Theorem (König 1936) In any bipartite graph ${\displaystyle G(V_{1},V_{2},E)}$, the size of a maximum matching equals the size of a minimum vertex cover.

We now show how a reduction of bipartite matchings to flows.

Construct a flow network ${\displaystyle (G'(V,E'),c,s,t)}$ as follows:

• ${\displaystyle V=V_{1}\cup V_{2}\cup \{s,t\}}$ where ${\displaystyle s}$ and ${\displaystyle t}$ are two new vertices.
• For ever ${\displaystyle uv\in E}$, add ${\displaystyle (u,v)}$ to ${\displaystyle E'}$; for every ${\displaystyle u\in V_{1}}$, add ${\displaystyle (s,u)}$ to ${\displaystyle E'}$; and for every ${\displaystyle v\in V_{2}}$, add ${\displaystyle (v,t)}$ to ${\displaystyle E'}$.
• Let ${\displaystyle c_{su}=1}$ for every ${\displaystyle u\in V_{1}}$ and ${\displaystyle c_{vt}=1}$ for every ${\displaystyle v\in V_{2}}$. Let ${\displaystyle c_{uv}=\infty }$ for every bipartite edges ${\displaystyle (u,v)}$.
 Lemma The size of a maximum matching in ${\displaystyle G}$ is equal to the value of a maximum ${\displaystyle s}$-${\displaystyle t}$ flow in ${\displaystyle G'}$.
Proof.
 Given an integral ${\displaystyle s}$-${\displaystyle t}$ flow ${\displaystyle f}$ in ${\displaystyle G'}$, let ${\displaystyle M=\{uv\in E\mid f_{uv}=1\}}$. Then ${\displaystyle M}$ must be a matching since for every ${\displaystyle u\in V_{1}}$. To see this, observe that there is at most one ${\displaystyle v\in V_{2}}$ that ${\displaystyle f_{uv}=1}$, because of that ${\displaystyle f_{su}\leq c_{su}=1}$ and conservation of flows. The same holds for vertices in ${\displaystyle V_{2}}$ by the same argument. Therefore, each flow corresponds to a matching. Given a matching ${\displaystyle M}$ in bipartite graph ${\displaystyle G}$, define an integral flow ${\displaystyle f}$ as such: for ${\displaystyle uv\in E}$, ${\displaystyle f_{uv}=1}$ if ${\displaystyle uv\in M}$ and ${\displaystyle f_{uv}=0}$ if otherwise; for ${\displaystyle u\in V_{1}}$, ${\displaystyle f_{su}=1}$ if ${\displaystyle uv\in M}$ for some ${\displaystyle v}$ and ${\displaystyle f_{su}=0}$ if otherwise; for ${\displaystyle v\in V_{2}}$, ${\displaystyle f_{vt}=1}$ if ${\displaystyle uv\in M}$ for some ${\displaystyle u}$ and ${\displaystyle f_{vt}=0}$ if otherwise. It is easy to check that ${\displaystyle f}$ is valid ${\displaystyle s}$-${\displaystyle t}$ flow in ${\displaystyle G'}$. Therefore, there is an one-one correspondence between flows in ${\displaystyle G'}$ and matchings in ${\displaystyle G}$. The lemma follows naturally.
${\displaystyle \square }$

We then establish a correspondence between ${\displaystyle s}$-${\displaystyle t}$ cuts in ${\displaystyle G'}$ and vertex covers in ${\displaystyle G}$.

Suppose ${\displaystyle (S,{\bar {S}})}$ is an ${\displaystyle s}$-${\displaystyle t}$ cut in ${\displaystyle G'}$.

 Lemma The size of a minimum vertex cover in ${\displaystyle G}$ is equal to the value of a minimum ${\displaystyle s}$-${\displaystyle t}$ cut in ${\displaystyle G'}$.
Proof.
 Let ${\displaystyle (S,{\bar {S}})}$ be an ${\displaystyle s}$-${\displaystyle t}$ cut of minimum capacity in ${\displaystyle G'}$. Then ${\displaystyle \sum _{u\in S,v\not \in S \atop (u,v)\in E'}c_{uv}}$ must be finite since ${\displaystyle S=\{s\}}$ gives us an ${\displaystyle s}$-${\displaystyle t}$ cut whose capacity is ${\displaystyle |V_{1}|}$ which is finite. Therefore, no edge ${\displaystyle uv\in E}$ has ${\displaystyle u\in V_{1}\cap S}$ and ${\displaystyle v\in V_{2}\setminus S}$, i.e., for all ${\displaystyle uv\in E}$, either ${\displaystyle u\in V_{1}\setminus S}$ or ${\displaystyle v\in V_{2}\cap S}$. Therefore, ${\displaystyle (V_{1}\setminus S)\cup (V_{2}\cap S)}$ is a vertex cover in ${\displaystyle G}$, whose size is ${\displaystyle |(V_{1}\setminus S)\cup (V_{2}\cap S)|=|V_{1}\setminus S|+|V_{2}\cap S|=\sum _{u\in V_{1}\setminus S}c_{su}+\sum _{v\in V_{2}\cap S}c_{ut}=\sum _{u\in S,v\not \in S \atop (u,v)\in E'}c_{uv}}$. The last term is the capacity of the minimum ${\displaystyle s}$-${\displaystyle t}$ cut ${\displaystyle (S,{\bar {S}})}$.
${\displaystyle \square }$

The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.