\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\usepackage{etex}
\usepackage{lpic}
\usepackage[all]{xypic}
\setlength{\parindent}{0em}

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}

\begin{document}

\thispagestyle{empty}



\begin{center}
	\Large\bf MATH 482, Spring 2013 - Homework 2
	
	\large Assigned Wednesday 09/18. Due Friday 09/20.
	
	Problems Assigned: 1, 2, 3.a., 4.c.
\end{center}

\textbf{1.} (\emph{Assigned! 5pts}) Consider the graph below.
\begin{center}
	\includegraphics[height=1.5in]{networkflow}
\end{center}
Find a shortest path and prove optimality using duality.\\

Label the vertices in the left column from top to bottom as $a$, $b$, $c$, and the vertices in the right column from top to bottom as $i$, $j$, $k$.
The shortest path is $s, b, j, t$ of weight $11$.
One dual solution (which assigns real values to all vertices) is to let
\[
y_s = 0,\quad y_a = 3,\quad y_b = 4, \quad y_c = 8, \quad y_i = 10, \quad y_j = 6, \quad y_k = 5,\quad y_t = 11.
\]
Observe that for every edge $uv$, we have $y_v \leq y_u + w(u,v)$, as required by the dual solution. 
Since $y_1 = 11$, all paths have weight at least $11$.


\clearpage
\textbf{2.} (\emph{Assigned! 5pts})  Consider the network below with given edge values, forming an integer feasible flow.
\begin{center}
	\includegraphics[height=2in]{flowproba}
\end{center}
Demonstrate a list of path and cycle flows whose sum is this flow.\\

Below is a path flow, a cycle flow, and two cycle flows. 
The sum of the flows across these flows matches the flow above.
\begin{center}
	\includegraphics[height=1.75in]{flowproba-sol1}\\
	\includegraphics[height=1.75in]{flowproba-sol2}\\
	\includegraphics[height=1.75in]{flowproba-sol3}
\end{center}

\clearpage
\textbf{3.} \\
\textbf{a.} (\emph{Assigned! 5pts})  Consider the network below and on the left, with given capacity and flow values. (Recall that an edge label $c,x$ has capacity $c$ and flow-value $x$.) Find augmenting paths and augment the flow until it has value 8.\\
\textbf{b.} Consider the network below and on the right, where every edge has capacity 1 and the numbers below are the flow values. Find augmenting paths and augment the flow until it has value 5.
\begin{center}
\begin{tabular}[h]{c@{\qquad}c}
	\includegraphics[height=1.65in]{flowprobb} & 
	\includegraphics[height=1.65in]{flowprobc}\\
	Problem 3.a. & Problem 3.b.
\end{tabular}
\end{center}

The two augmenting paths below complete this problem.
\begin{center}
\begin{tabular}[h]{c@{\qquad}c}
	Problem 3.a. & Problem 3.b. \\
	\includegraphics[height=1.65in]{flowprobb-sol1} & 
	\includegraphics[height=1.65in]{flowprobc-sol1}\\
	\includegraphics[height=1.65in]{flowprobb-sol2} & 
	\includegraphics[height=1.65in]{flowprobc-sol2}
\end{tabular}
\end{center}

\clearpage
\textbf{4.}\\
\textbf{a.} Construct a network such that there is a unique maximum flow, but multiple distinct minimum cuts.\\
\textbf{b.} Construct a network such that there is a unique minimum cut, but multiple distinct maximum flows.\\
\textbf{c.} (\emph{Assigned!} 5pts) Prove that the network below has a unique maximum flow and a unique minimum cut. (\emph{Hint:} Find a max flow and a min cut. Use the flow to prove there is a unique cut, and use the cut to prove there is a unique flow.)
\begin{center}
	\includegraphics[height=2in]{flowprobd}
\end{center}
\emph{Note: I did not get to this result in class, so here is the result you should use for 4.c.}

\textbf{Cor:} Let $\vx$ be a feasible $rs$-flow and $\delta(R)$ be an $rs$-cut. 
Then, $f_{\vx}(s) = c(\delta(R))$ if and only if $x_e = c(e)$ for all $e \in \delta(R)$ and $x_e = 0$ for all $e \in \delta(\overline{R})$.

\begin{proof}(\emph{There is a unique minimum cut.})
Consider the following flow.
\begin{center}
	\includegraphics[height=2in]{flowprobd-sol1}
\end{center}
If this flow is maximum, then the only edges that can be used in a minimum cut are those that are at capacity or have zero flow.
These edges are below, including the zero-flow edges being dotted.
\begin{center}
	\includegraphics[height=2in]{flowprobd-sol2}
\end{center}
Any cut must use only edges in this set of edges, and must use them in their given direction.
Since $a,i,c,$ and $k$ are reachable from $r$ using edges not in this set, they must be in $R$ for any minimum $rs$-cut $\delta(R)$.
Since $s$ is reachable from $b$ and $j$ using edges not in this set, they must not be in $R$ for any minimum $rs$-cut $\delta(R)$.
Thus, these restrictions uniquely define $R$, and $\delta(R)$ uses exactly these edges, as shown below.
\begin{center}
	\includegraphics[height=2in]{flowprobd-sol3}
\end{center}
This cut matches our flow, so they are both optimal, and this cut is unique.

(\emph{There is a unique maximum flow.}
Consider our minimum $rs$-cut $\delta(R)$ with $R = \{ r, a, c, i, k\}$.
Consider unknown flow values in our flow network.
\begin{center}
	\includegraphics[height=2in]{flowprobd-sol4}
\end{center}
If we have a maximum flow, then by the corollary we must have full capacity for edges in $\delta(R)$ and no flow for edges not in $\delta(\overline{R})$.
\begin{center}
	\includegraphics[height=2in]{flowprobd-sol5}
\end{center}
For these values of flow, the vertex $i$ requires an incoming flow of value $16$, which determines the flow across $ai$ and across $ra$.
The vertex $k$ requires an incoming flow of value $11$, which determines the flow across $ck$.
Then, the vertex $c$ requires an incoming flow of value $16$, which determines the flow across $rc$.
The vertex $b$ requires an outgoing flow of value $21$, which determines the flow across $bj$.
Finally, the vertex $j$ requires an outgoing flow of value $24$, which determines the flow across $js$.
\begin{center}
	\includegraphics[height=2in]{flowprobd-sol6}
\end{center}
\end{proof}

\end{document} 