\documentclass[12pt]{amsart}
\pagestyle{empty}
\usepackage[hmargin=1in,vmargin=1in]{geometry}
\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{fancyhdr} 
\usepackage[T1]{fontenc}


\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{graphicx,  epstopdf}
\usepackage{subfig}
\usepackage{color}
\usepackage{bbm}
\usepackage{subfloat}
\usepackage[draft]{fixme}
\usepackage{bm} 
\usepackage{bbm} 
\usepackage{epigraph}
\usepackage{endnotes}
\usepackage{ifpdf}
\usepackage{array}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{tikz}

\newcommand{\A}{\mathbb{A}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\ol}{\overline}
\newcommand{\J}{\mathcal{J}}
\newcommand{\X}{\mathcal{X}}
\theoremstyle{definition}
\newtheorem{prob}{Problem}
\newtheorem{extraProb}{Extra Problem}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\ext}{ext}




\begin{document}
 \thispagestyle{empty}
\begin{center} {\large \textbf{Math 409 -- Homework  4}} \smallskip \\ 
Due on Thursday, April 25\ \\ \ \\
 \end{center}

You are welcome to talk with other students in the class about problems but should write up solutions on your own. 
Solutions can be handwritten or typed but need to be legible and submitted via Gradescope by the end of the day 
on Thursday. You should justify all your answers in order to receive full credit.  


\bigskip 


\begin{prob}[Adapted from  \emph{A Course in Combinatorial Optimization} by Schrijver] \ 
\begin{itemize}
\item[(a)] Find a maximum value $s$-$t$ flow and minimum capacity $s$-$t$ cut of the following graph: 
\begin{center}

\begin{tikzpicture}[->, thick,scale=.9]
\node[circle,fill=black,inner sep=2pt, label=left:$s$] (s) at (0, 2) {}; 
\node[circle,fill=black,inner sep=2pt] (1) at (2,4) {}; 
\node[circle,fill=black,inner sep=2pt] (2) at (2,2) {}; 
\node[circle,fill=black,inner sep=2pt] (3) at (2, 0) {}; 
\node[circle,fill=black,inner sep=2pt] (4) at (4,4) {}; 
\node[circle,fill=black,inner sep=2pt] (5) at (4,2) {}; 
\node[circle,fill=black,inner sep=2pt] (6) at (4, 0) {}; 
\node[circle,fill=black,inner sep=2pt, label=right:$t$] (t) at (6, 2) {}; 
 \path (s) edge node[above]  {{\color{blue}$2$}} (1);
 \path (s) edge node[above]  {{\color{blue}$10$}} (2);
 \path (s) edge node[above]  {{\color{blue}$5$}} (3);
 \path (1) edge node[left]  {{\color{blue}$3$}} (2);
 \path (2) edge node[left]  {{\color{blue}$2$}} (3);
 \path (1) edge node[above]  {{\color{blue}$3$}} (4);
  \path (1) edge (5);
 \path (2) edge  (4); 
  \node (e1) at (2.5,3.3)  {{\color{blue}$4$}};
\node (e1) at (3.5,3.3)  {{\color{blue}$4$}};
 \path (2) edge node[above]  {{\color{blue}$2$}} (5); 
 \path (2) edge (6); 
  \path (3) edge  (5); 
     \node (e1) at (2.5,1.3)  {{\color{blue}$2$}};
\node (e1) at (3.5,1.3)  {{\color{blue}$5$}}; 
 \path (3) edge node[above]  {{\color{blue}$6$}} (6); 
  \path (4) edge node[right]  {{\color{blue}$1$}} (5);
  \path (5) edge node[right]  {{\color{blue}$7$}} (6);
   \path (4) edge node[above]  {{\color{blue}$2$}} (t);
 \path (5) edge node[above]  {{\color{blue}$4$}} (t);
 \path (6) edge node[above]  {{\color{blue}$12$}} (t);
\end{tikzpicture}
\end{center}


\item[(b)] Factories in Everett, Kent, and Spokane produce $130$, $90$, and $40$ widgets per week, respectively. 
These are transported to retailers in  Portland, Seattle, and Vancouver who can sell up to $30$, $70$, and $120$ widgets per week, respectively. The number of widgets per week that can be transported from each factory to each retailer is: \begin{center}
\begin{tabular}{c|ccc}
from$\backslash$ to & Portland & Seattle & Vancouver \\ \hline
Everett & 20&0&80\\
Kent &   30&80&30 \\
Spokane & 0&10&30 \\
\end{tabular}
\end{center}
Determine the maximum number of widgets that can be sold per week.
\end{itemize}
\end{prob}

\bigskip 

\begin{prob}
Let $G =(V,E)$ be a directed graph and let $s,t\in V$ with integer edge capacities.
Show that if $f:E\to \R_{\geq 0}$ is an $s$-$t$ flow of value $\alpha$, then there exists an $s$-$t$ flow $f':E\to \Z_{\geq 0}$ 
of value $\geq \alpha$ with $\lfloor f(e) \rfloor \leq f'(e) \leq   \lceil f(e) \rceil $ for all $e\in E$. \smallskip 

\noindent \emph{Hint:} define an auxiliary graph $G_f$ with 
edges coming from edges $e\in E$ for which $f(e)$  is non-integer with appropriate capacities and consider flow-augmenting paths in $G_f$. 
\end{prob}

\bigskip 

\emph{Problem 3 on the next page. }
\pagebreak 



\begin{prob}
Let $G=(V,E)$ be a directed graph and $s, t\in V$ and $(s,t)\not\in E$. Two $s$-$t$ paths are \emph{edge-disjoint} if they do not share any edges in common. They are \emph{vertex-disjoint} if they do not share are vertices except for $s$ and $t$. 

Recall from class that an $s$-$t$ \emph{cut} is a set $U\subset V$ with $s\in U$ and $t\not\in U$. Removing the edges in $\delta^{\rm out}(U)$ disconnects any $s$-$t$ path. 
A set $U\subset V$ is  an $s$-$t$ \emph{vertex-cut} if $s,t\not\in U$ and every $s$-$t$ path uses a vertex in $U$. Removing these vertices disconnects any $s$-$t$ path.  \smallskip 
\begin{itemize}
\item[(a)] Show that the maximum number of pairwise edge-disjoint $s$-$t$ paths equals the minimum size of $\delta^{\rm out}(U)$ for any $s$-$t$ cut $U$ of $G$.  \smallskip 
 \item[(b)] Show that the maximum number of pairwise vertex-disjoint $s$-$t$ paths equals the minimum size $|U|$ of an $s$-$t$ vertex cut $U$ of $G$. \smallskip \\ 
 \emph{Hint:} define a new graph $G'$. Replace each vertex $v\in V$ by two vertices $v',v''$ in $G'$. 
  Make an edge $(v',v'')$ and, for every edge $(v,w)$ of $G$, create an edge $(v'',w')$ in $G'$. \smallskip 
\end{itemize}


\begin{center}
\begin{tikzpicture}[->, thick,scale=.9]
\node[circle,draw] (v) at (1, 1) {$v$}; 
\node[circle,draw] (a) at (0,2) {$a$}; 
\node[circle,draw] (b) at (2, 2) {$b$}; 
\node[circle,draw] (c) at (0,0) {$c$}; 
\node[circle,draw] (d) at (2,0) {$d$}; 
\draw (a) -- (v);
\draw (c) -- (v);
\draw (v) -- (b);
\draw (v) -- (d);
\end{tikzpicture} \hspace{1in}
\begin{tikzpicture}[->, thick,scale=.9]
\node[circle,draw] (v1) at (1, 1) {$v'$}; 
\node[circle,draw] (v2) at (3, 1) {$v''$}; 
\node (a1) at (-1,2) {}; 
\node[circle,draw] (a2) at (0,2) {$a''$}; 
\node[circle,draw] (b1) at (4, 2) {$b'$}; 
\node (b2) at (5,2) {}; 
\node[circle,draw] (c2) at (0,0) {$c''$}; 
\node (c1) at (-1,0) {}; 
\node[circle,draw] (d1) at (4,0) {$d'$}; 
\node (d2) at (5,0) {}; 
\draw (a1) -- (a2);
\draw (a2) -- (v1);
\draw (c1) -- (c2);
\draw (c2) -- (v1);
\draw (v1) -- (v2);
\draw (v2) -- (b1);
\draw (b1) -- (b2);
\draw (v2) -- (d1);
\draw (d1) -- (d2);
\end{tikzpicture}

\end{center}

\end{prob}







%\bigskip 
%
%\begin{prob}
%Let $G=(V,E)$ be a directed graph with edge capacities $c:E\to \Z_{\geq 0}$ and 
%let $f : E \to \R_{\geq 0}$ be a feasible $s$-$t$ flow in that network.
%Suppose $f^*$ is a maximum $s$-$t$ flow.
%  \begin{enumerate}
%  \item[a)] Let $S \subseteq V$ with $s \in S, t \notin S$. Prove that
%  \[
%   \textrm{value}(f^*) \leq \textrm{value}(f) + \sum_{e \in \delta_{E_f}^{\rm out}(S)} c_f(e)
% \]
% where $E_f$ is the set of edges in $G_f$ and $\delta_{E_f}^{\rm out}(S) := \{ (i,j) \in E_f \mid i \in S, j \notin S\}$. \smallskip 
%\item[b)] Let $\gamma>0$ be the maximum value so that there is an $s$-$t$ path $P$ in $G_f$ with $c_f(e) \geq \gamma$ for all $e \in P$. Prove that $\textrm{value}(f^*) \leq \textrm{value}(f) + \gamma m$ where $m = |E|$.
%  \end{enumerate}
%\end{prob}



\end{document}