Assignment 5
due by the end of class Wednesday February 28 2001.
-
Show that for all n there are inputs for which the
running time of the simple implementation of P/D MST
is bounded below by a constant times n cubed.
Hint: complete the argument made in the lecture.
- Prove that the operation "decrease-key"
can be performed in log n time in a heap with n keys.
- The straightforward implementation of Prim's
MST algorithm takes Theta(n^3) time;
storing only the best edge for each fringe vertex
takes Theta(n^2) time.
[See my fall 2000 204 notes, week 9 page 7.]
Suppose that the values of "best edge for each fringe vertex"
are stored in a priority queue implemented
with a heap, instead of in an array.
Explain in detail how this leads to a
running time of O(n+mlog(n)).
- It is known that if no two edges of a weighted
graph have the same weight, then the graph
has a unique minimum spanning tree (e.g. see Baase).
Prove or disprove the two following statements.
- If a weighted graph has an MST
in which all edge weights are distinct,
then that is the only MST of that weighted graph.
- Let x be the maximum weight of an edge
of an MST T of a weighted graph G,
and suppose that in G,
for every possible weight at most x,
there is at most one edge with that weight.
Then T is the only mst of G.