\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{url}
\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}

\title{CS140 - Assignment 9\\\small{Due: \textbf{Tuesday},  Nov. 22nd at 11:59pm}}
\author{}
\date{}

\begin{document}

\maketitle

\vspace{-0.5in}

\begin{enumerate}

\item \textbf{[13 points]} Go with the flow

%\begin{center}
%\includegraphics[scale=0.8]{figures/graph.jpg}
%\end{center}

\begin{enumerate}
\item \textbf{[2 points]} Find the maximum flow $f$ for the graph above \textit{and} a minimum cut.  Don't just state the max-flow value, but annotate the graph with the flow along each edge.

\item \textbf{[2 points]} Draw the residual graph $G_F$ at this maximum flow.

\item \textbf{[2 points]} An edge of a network is called a \textit{bottleneck edge} if increasing its capacity results in an increase in the maximum flow (without changing any other capacities in the network).  List all of the bottleneck edges in the above network.

\item \textbf{[2 points]} Give a simple example of a valid flow network which has no bottleneck edges.

\item \textbf{[5 points]} Describe clearly (or write pseudocode for) an efficient algorithm to identify all the bottleneck edges in a network.  \textit{Hint:} It may be useful to calculate the max-flow first.  State your running time.

\end{enumerate}

\item \textbf{[3 points]} Determine wether the following statement is true or false.  If false, give a counterexample.  If true, give a brief (but concrete) explanation justifying the statement.

Given a flow network $G$, let $(L, R)$ be a minimum capacity cut in the flow graph.  If we increase the capacity of all of the edges in the graph by 1, then $(L, R)$ is still a minimum capacity cut in this new graph.

\item \textbf{[6 points]} You're opening up a hip new restaurant chain with $k$ restaurants spaced out throughout LA county.  You have $n$ people that have registered to attend opening night that are scattered throughout the county. You're trying to tell people with restaurant to go to such that:

\begin{itemize}

\item[-] Each person shouldn't have to drive more than 30 minutes to get to their assigned restaurant (you can assume you can calculate the time it would take for a person to go to any given resteraunt).

\item[-] So as not to overload the staff at any one restaurant, you'd like to distribute these people evenly across so that is each restaurant should have $n/k$ people attend on opening night (you may assume that $n$ divides equally into $k$).

\end{itemize}

\begin{enumerate}

\item Describe an algorithm that determines if this is possible.  Make sure to state clearly what you're checking for to determine if it is possible.

\item Very briefly, justify that your approach is correct (in particular, how you've handled all of the problem constraints).

\item If it is possible, describe how to determine where to send each of the $n$ people.

\end{enumerate}

\end{enumerate}

\end{document}
