\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\usepackage{etex}
\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.

\vspace{1em}
\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.


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

\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})$.

\end{document} 