\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{Spring 1999}{26 May 1999}{21}

\begin{center}
\Large{\bf Problem of the Week -- 9}
\end{center}

\bigskip

Let $G = (V, E)$ be a flow network.  Let $s$ and $t$ denote the source and
sink, respectively.  Let $c(u,v)$ denote the capacity of the directed edge
$(u,v)$.  Assume that for every vertex $u$, $u$ is reachable from $s$ and $t$
is reachable from $u$.

\begin{itemize}
\item[(a)] Given a flow $f$ from $s$ to $t$, we say that an edge $(u,v)$ is
{\em saturated}\/ by $f$ if $f(u,v) = c(u,v)$; that is, the flow across the
edge equals its capacity.  Prove or disprove: If the capacity of every cut
separating $s$ and $t$ equals the flow value $|f|$, then every edge is either
saturated by $f$ or carries no flow.

\item[(b)] A {\em path flow}\/ of is a flow from $s$ to $t$ along a single path.
Give an efficient algorithm to decompose a given flow $f$ in $G$ into a set of
at most $|E|$ path flows.
\end{itemize}

\end{document}