CompSci 163/265, Spring 2016, Homework 2

  1. (163 students:) Prove that the smallest and second-smallest weight edges in an undirected graph are always both part of the minimum spanning tree. (Hint: what does Kruskal's algorithm do with these edges?)

    (265 students:) Suppose that the vertices of a graph are colored black and white. Define an edge to be white if both its endpoints are white, black if both its endpoints are black, and gray if it has one black and one white endpoint. The blue rule shows that the smallest gray edge is always part of the minimum spanning tree. Is the second-smallest gray edge also always part of the minimum spanning tree? If so, prove it. If not, find an example where it is not.

  2. What are the smallest and largest possible numbers of rounds that Boruvka's algorithm can take to compute the minimum spanning tree of an eight-vertex connected graph? (Here a "round" means that each spanning tree in the current forest finds its smallest outgoing edge, and all these edges are added to the forest. As usual, we assume that there are no two edges with equal weights.) Give an example of an eight-vertex graph that uses the smallest possible number of rounds, and another eight-vertex graph that uses the largest possible number of rounds.

  3. The red rule can be used to prove the correctness of a "backwards Kruskal" algorithm that sorts the edges in descending order by weight and then loops through the edges in that order, deleting any edge that belongs to a cycle in the remaining graph. To test whether an edge belongs to a cycle, we can use depth first search to look for a path that does not go through the edge but connects its endpoints. What is the running time of this algorithm, including both the time for the sorting step and the time to do a depth first search for each edge? Express your answer in $O$-notation, as a function of $n$, the number of vertices, and $m$, the number of edges. (This algorithm is described in Wikipedia as the reverse-delete algorithm but the analysis on Wikipedia uses different variable names and a more sophisticated method than depth-first search to find cycles, and should not be used for your answer. Your answer should be simplified as much as possible; you may assume that $m > n$.)

  4. Give an example of a system of voter preferences for which the Borda count does not obey the Condorcet property. That is, for each of the $k!$ permutations of the set of $k$ candidates, you should specify how many voters prefer that permutation. This specification should have the property that there is one candidate who wins all head-to-head competitions against individual other candidates (the Condorcet winner), but that the Borda count chooses a different winner than this candidate. As part of your answer, specify who the Condorcet winner is and who the Borda winner is.