CS 163 / CS 265 Homework 3,  due Friday, February 1


1. (a) 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.

(b) Explain why this does not violate the cut property of minimum spanning trees described in class.


2. (a) Find a weighted undirected connected graph with exactly four vertices that has the property that the Prim-Dijkstra-Jarnik algorithm will add its edges to the minimum spanning tree in a different order than Kruskal's algorithm.

(b) For your graph, which edges are in the minimum spanning tree, and in what order are they added by the Prim-Dijkstra-Jarnik algorithm? (You may choose whichever vertex you prefer as the starting vertex for this algorithm.)

(c) In what order are the same edges added by Kruskal's algorithm?


3. In an undirected weighted graph with n vertices, suppose that we compute the width of the widest path between every pair of vertices. Let S be the set of different numbers computed in this way. What is the maximum possible size of this set? That is, if we try to make a graph with as many different widths as possible, how many different widths does it have, as a function of n?
(Do not use O notation.)


4. Suppose we are holding a preference ballot with three candidates: Washington, Jefferson, and Hamilton (so each voter can choose one of the six permutations of those candidates, describing which one is their favorite, second favorite, and least favorite). There are 100 voters. Choose how many people should vote for each permutation, in such a way that that Washington is the Condorcet winner (he would win each one-on-one pairing of two candidates that he participates in) but gets the smallest number of first-place votes.


5* (CS265 students only). Describe how to construct an n-vertex directed graph such that, if the set S from problem 3 is constructed in the same way as that problem (that is, it is the set of different widths of widest paths in your graph), then the number of different widths in S will be proportional to n^2.