Homework 6

Due Wednesday, March 25

1. Determine if the following statements are true or false. Prove your claims.

   (a) If $e$ is an edge of a minimum spanning tree of $G$, then $e$ is an edge with the least cost in some cutset in $G$.

   (b) If $e$ is an edge with the least cost in a cycle of $G$, then $e$ belongs to a minimum spanning tree of $G$.

2. In general, a graph $X'$ is a subgraph of a graph $X$ if the node and edge sets of $X'$ are subsets of the node and edge sets of $X$, respectively. Let $(V, T)$ be a minimum spanning tree of $G$ and $G' = (V', E')$ be a connected subgraph of $G$.

   (a) Prove that $(V', E' \cap T)$ is a subgraph of a minimum spanning tree of $G'$.

   (b) Is $(V', E' \cap T)$ a minimum spanning tree of $G'$? Prove your claim.

3. Suppose now that $G$ has $n$ nodes and $m$ edges and its edge costs are distinct. For a spanning tree $T$ of $G$, the bottleneck cost of $T$ is the largest of all edge costs of $T$. A minimum-bottleneck spanning tree of $G$ is a spanning tree of $G$ whose bottleneck cost is minimum amongst those of all spanning trees of $G$.

   (a) Is every minimum-bottleneck spanning tree of $G$ a minimum-spanning tree of $G$? Prove your claim.

   (b) Design an efficient algorithm to find a minimum-bottleneck spanning tree of $G$.

CPSC 320 home page