\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Thursday, August 21, 2008 14:03:59}
%TCIDATA{LastRevised=Friday, November 14, 2014 14:47:26}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}
\title{Math 443/543 Graph Theory Notes 8: Pipelines and network flows}
\author{David Glickenstein}
\maketitle
\section{Pipeline problems}
Suppose you have several pipelines arranged in a complicated way (with
junctions and multiple input and output). Each pipe has a maximum capacity. We
might ask:
\begin{itemize}
\item What is the maximum amount of stuff (oil, water, electricity, etc) that
can be moved by the network from the inputs to the outputs?
\item Is a certain collection of assigned inputs and outputs able to be
attained by adjustments in the flow through the pipes?
\end{itemize}
This work is mostly from BM Chapter 7.
\section{Networks and flows}
We will recall some definitions for networks and then talk about flows.
\begin{definition}
A network $N$ is a digraph $G$ together with a capacity function
$c:E_{+}\left( G\right) \rightarrow\lbrack0,\infty]$ and two disjoint sets
of vertices $X,Y\subset V\left( G\right) .$ The vertices $X$ are called the
sources and the vertices $Y$ are called the sinks. Vertices in $G-(X\cup Y)$
are called intermediate vertices and denoted as $I.$
\end{definition}
\begin{definition}
We will consider functions $f$ from the directed edges $E_{+}\left( G\right)
$ to some set of numbers (usually positive real or positive integer. We
denote
\[
f\left( K\right) =\sum_{e\in K}f\left( e\right)
\]
if $K\subset E_{+}\left( G\right) .$ Suppose $S\subset V\left( G\right) .$
Let $\left( S,S^{c}\right) $ denote the set of all directed edges from
vertices in $S$ to vertices in $S^{c}=V\left( G\right) -S.$ We denote
\begin{align*}
f\left( S,S^{c}\right) & =f^{+}\left( S\right) \\
f\left( S^{c},S\right) & =f^{-}\left( S\right) .
\end{align*}
In particular, $f^{+}\left( v\right) $ is the sum of all values of $f$ on
arcs from $v$ and $f^{-}\left( v\right) $ is the sum of all values of $f$ on
arcs to $v.$ Also note that $f^{+}\left( S\right) =f^{-}\left(
S^{c}\right) $ and $f^{-}\left( S\right) =f^{+}\left( S^{c}\right) .$
\end{definition}
\begin{definition}
A flow through a network $N$ is a function $f:E_{+}\left( G\right)
\rightarrow\mathbb{Z}_{\geq0}$ such that
\begin{align*}
f\left( e\right) & \leq c\left( e\right) \text{ for all }e\in
E_{+}\left( G\right) \\
f^{-}\left( v\right) & =f^{+}\left( v\right) \text{ if }v\in I.
\end{align*}
\end{definition}
We think of $f$ as specifying the amount of stuff flowing through a particular
directed edge in the network. The first condition says we cannot exceed the
capacity of any one pipe. The second is a conservation condition, saying that
everything enters and leaves the network via $X$ and $Y.$
\begin{definition}
If $S\subset V\left( G\right) $ and $f$ is a flow then we define the
\emph{resultant flow out of }$S$\emph{ relative to }$f$ to be
\[
f^{+}\left( S\right) -f^{-}\left( S\right) .
\]
Similarly,\emph{ the resultant flow into }$S$\emph{ relative to }$f$\emph{
}is
\[
f^{-}\left( S\right) -f^{+}\left( S\right) .
\]
\end{definition}
The resultant flow tells how much net stuff leaves $S$ (like a flux). Note the following:
\begin{proposition}
For any $S\subset V\left( G\right) $ and flow $f,$%
\[
f^{+}\left( S\right) -f^{-}\left( S\right) =\sum_{v\in S}\left[
f^{+}\left( v\right) -f^{-}\left( v\right) \right] .
\]
\end{proposition}
Note that it is not true that
\[
f^{+}\left( S\right) =\sum_{v\in S}f^{+}\left( v\right) .
\]
\begin{proposition}
The resultant flow out of $X$ is equal to the resultant flow into $Y.$
\end{proposition}
\begin{proof}
We know that $f^{+}\left( v\right) =0$ if $v\in I,$ and so
\begin{align*}
f^{+}\left( X\right) -f^{-}\left( X\right) & =\sum_{v\in X}\left[
f^{+}\left( v\right) -f^{-}\left( v\right) \right] \\
& =\sum_{v\in Y^{c}}\left[ f^{+}\left( v\right) -f^{-}\left( v\right)
\right] \\
& =f^{+}\left( Y^{c}\right) -f^{-}\left( Y^{c}\right) \\
& =f^{-}\left( Y\right) -f^{+}\left( Y\right) .
\end{align*}
\end{proof}
\begin{definition}
The \emph{value of }$f$ is defined as
\[
\operatorname{val}f=f^{+}\left( X\right) -f^{-}\left( X\right)
=f^{-}\left( Y\right) -f^{+}\left( Y\right) .
\]
\end{definition}
The value tells how much stuff is flowing through the network.
\begin{definition}
A flow $f$ on a network $N$ is a \emph{maximal flow} if there is no other flow
on $N$ with larger value.
\end{definition}
Thus a maximal flow is one which transmits the most stuff through the network.
\begin{proposition}
For any network $N,$ there is a new network $N^{\prime}$ such that $X^{\prime
}=\left\{ x\right\} ,$ $Y^{\prime}=\left\{ y\right\} ,$ and there is a
one-to-one correspondence of flows $f$ on $N$ and flows $f^{\prime}$ on $N$'
such that
\[
\operatorname{val}f^{\prime}=\operatorname{val}f.
\]
\end{proposition}
\begin{proof}
Let $N^{\prime}$ be the network obtained from $N$ by adding vertices $x$ and
$y,$ arcs from $x$ to each element of $X$ and arcs from each element of $Y$ to
$y.$ Give the new arcs capacity equal to infinity. Given a flow $f^{\prime}$
on $N^{\prime}$, there is an obvious subflow $f$ on $N.$ Given a flow $f$ on
$N,$ we can construct the flow $f^{\prime}$ by setting
\[
f^{\prime}\left( a\right) =\left\{
\begin{array}
[c]{cc}%
f\left( a\right) & \text{if }a\in E_{+}\left( N\right) \\
f^{+}\left( v\right) -f^{-}\left( v\right) & \text{if }a=\left(
x,v\right) \\
f^{-}\left( v\right) -f^{+}\left( v\right) & \text{if }a=\left(
v,y\right)
\end{array}
\right. .
\]
We see that $\operatorname{val}f^{\prime}=\operatorname{val}f.$
\end{proof}
For this reason, we will often confine ourselves to networks with a single
source $x$ and a single sink $y.$
\begin{definition}
Let $N$ be a network with a single source $x$ and a single sink $y.$ A
\emph{cut }in $N$ is a set $\left( S,S^{c}\right) $ of arcs where $x\in S$
and $y\in S^{c}.$
\end{definition}
%
%TCIMACRO{\FRAME{ftbFU}{4.2001in}{3.1548in}{0pt}{\Qcb{A flow}}{\Qlb{network1}%
%}{networkpics1.png}{\special{ language "Scientific Word"; type "GRAPHIC";
%maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F";
%width 4.2001in; height 3.1548in; depth 0pt; original-width 9.5998in;
%original-height 7.1996in; cropleft "0"; croptop "1"; cropright "1";
%cropbottom "0";
%filename '../2012-2013/math443f12/graphics/networkpics1.png';file-properties "XNPEU";}%
%} }%
%BeginExpansion
\begin{figure}
[tb]
\begin{center}
\includegraphics[
natheight=7.199600in,
natwidth=9.599800in,
height=3.1548in,
width=4.2001in
]%
{../2012-2013/math443f12/graphics/networkpics1.png}%
\caption{A flow}%
\label{network1}%
\end{center}
\end{figure}
%EndExpansion
Consider Figure \ref{network1}. This shows a flow. Notice that it is not maximal.
\begin{definition}
The \emph{capacity} of a cut $K$ is equal to
\[
\operatorname{cap}K=\sum_{a\in K}c\left( a\right) .
\]
A \emph{minimum cut} is a cut $K$ such that there is no cut $K^{\prime}$ with
$\operatorname{cap}K^{\prime}<\operatorname{cap}K.$
\end{definition}
A minimum cut is like the \textquotedblleft weakest link\textquotedblright\ in
the chain. If one could turn the network into a linear path from $x$ to $y,$
the minimum cut would be the smallest capacity in that chain. Notice the cut
in Figure \ref{network1}.
The key theorem about maximum flows and minimum cuts is the following.
\begin{theorem}
[Max Flow/Min Cut Theorem]If $f^{\ast}$ is the maximum flow and $K_{\ast}$ is
the minimum cut, then
\[
\operatorname{val}f^{\ast}=\operatorname{cap}K_{\ast}.
\]
\end{theorem}
We will prove this soon, but first let's prove a more modest few things.
\begin{lemma}
For any flow $f$ and any cut $\left( S,S^{c}\right) $ in $N,$%
\[
\operatorname{val}f=f^{+}\left( S\right) -f^{-}\left( S\right) .
\]
\end{lemma}
\begin{proof}
We know that
\[
f^{+}\left( x\right) -f^{-}\left( x\right) =\operatorname{val}f
\]
and that
\[
f^{+}\left( v\right) -f^{-}\left( v\right) =0
\]
for any $v\in S-x.$ Thus we get that
\[
\operatorname{val}f=\sum_{v\in S}\left[ f^{+}\left( v\right) -f^{-}\left(
v\right) \right] =f^{+}\left( S\right) -f^{-}\left( S\right) .
\]
\end{proof}
\begin{theorem}
\label{valcapineq}For any flow $f$ and any cut $K=\left( S,S^{c}\right) $ in
$N,$%
\[
\operatorname{val}f\leq\operatorname{cap}K.
\]
Equality holds only if and only if $f\left( a\right) =c\left( a\right) $
for all $a\in\left( S,S^{c}\right) $ and if $f\left( a\right) =0$ for all
$a\in\left( S^{c},S\right) .$
\end{theorem}
\begin{corollary}
If $f^{\ast}$ is the maximum flow and $K_{\ast}$ is the minimum cut, then
\[
\operatorname{val}f^{\ast}\leq\operatorname{cap}K_{\ast}.
\]
\end{corollary}
Note, we have proved one half of the Max Flow/Min Cut Theorem. The other
inequality will be proven later.
\begin{corollary}
If $f$ is a flow and $K$ is a cut such that $\operatorname{val}%
f=\operatorname{cap}K,$ then $f$ is a maximum flow and $K$ is a minimum cut.
\end{corollary}
\begin{proof}
We have that
\[
\operatorname{val}f\leq\operatorname{val}f^{\ast}\leq\operatorname{cap}%
K_{\ast}\leq\operatorname{cap}K,
\]
but the assumptions imply that these are all equalities. In particular, $f$ is
a maximum flow and $K$ is a minimum cut.
\end{proof}
\begin{corollary}
\label{corfindflow}For any flow $f$ and any cut $K=\left( S,S^{c}\right) $
in $N,$ if $f\left( a\right) =c\left( a\right) $ for all $a\in\left(
S,S^{c}\right) $ and if $f\left( a\right) =0$ for all $a\in\left(
S^{c},S\right) ,$ then $f$ is a maximum flow and $K$ is a minimum cut.
\end{corollary}
\begin{proof}
[Proof of Theorem \ref{valcapineq}]We know that%
\begin{align*}
f^{+}\left( S\right) & \leq\operatorname{cap}K\\
f^{-}\left( S\right) & \geq0
\end{align*}
so
\begin{align*}
\operatorname{val}f & =f^{+}\left( S\right) -f^{-}\left( S\right) \\
& \leq\operatorname{cap}K.
\end{align*}
The equality is if $f^{+}\left( S\right) =\operatorname{cap}K$ and
$f^{-}\left( S\right) =0,$ so the second statement follows.
\end{proof}
\section{Proof of Max Flow/Min Cut Theorem}
In this section, we will consider the following types of paths (which are
different from directed paths considered earlier).
\begin{definition}
A $v_{0}v_{k+1}$-\emph{semipath} is a list $v_{0},a_{0},v_{1},a_{1}%
,v_{2},a_{2},v_{3},\ldots,a_{k},v_{k+1}$ where $v_{i}$ are vertices and
$a_{i}$ are arcs such that either $a_{i}=\left( v_{i},v_{i+1}\right) $ or
$a_{i}=\left( v_{i+1},v_{i}\right) ,$ and no vertex is repeated. Arcs of the
first type are called \emph{forward arcs} and arcs of the second type are
called \emph{reverse arcs}.
\end{definition}
We note that given a flow $f$ on a network $N$ together with a semipath $P$
from $x$ to $y,$ we can produce a new flow $\tilde{f}$ by making
\[
\tilde{f}\left( a\right) =\left\{
\begin{array}
[c]{cc}%
f\left( a\right) +\varepsilon & \text{if }a\text{ is a forward arc}\\
f\left( a\right) -\varepsilon & \text{if }a\text{ is a reverse arc}\\
f\left( a\right) & \text{otherwise}%
\end{array}
\right. ,
\]
as long as $f\left( a\right) +\varepsilon\leq c\left( a\right) $ and
$f\left( a\right) -\varepsilon\geq0.$ The construction is designed to ensure
that $f^{+}\left( v\right) =f^{-}\left( v\right) $ if $v\in I.$
We will now consider a way to use these semipaths to increase the value of a
flow. For a $xy$-path $P,$ define
\[
\iota\left( a\right) =\left\{
\begin{array}
[c]{cc}%
c\left( a\right) -f\left( a\right) & \text{if }a\text{ is a forward arc in
}P\\
f\left( a\right) & \text{if }a\text{ is a reverse arc in }P
\end{array}
\right.
\]
and define
\[
\iota\left( P\right) =\min_{a\in P}\iota\left( v\right) .
\]
Note that $\iota\left( a\right) $ is how much we can increase the forward
flow or decrease the backward flow. We can now choose a new semipath
\[
\hat{f}\left( a\right) =\left\{
\begin{array}
[c]{cc}%
f\left( a\right) +\iota\left( P\right) & \text{if }a\text{ is a forward
arc}\\
f\left( a\right) -\iota\left( P\right) & \text{if }a\text{ is a reverse
arc}\\
f\left( a\right) & \text{otherwise}%
\end{array}
\right. .
\]
Note that $\hat{f}$ is a new flow, since it satisfies the conditions to ensure
$0\leq\hat{f}\left( a\right) \leq c\left( a\right) .$ Also note that
\[
\operatorname{val}\hat{f}=\operatorname{val}f+\iota\left( P\right) .
\]
\begin{theorem}
A flow $f$ is a maximum flow if and only if $N$ contains no $xy$-semipaths $P$
with $\iota\left( P\right) >0.$
\end{theorem}
\begin{proof}
If $N$ contains such a semipath $P,$ we have shown how to increase the value
of $f,$ and so $f$ is not a maximum. Now suppose $N$ contains no such
semipaths. We let $S$ be the set of all vertices $v$ such that there is a
$xv$-semipath $P_{v}$ such that $\iota\left( P_{v}\right) >0,$ together with
$x.$ We know that $y$ is not in this set (by assumption), and so $\left(
S,S^{c}\right) $ is a cut. We will now show that each arc in $\left(
S,S^{c}\right) $ satisfies $f\left( a\right) =c\left( a\right) $ and
every arc in $\left( S^{c},S\right) $ satisfies $f\left( a\right) =0.$ By
Corollary, \ref{corfindflow} this would imply that $f$ is a maximum flow. Now
suppose $a\in\left( S,S^{c}\right) $ and $a=\left( v,w\right) .$ Then
There is a $xv$-path $P_{v}$ in $N$ such that $\iota\left( P_{v}\right) >0.$
if $f\left( a\right) 0$ then we could extend $P_{v}$ to
a $xw$-semipath. This completes the proof.
\end{proof}
Thus, in the process of the proof, we have shown that, given a flow, we can
construct a maximum flow by incrementally considering $xy$-semipaths $P$ with
$\iota\left( P\right) >0$ (these are called $f$-incremental paths in BM),
finding new flows $\hat{f},$ and continuing until there are no such semipaths
left. This flow will be a maximum and its value will be equal to the minimum
cut, also shown in the proof. Thus, we have proven the Max Flow/Min Cut Theorem.
%comment
\end{document}