CompSci 163/265, Spring 2015, Homework 5

1. In an undirected weighted graph, recall that the width of a path is the minimum weight of one of its edges, and define the width of a cut to be the maximum weight of one of its edges. Prove that, for every two vertices $s$ and $t$, the width of the widest path from $s$ to $t$ equals the width of the narrowest cut separating $s$ from $t$ (the cut with the smallest possible width). Hint: Use the fact that the maximum spanning tree contains the widest path to find a cut with this width. You may assume that no two edges have equal weights if it simplifies your proof.

2. The graph of a cube has eight vertices and twelve edges. Find weights for these edges such that Boruvka's algorithm takes three iterations to construct the minimum spanning tree of the graph.

3. (163 only): Find a weighted undirected graph $G$, and a minimum spanning tree $T$ of $G$, such that at least one of the minimum weight edges in $G$ does not belong to $T$. Explain why this does not violate the cut property of minimum spanning trees described in class.

(265 only): Let $G$ be a graph in which all edge weights are positive. Describe a method for constructing a spanning tree that maximizes the product of the edge weights (instead of their sum). Explain why your method is correct.

4. (163 only): Describe how to modify Kruskal's algorithm to compute a maximum spanning tree instead of a minimum spanning tree.

(265 only): Describe how to modify the maximum-spanning-tree version of Kruskal's algorithm to compute a widest cycle in a given weighted undirected graph. (That is, among all simple cycles, we want the one whose lightest edge is as heavy as possible.)