\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\usepackage{etex}
\usepackage[all]{xypic}
\usepackage{lpic}
\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 3
	
	\large Assigned Monday 10/07. Due Wednesday 10/09.
\end{center}

\textbf{1.} Find a maximum flow in the networks below. Use duality to prove optimality.

\begin{center}
\begin{tabular}[h]{c@{\qquad}c@{\qquad}c}
\begin{lpic}{"flow011"(,1.5in)}
\lbl[br]{25,90;5}
\lbl[br]{29,72;2}
\lbl[tr]{29,49;4}
\lbl[tr]{25,30;6}
\lbl[t]{60,7;3}
\lbl[b]{60,116;4}
\lbl[tr]{48,108;3}
\lbl[br]{48,85;1}
\lbl[br]{52,50;3}
\lbl[tr]{52,35;2}
\lbl[br]{52,15;6}
\lbl[bl]{95,95;10}
\lbl[bl]{90,75;3}
\lbl[br]{96,52;5}
\lbl[tl]{95,25;1}
\end{lpic}
&
\begin{lpic}[]{"flow012"(,1.5in)}
\lbl[br]{25,90;3}
\lbl[br]{29,72;7}
\lbl[tr]{29,49;1}
\lbl[tr]{25,30;5}
\lbl[t]{60,7;10}
\lbl[b]{60,116;7}
\lbl[br]{55,90;4}
\lbl[bl]{54,70;2}
\lbl[br]{52,52;6}
\lbl[tr]{52,35;2}
\lbl[bl]{95,95;2}
\lbl[bl]{90,75;1}
\lbl[br]{96,52;3}
\lbl[tl]{95,25;6}
\end{lpic}
&
\begin{lpic}[]{"flow026"(,1.5in,)}
\lbl[br]{22,50;12}
\lbl[tr]{22,15;6}
\lbl[b]{22,35;2}
\lbl[b]{45,60;3}
\lbl[tr]{42,51;6}
\lbl[br]{42,40;5}
\lbl[b]{45,33;5}
\lbl[tr]{42,24;9}
\lbl[tl]{42,10;10}
\lbl[b]{72,60;5}
\lbl[tr]{68,51;9}
\lbl[b]{72,33;1}
\lbl[tr]{68,24;13}
\lbl[br]{68,12;5}
\lbl[t]{74,4;6}

\lbl[bl]{100,48;4}
\lbl[b]{100,33;10}
\lbl[tl]{100,16;3}
\end{lpic}
\\
\textbf{a.} & \textbf{b.} & \textbf{c.}
%&
%
%\scalebox{0.75}{
%\begin{lpic}[draft]{"flow030"(,2in)}
%\lbl[br]{22,50;12}
%\lbl[tr]{22,15;6}
%\lbl[b]{22,35;2}
%\lbl[b]{45,60;3}
%\lbl[tr]{42,51;6}
%\lbl[br]{42,40;5}
%\lbl[b]{45,33;5}
%\lbl[tr]{42,24;9}
%\lbl[tl]{42,10;10}
%\lbl[b]{72,60;5}
%\lbl[tr]{68,51;9}
%\lbl[b]{72,33;1}
%\lbl[tr]{68,24;13}
%\lbl[br]{68,12;5}
%\lbl[t]{74,4;6}
%
%\lbl[bl]{100,48;4}
%\lbl[b]{100,33;10}
%\lbl[tl]{100,16;3}
%\end{lpic}}
%\\
%\textbf{c.} & \textbf{d.}\\
%\multicolumn{2}{c}{
%\begin{lpic}[draft]{"flow044"(,1.5in)}
%\end{lpic}}
%\\
%\multicolumn{2}{c}{\textbf{e.}}
\end{tabular}
\end{center}

\textbf{2.} Find a maximum matching for each bipartite graph below. Use duality to show optimality.

\begin{center}
\begin{tabular}[h]{c@{\qquad}c@{\qquad}c}
\includegraphics[width=2in]{match004} 
&
\includegraphics[width=2in]{match020} 
&
\includegraphics[width=2in]{match023}
\\
\textbf{a.} & \textbf{b.} & \textbf{c.}
\\
\includegraphics[width=2in]{match026} 
&
\includegraphics[width=2in]{match033} 
&
\includegraphics[width=2in]{match062}
\\
\textbf{d.} & \textbf{e.} & \textbf{f.}
\\ 
\end{tabular}
\end{center}

\clearpage
\textbf{3.} Find an optimal closure for each directed graph below with prescribed vertex weights.


\begin{center}
\begin{tabular}[h]{c@{\qquad}c}
\includegraphics[height=1.5in]{closure001} 
 & 
\includegraphics[height=0.9in]{closure006}
\\
\textbf{a.} & \textbf{b.} \\
\includegraphics[height=2.5in]{closure022}
&
\includegraphics[height=2in]{closure026}\\
 \textbf{c.} & \textbf{d.}
\end{tabular}
\end{center}

\clearpage
\textbf{4.} Determine the (local) $uv$-edge-connectivity of the following undirected graphs. Use duality to show optimality. (Hint: Use Menger's Theorem.)

\begin{center}
\begin{tabular}[h]{c@{\qquad}c@{\qquad}c}
\includegraphics[width=2in]{connectivity003} 
&
\includegraphics[width=2in]{connectivity002} 
&
\includegraphics[width=2in]{connectivity010b}
\\
\textbf{a.} & \textbf{b.} & \textbf{c.}\\
\includegraphics[height=2in]{connectivity060} 
&
\includegraphics[width=2in]{connectivity018} 
&
\includegraphics[width=2in]{connectivity010}
\\
\textbf{d.} & \textbf{e.} & \textbf{f.}
\end{tabular}
\end{center}


\textbf{5.} Determine the global edge-connectivity of the above undirected graphs.



\end{document} 