TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:43:13Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
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''' (or 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>
}}

=== The 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 is easy to see 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 ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:19:41Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
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''' (or 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>
}}

=== The 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 is easy to see 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.

}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:06:22Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
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''' (or 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>
}}

=== The 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 is easy to see 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.
}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:05:34Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
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''' (or 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>
}}

=== The 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 is easy to see 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,
}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:02:56Z

172.21.3.81: /* Cuts */

== Flow ==

=== The maximum flow problem ===
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''' (or 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>
}}

=== The 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 is easy to see 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.

}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===