\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{5: Flows}{Due Friday, Week 3}

Do \textbf{one} of the following \textbf{three} problems!

\begin{enumerate}
\item In class, we proved that Ford-Fulkerson holds for all rational-valued capacity functions.  Extend this result to all real-valued capacity functions, by proving the following theorem:
\begin{theorem}
(Ford-Fulkerson:)  Suppose that $G$ is a graph with source and sink nodes $s,t$ and a real-valued capacity function $c$.  Then the maximum value of any feasible flow $f$ on $G$ is equal to the minimum value of any cut on $G$. 
\end{theorem}
\item  This graph is meant to illustrate the dangers of irrational flows and the Ford-Fulkerson algorithm for finding maximum flows.  Consider the following graph $G$, which we've drawn below along with three distinct paths $A,B,C$:
\begin{center}
\includegraphics[width=5in]{flow_augmenting_path_doom.pdf}
\end{center}
Suppose that the capacity function on this graph has $c(v_2 \to v_1) = 1, c(v_2 \to v_3) = 1, c(v_4 \to v_3) = \Phi = \frac{\sqrt{5}-1}{2}$, and the capacity of all other edges is some really large constant: say the speed of light ($3 \cdot 10^8$.)

Run Ford-Fulkerson on this graph by picking the following specific augmenting paths:
\begin{enumerate}
\item At the very start, augment on the path $(s,v_2), (v_2,v_3), (v_3,t)$.
\item Now, augment on path $B$.
\item Now, augment on path $C$.
\item Now, augment on path $B$.
\item Now, augment on path $A$.
\item Repeat, starting at step (b).
\end{enumerate}
Show that all of these paths are augmenting, and thus that Ford-Fulkerson could conceivably pick these paths; show that the process above converges to a flow with value $2+\sqrt{5}$, and finally notice that this is far far less than its maximum possible value!
\item Suppose that you have a $n \times n$ matrix of real numbers $A$.  Let $c_i$ denote the sum of all of the elements in the $i$-th column of $A$, and $r_i$ denote the sum of all of the entries in the $i$-th row of $A$.  A \textbf{rounding} of $A$ is the act of taking each value $a_{ij}, r_i, c_j$ and rounding these numbers either up or down to integer values.  A rounding is called \textbf{successful} if in the resulting rounded matrix $A_R$, the row and column sums are the same things as the values we chose to round the $r_i, c_j$'s to.  We give an example of a successful and an unsuccessful rounding below:
\begin{align*}
 \begin{array}{|c|c|c|c|} 
\hline0.6 &0 .8 & 2.7 & \cellcolor{lightgray}{ 4.1}\\\hline
 0.3 & 1.9 & 2.7 & \cellcolor{lightgray}{ 4.9}\\\hline
 2.3 & 0.4 & 0.4 &  \cellcolor{lightgray}{3.1} \\\hline
 \cellcolor{lightgray}{3.2} & \cellcolor{lightgray}{ 3.1} &  \cellcolor{lightgray}{5.8} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array} ~~\xrightarrow[\textrm{rounding}]{\textrm{unsuccessful}}~~   \begin{array}{|c|c|c|c|} 
\hline1 &1 & 3 & \cellcolor{lightgray}{ 5}\\\hline
 0 & 2 & 3 & \cellcolor{lightgray}{ 5}\\\hline
 2 & 0 & 0 &  \cellcolor{pink}{3} \\\hline
 \cellcolor{lightgray}{3} & \cellcolor{lightgray}{ 3} &  \cellcolor{lightgray}{6} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array},\\
 \begin{array}{|c|c|c|c|} 
\hline0.6 &0 .8 & 2.7 & \cellcolor{lightgray}{ 4.1}\\\hline
 0.3 & 1.9 & 2.7 & \cellcolor{lightgray}{ 4.9}\\\hline
 2.3 & 0.4 & 0.4 &  \cellcolor{lightgray}{3.1} \\\hline
 \cellcolor{lightgray}{3.2} & \cellcolor{lightgray}{ 3.1} &  \cellcolor{lightgray}{5.8} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array} ~~\xrightarrow[\textrm{rounding}]{\textrm{~~successful~~}}~~  \begin{array}{|c|c|c|c|} 
\hline1 &0& 3 & \cellcolor{lightgray}{ 4}\\\hline
 1 & 2 & 2 & \cellcolor{lightgray}{ 5}\\\hline
 2 & 1 & 0 &  \cellcolor{lightgray}{3} \\\hline
 \cellcolor{lightgray}{4} & \cellcolor{lightgray}{ 3} &  \cellcolor{lightgray}{5} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array}.\\
\end{align*}
Prove, ideally using the Max-Flow-Min-Cut theorem, that every real-valued $n \times n$ matrix has a successful rounding.
\end{enumerate}



\end{document}