%% This LaTeX-file was created by <jl> Mon Mar  9 11:44:23 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 16 3/9/98 ``To be perverse, what we'll do now is...''


\section{Max Flow}


\subsection{definitions}

\begin{itemize}
\item flow-network = directed \( G=(V,E) \) 
\item Capacities \( C(u,v)\geq 0 \) If \( (u,v)\notin E\Rightarrow c(u,v)=0 \)
\item For \( s,t\in V \) let \( s=source \), \( t=sink \)
\item flow = \( f:V\times V\rightarrow R \) s.t. 
\end{itemize}
\begin{enumerate}
\item \( f(u,v)\leq c(u,v) \)
\item \( f(u,v)=-f(v,u) \)
\item \( u\in V-\{s,t\} \) s.t. \( \sum _{v\in V}f(u,v)=0 \) 
\end{enumerate}
\begin{itemize}
\item \( |f|=\sum _{v\in V}f(s,v) \) = net flow
\end{itemize}
The max flow problem has as input a flow network and as output a flow, \( f \), with
maximum net flow.


\section{Example problems}


\subsection{bananas}

There are a set of banana producers and a set of banana consumers. We want to
maximize the number of bananas succesfully fed to consumers. Make the source
node connect to every banana producer with capacity = banana production quantity.
Make the sink node connect to every consumer with capacity = number of bananas
eaten. Connect producers to consumers with capacity = amount of shipping capacity.
Solve the problem. The solution maximizes shipping consumption.


\subsection{network flow with delays}

Nodes are connected with some capacity and some delay. We want to mazimize the
flow within some amount of time, \( t \). Expand the graph to \( G\times t=(V\times t,E_{t}) \). Two nodes \( v_{t_{1}},u_{t_{2}} \) are connected
if \( (v,u)\in E \) and \( t_{2}-t_{1}= \) delay on that edge. Solving this flow problem will give the solution.


\section{Algorithm}


\subsection{definitions}

\begin{itemize}
\item residual capacity: \( f \) = flow on \( G \), \( C_{f}(u,v)=C(u,v)-f(u,v) \)
\item residual network: \( E_{f}=\{(u,v)\in V^{2}|C_{f}(u,v)>0\} \)
\end{itemize}
Given the residual network, we need to find an ``augmenting path'' which increases
the flow. 

\begin{itemize}
\item Partition \( A,B \) of \( V \) is \( s,t \) cut if \( s\in A,t\in B \). 
\item Cost of the cut: \( C(A,B)=\sum _{u\in A,v\in B}c(u,v) \)
\item In general: \( f(A,B)=\sum _{u\in A,v\in B}f(u,v) \)
\end{itemize}

\subsection{lemma}

if \( f \) a flow on \( G \), \( G_{f} \) is a residual then

\begin{enumerate}
\item \( f' \) a flow on \( G_{f} \) iff \( f+f' \) a flow on \( G \)
\item \( f' \) max flow on \( G_{f} \) iff \( f+f' \) is a max flow on \( G \)
\item \( |f+f'|=|f|+|f'| \)
\end{enumerate}
Proof of (1) \( f' \) is flow on \( G_{f} \) then \( f'(e)\leq C_{f}(e)=C(e)-f(e) \) Which implies \( f'(e)+f(e)\leq C_{f}(e) \)


\subsection{Another lemma}

\( \forall s,t \) cuts \( A,B \) \( f(A,B)=|f| \).


\subsection{Yet another lemma}

\( |f|\leq C(A,B) \)


\subsection{Max flow min cut theorem}

The following are equivalent:

\begin{itemize}
\item \( f \) is a max flow
\item \( \exists  \) cut \( A,B \) s.t. \( C(A,B)=|f| \)
\item There does not exist an augmenting path
\end{itemize}

\subsection{Algorithm}

\begin{enumerate}
\item Find augmenting path -> none means you are done
\item Calculate residual
\item repeat
\end{enumerate}
Add up all the augmenting paths to get the flow.


\section{Analysis}

The convergence time can be very long. For integers it can be at least proportional
to \( |f| \). If you allow noninteger capacities the algorithm may not even be convergent.

\end{document}