\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}[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}