\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newif\ifanswer
\answertrue
\head{CS5800}{Algorithms}{Spring 2011}{April 11 2011}{24}

\begin{center}
\Large{\bf Quiz 5}
\end{center}

\noindent {\Large Name:~}\leaders\hrule\hfill\ 

\smallskip

{\bf (3 + 3.5 + 3.5 = 10 points) Crucial edges in a network flow}

Consider a network flow (directed) graph $G$ with a positive integer
capacity on each edge, a source $s$, and a sink $t$.  We say that an
edge $e$ is {\em crucial} if decreasing its capacity by one will
decrease the maximum flow from $s$ to $t$ by one.

\begin{itemize}
\item[{\bf (a)}] Give an example network flow graph in which at least
  three edges are crucial and at least two edges are not crucial.
  Mark each edge as crucial or not crucial.

\vfill

\vfill
\end{itemize}

Recall that an edge $e$ is a {\em bottleneck}\/ if increasing its
capacity by one will increase the maximum flow from $s$ to $t$ by one.
In the following two parts, indicate whether the given statement is
true or false.  If you claim that the statement is true, give a brief
proof; otherwise, give a counterexample.

\begin{itemize}
\item[{\bf (b)}] True or False: If an edge is a bottleneck, then it is
  also crucial.

\vfill

\newpage

\vspace*{3in}

\item[{\bf (c)}] True or False: If an edge is crucial, then it is also
  a bottleneck.

\vfill

\end{itemize}

\end{document}