


\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref}

\usepackage{multicol}
\usepackage{soul}
\usepackage{xcolor}
\usepackage{graphicx}      
\usepackage{caption}                                      
\usepackage{float}                                                

\vfuzz2pt 
\hfuzz2pt 

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{fact*}{Fact}
\numberwithin{equation}{section}

\newtheoremstyle{probstyle}  
{3ex}                        
{0pt}                        
{\normalfont}                
{-3ex}                       
{\normalfont\bfseries}       
{.}                          
{.5em}                       
{}                           
\theoremstyle{probstyle}
\newtheorem{problem}{Problem}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\R}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\setlength\parindent{0pt}
\setul{.25ex}{}

\begin{document}
	\title{Math 154 Homework \#8\vspace{-3ex}}
\date{Spring 2023\vspace{-2ex}}
	\maketitle
	\begin{center}
		Due date: \textbf{11:59pm} Pacific Time on \textbf{Wed, June 7} (via \href{https://www.gradescope.com/}{Gradescope})\vspace{-2ex}
	\end{center} 
	\vskip 0ex
	\thispagestyle{empty}

\begin{problem}
	Fill out your CAPEs, and take a screenshot of the confirmation page. \\
	
	Link for CAPEs: \url{https://cape.ucsd.edu/students/}
	
	Link for TA evaluations (I think): \url{http://academicaffairs.ucsd.edu/Modules/Evals}\\\vspace{-1ex}
	
	\textit{If you don't want to fill out the CAPEs, or don't want to take a screenshot the confirmation page, that's okay! You will be given full credit for this problem as long as you submit something -- feel free to draw a picture, write a poem, or upload a favorite meme $\ddot{\smile}$}\\
\end{problem}	



\begin{problem}In each of the examples below, the gray numbers represent a flow. For each one, decide: is it a maximum flow? If so, identify a cut whose capacity is equal to the value of the flow. If not, identify an augmenting path (drawing/highlighting arcs is okay).\\
	\begin{figure}[H]
		\centering
		\begin{minipage}{.29\textwidth}
			\includegraphics[width=1\linewidth]{./augment3}
			
			\caption*{\textsf{Example A}}
		\end{minipage}\hspace{.045\textwidth}
	\begin{minipage}{.29\textwidth}
		\includegraphics[width=1\linewidth]{./augment2}
		
			\caption*{\textsf{Example B}}
	\end{minipage}\hspace{.045\textwidth}
	\begin{minipage}{.29\textwidth}
	\includegraphics[width=1\linewidth]{./augment1}
	
			\caption*{\textsf{Example C}}
\end{minipage}
	\end{figure}
\end{problem}

	\begin{problem}Use the Ford-Fulkerson Algorithm to find a maximum $st$-flow in the network shown below. Show every step of the algorithm: 
	at each step, specify on which path you are augmenting the flow (drawing/highlighting arcs is okay), and by how much. To certify that you have found a maximum flow, specify a cut whose capacity is equal to the value of the flow you have found.
	
	\begin{figure}[H]
		\centering
		\begin{minipage}{.65\textwidth}
			\includegraphics[width=1\linewidth]{./hw7_graph2}\\
			
		\end{minipage}
	\end{figure}
	\end{problem}
	
	
\begin{problem}
	In this class, we have only discussed directed graphs with a single source and a single sink; however, this is not an accurate model of many real-world directed networks (e.g., in a residential water-distribution network, every home is a sink). 	
	\begin{enumerate}[(a)]
		\item Describe how a multi-source, multi-sink network can be transformed into a network with a single source and a single sink, so that the methods we have learned in this class can be used to analyze it.
		
		\textit{More specifically: given a directed network $G$ with a set $\Sigma$ of sources and a set $T$ of sinks (and where the arcs of $G$ have capacities), describe how to construct a network $G'$ with a single source $s$ and a single sink $t$ in which the maximum value of a flow is the same as the maximum value of a flow in $G$. (The value of a flow in $G$ is the net flow leaving $\Sigma$.) Note: you will get full credit if your method is correct and clear; you do \ul{not} need to give a proof!}
		
		\item (NOT TO BE TURNED IN -- just for practice/clarification!) Use your transformation to solve the problem of finding the maximum total flow from the two sources to the three sinks in the network shown below. To certify that you have found a maximum flow in your transformed (single-source, single-sink) network, specify a cut whose capacity is equal to the value of the flow you have found.\\
		\begin{figure}[H]
			\centering
			\begin{minipage}{.59\textwidth}
				\includegraphics[width=1\linewidth]{./hw7_graph3}\\
				
			\end{minipage}
		\end{figure}
	\end{enumerate}
\end{problem}	

\end{document} 
