\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}{22 April 2011}{26}

\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
  two edges are crucial and at least three edges are not crucial.
  Mark each edge as crucial or not crucial.

  {\bf Answer:} Here is an example with three crucial edges and three
  edges that are not crucial.  Consider the graph $G$ with $5$
  vertices $s$, $v_1$, $v_2$, $v_3$, $t$, and 6 edges: $(s,v_1)$,
  $(s,v_2)$, $(s,v_3)$, $(v_1, t)$, $(v_2, t)$, and $(v_3,t)$ with
  capacities $1$, $1$, $1$, $2$, $2$, and $2$, respectively.  The
  first three edges (all out of $s$) are crucial, while the last three
  edges (all into $t$) are 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 True or False: If an edge is crucial, then it is also
  a bottleneck.

  {\bf Answer:} False.  Consider the flow network with 3 vertices $s$,
  $v$, and $t$, and two edges $(s,v)$ and $(v,t)$, each with capacity
  $1$.  Both the edges are crucial, but neither is a bottleneck.

\vfill

\newpage

\vspace*{3in}

\item True or False: If an edge is a bottleneck, then it is
  also crucial.

  {\bf Answer:} True.  

  Let $e$ be a bottleneck edge.  Since increasing the capacity of $e$
  by increases the maximum flow, it must also increase the minimum
  cut.  It thus follows that $e$ must belong to {\em every minimum
    cut}\/ separating $s$ and $t$ in $G$.

  Consider any edge $e'$ that is in a minimum cut of $G$.  If we
  decrease the capacity of $e'$, then the value of this cut will
  decrease, decreasing the maximum flow in turn.  Thus any edge in
  {\em any minimum cut}\/ separating $s$ and $t$ in $G$ is a crucial
  edge.

  The above two arguments say the following: a bottleneck edge is one
  that belongs to {\em every}\/ minimum cut, while a crucial edge is
  one that belongs to {\em some}\/ minimum cut.  It thus follows that
  every bottleneck edge is also a crucial edge.

\vfill

\end{itemize}

\end{document}