| Graph Algorithms: Minimum-Cost Spanning Trees |
About This Exercise
This exercise is based on the information about graph properties and algorithms introduced in lectures on December 3, and December 5
The objectives of this exercise are
- to ensure that you understand Prim’s algorithm well enough to be able to trace its execution by hand on small examples;
- to help you to understand why this algorithm is correct (as well as efficient).
Please read through and try to solve the problems on this exercise before attending the tutorials during the last week of classes. The problems on this exercise will be discussed during these tutorials.
Problems
-
Trace the execution of MST-Prim on the following weighted undirected graphs. In order to obtain the same as executions, you should choose 0 as the start vertex and visit neighbours of each vertex by increasing value for the label.
-
-
What would happen if you applied Prim’s algorithm to a weighted graph G that is not connected? What, if anything, could be stated and proved about the algorithm’s output in this case?
-
Prove the following claim, which was used in the proof of correctness of both Dijkstra’s and Prim”s algorithms.
Claim: Suppose that each vertex in an undirected graph is coloured either white, grey, or black. Suppose, as well, that every neighbour of a black node is black, as well. Then the only vertices that are reachable from any black nodes are also black.
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F08/tutorials/tutorial16.html |