TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:28:29Z

172.21.5.190: /* Integrality of polytopes */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

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.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le 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}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

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

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\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}\,.</math>
On the other hand, summing flow over edges,
:<math>\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}\,.</math>
Therefore,
:<math>\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}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\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}</math>.
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.

{{Theorem|Lemma|
:A flow <math>f</math> 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 <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\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}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\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}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

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

== Unimodularity ==

=== Integer Programming===

=== Integrality of polytopes ===
A point in an <math>n</math>-dimensional space is integral if all its coordinates are integers.

A polyhedron is said to be '''integral''' if all its vertices are integral.

There always exists an optimal solution which is a vertex in <math>P</math>. For integral <math>P</math>, all vertices are integral.

{{Theorem|Theorem (Hoffman 1974)|
: If a polyhedron <math>P</math> is integral then for all integer vectors <math>\boldsymbol{c}</math> there is an optimal solution to <math>\max\{\boldsymbol{c}^T\boldsymbol{x}\mid \boldsymbol{x}\in P\}</math> which is integral.
}}

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:10:55Z

172.21.5.190: /* Cuts */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

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.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le 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}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

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

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\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}\,.</math>
On the other hand, summing flow over edges,
:<math>\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}\,.</math>
Therefore,
:<math>\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}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\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}</math>.
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.

{{Theorem|Lemma|
:A flow <math>f</math> 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 <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\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}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\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}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

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

== Unimodularity ==

=== Integer Programming===

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:09:55Z

172.21.5.190: /* Integer Programmings */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

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.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le 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}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

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

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\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}\,.</math>
On the other hand, summing flow over edges,
:<math>\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}\,.</math>
Therefore,
:<math>\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}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\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}</math>.
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.

{{Theorem|Lemma|
:A flow <math>f</math> 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 <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\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}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\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}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

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

== Unimodularity ==

=== Integer Programming===

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}

Combinatorics (Fall 2010)/Flow and matching

2010-12-26T07:04:57Z

172.21.5.190: /* Unimodularity and total unimodularity */

== Flow and Cut==

=== Flows ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

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.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le 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}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

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

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\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}\,.</math>
On the other hand, summing flow over edges,
:<math>\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}\,.</math>
Therefore,
:<math>\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}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== Augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\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}</math>.
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.

{{Theorem|Lemma|
:A flow <math>f</math> 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 <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\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}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\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}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

{{Proof|
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.

Again, let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.

Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}

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

== Unimodularity ==

=== Integer Programmings===

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===
{{Theorem|Definition (Unimodularity)|
:An <math>n\times n</math> integer matrix <math>A</math> is called '''unimodular''' if <math>\det(A)=\pm1</math>.
:An <math>m\times n</math> integer matrix <math>A</math> is called '''total unimodular''' if every square submatrix <math>B</math> of <math>A</math> has <math>\det(B)\in\{1,-1,0\}</math>, that is, every square, nonsingular submatrix of <math>A</math> is unimodular.
}}

{{Theorem|Theorem|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>B</math> be a basis of <math>A</math>, and let <math>\boldsymbol{b}'</math> be the corresponding coordinates in <math>\boldsymbol{b}</math>. A basic solution is formed by <math>B^{-1}\boldsymbol{b}'</math> and zeros. Since <math>A</math> is totally unimodular and <math>B</math> is a basis thus nonsingular, <math>\det(B)\in\{1,-1,0\}</math>. By [http://en.wikipedia.org/wiki/Cramer's_rule Cramer's rule], <math>B^{-1}</math> has integer entries, thus <math>B^{-1}\boldsymbol{b}'</math> is integral. Therefore, any basic solution of <math>A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}</math> is integral, which means the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}

{{Theorem|Theorem (Hoffman-Kruskal 1956)|
:Let <math>A</math> be an <math>m\times n</math> integer matrix.
:If <math>A</math> is totally unimodualr, then for any integer vector <math>\boldsymbol{b}\in\mathbb{Z}^n</math> the polyhedron <math>\{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral.
}}
{{Proof|
Let <math>A'=\begin{bmatrix}A & -I\end{bmatrix}</math>. We claim that <math>A'</math> is also totally unimodular. Any square submatrix <math>B</math> of <math>A</math> can be written in the following form after permutation:
:<math>B=\begin{bmatrix}
C & 0\\
D & I
\end{bmatrix}</math>
where <math>C</math> is a square submatrix of <math>A</math> and <math>I</math> is identity matrix. Therefore,
:<math>\det(B)=\det(C)\in\{1,-1,0\}</math>,
thus <math>A'</math> is totally unimodular.

Add slack variables to transform the constraints to the standard form <math>A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0}</math>. The polyhedron <math>\{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\}</math> is integral if the polyhedron <math>\{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\}</math> is integral, which is implied by the total unimodularity of <math>A'\,</math>.
}}