\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{courseMacros}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\num}[1]{\mbox{{\em num}}[#1]}
\newcommand{\parent}[1]{\mbox{{\em parent}}[#1]}

\head{1390}{Algorithms}{Winter 2001}{12 March 2001}{22}

\begin{center}
\Large{\bf Sample Solution to Problem Set 5}
\end{center}

{\bf 1. (30 points) Minimum spanning trees} 
\begin{itemize}
\item 
Suppose $T_1$ and $T_2$ are distinct minimum spanning trees for graph
$G$.  Let $(u,v)$ be the lightest edge (smallest weight edge) that is
in $T_2$ and is not in $T_1$.  Let $(x, y)$ be any edge that is in
$T_1$ and not in $T_2$.  Show that $w(x, y) \ge w(u,v)$.

{\bf Answer:} Suppose we add edge $(x,y)$ to $T_1$.  This creates a
cycle $C$.  By the MST property, it follows that the weight of every
edge in $C$ is at most $w(x, y)$.  Furthermore, at least one edge in
$C$ is in $T_1$ and not in $T_2$, because otherwise $T_2$ has a
cycle.  Let this edge be $(a, b)$.  Thus, it follows that $w(x, y) \ge
w(a, b)$.  Since $(u,v)$ is the lightest edge that is in $T_1$ and not
in $T_2$, we have $w(u, v) \le w(a, b)$.  This implies that $w(x, y)
\ge w(u, v)$, thus proving the desired claim.

\item
Prove that if the weights on the edges of a connected, undirected
graph are distinct, then there is a unique minimum spanning tree.

{\bf Answer:} Let, if possible, there be two distinct minimum spanning
trees $T_1$ and $T_2$.  We will derive a contradiction.  Let $(u,v)$
be the smallest weight edge in $T_1$ that is not in $T_2$, and let
$(u', v')$ be the smallest weight edge in $T_2$ that is not in $T_1$.
Since all the edges weights are distinct, we have either $w(u,v) <
w(u', v')$ or $w(u', v') < w(u,v)$.  Without loss of generality,
assume the former.  Now suppose we add the edge $(u,v)$ to $T_2$.
This forms a cycle, say $C$, in $T_2$.  Cycle $C$ contains at least on
edge that is in $T_2$ and not in $T_1$, because otherwise $T_2$ has a
cycle.  Let this edge be $(x, y)$.  By the definition of $(u', v')$,
we have $w(u', v') \ge w(x, y)$.  But $w(u',v') > w(u,v)$, implying
that $w(x,y) > w(u,v)$, violating the MST property of $T_2$.  This
yields a contradiction.
\end{itemize}

{\bf 2. (20 points) Bottleneck bandwidth} 

One can model a communication network by a weighted directed graph
$G$, in which the vertices of $G$ represent the nodes of the network,
the edges of $G$ represent the communication links of the network and
the weight of an edge is the bandwidth of the link.  We define the
{\em bottleneck bandwidth}\/ of a path $p$ as the bandwidth of the
minimum-bandwidth link in $p$.

Design and analyze an efficient algorithm to determine a path with the
largest bottleneck bandwidth from a given node $s$ to a given node $t$.
If no path from $s$ to $t$ exists, then your algorithm must indicate
so.  Briefly justify the correctness of your algorithm.  Analyze the
running time of your algorithm.  You may assume that the bandwidth of
every link is positive.  ({\em Hint:} Modify Dijkstra's algorithm.)

{\bf Answer:} We can modify Dijkstra's algorithm by mainly replacing
the ``$\min$'' operation by ``$\max$'', the ``$+$'' operation by
``$\min$'', and the ``$>$'' operation by ``$<$''.  These entail three
kinds of changes in the algorithm.

First, consider the initialization routine {\sc
Initialize-Single-Source}$(G,s)$.  We will set $d[v]$ to $0$ for all
$v \neq s$ and we set $d[s]$ to $\infty$.

Second, the {\sc Relax}$(u,v,w)$ operation will change to the following code.
\begin{tabbing}
{\sc Relax}$(u,v,w)$\\
1. \= \algif\ \= $d[v] < \min\{d[u], w(u,v)\}$\\
2. \>  \> \= $d[v] = \min\{d[u], w(u,v)\}$\\
3. \> \> \> $\pi[v] = u$
\end{tabbing}

Finally, in {\sc Dijkstra}$(G,w,s)$, instead of extracting the vertex
with the minimum $d$ value, we extract the vertex with the maximum $d$
value.

The proof of Dijkstra's algorithm for shortest paths proceeds by
showing two claims: (a) $d[u] \ge \delta(s,u)$ for all $u$ at all
times, and (b) at the time $u$ is extracted from $Q$, $d[u] =
\delta(s,u)$.  For establishing these two claims, the two main
properties that we need are (i) if the last edge on the shortest path
from $s$ to $v$ is $(u,v)$, then $\delta(s,v) = \delta(s,u) + w(u,v)$,
and (ii) for any edge $(u, v)$, $\delta(s,v) \le \delta(s,u) + w(u,v)$
(triangle inequality).

In our present situation, we are seeking the path with the largest bottleneck
bandwidth -- not the shortest path.  Let $\Delta(s,u)$ denote the bottleneck
bandwidth of the path from $s$ to $u$ with the largest bottleneck bandwidth.
Claims (a) and (b) translate to the following two claims: (A) $d[u] \le
\Delta(s,u)$ for all $u$ at all times, and (b) at the time $u$ is extracted
from $Q$, $d[u] = \Delta(s,u)$.  We can establish these two claims by showing
properties (I) and (II) analogous to the properties (i) and (ii) above: (I) if
the last edge on the path with the largest bottleneck bandwidth from $s$ to $v$
is $(u,v)$, then $\Delta(s,v) = \min\{\Delta(s,u), w(u,v)\}$, and (II) for any
edge $(u, v)$, $\Delta(s,v) \ge \min\{\delta(s,u), w(u,v)\}$.  Note that all
we have done is to replace $+$ by $\min$ and $\le$ by $\ge$.  Both claims~(I)
and~(II) can be proved in a manner very similar to the proofs of~(i) and~(ii),
that we went through in class.

One worthwhile remark is that the proof of claim~(i) for the
shortest-paths case can be done by establishing the optimal
substructure property -- that is, subpaths of shortest paths are
shortest paths, something that is not always true for the bottleneck
bandwidth case!  Nevertheless, claim (I) can be proved by a simple
argument based on contradiction.

{\bf 4. (20 bonus points)} Exercise 7.49, page 384.  

{\bf Answer:} Starting from an arbitrary vertex $r$, we obtain a
depth-first traversal of the graph.  Since the graph is a tree, all
the edges are tree edges.  During the depth-first traversal, we also
determine, for each node $u$, $\num{u}$, the number of nodes that were
discovered from $u$.  This can be easily calculated by noting that 
\[
\num{u} = 1 + \sum_{\mbox{\scriptsize edge} (u,v) \atop v \neq {\scriptsize \parent{u}}} \num{v}.
\]
After the depth-first traversal, we start from root $r$ and check
whether there exists a child $v$ such that $\num{v} > n/2$.  If not,
then removing $r$ and its incident edges leaves no subtree with more
than $n/2$ vertices, and we are done.  Otherwise, there exists a
vertex $v$ with $\num{v} > n/2$.  We now set $r$ equal to $v$ and
repeat the above test, until we find a node $r$ such that $\num{r} >
n/2$ and there is no child $v$ of $r$ with $\num{v} > n/2$.  Then
removing $r$ and its incident edges leaves no subtree with more than
$n/2$ vertices, and we are done.

The running time of the algorithm is $O(n)$ since the depth-first
search takes $O(n)$ time (note that the number of edges is $n - 1$)
and the remainder of the algorithm also takes $O(n)$ time.
\end{document}
