Minimum Weight Spanning Trees
Instructions
Recall Kruskal's algorithm for finding a minimum weight spanning tree (MWST): Repeatedly select the least expensive edge so that no cycles are created. You're done once you have a spanning tree.
1. a. Apply Kruskal's algorithm to find the MWST in position 1.
b. Apply Kruskal's algorithm to find the MWST in position 2.
2. Now, try these other algorithms. Do they find the same MWSTs as Kruskal's algorithm?
a. (Reverse Delete Algorithm) start with all the edges selected (all edges red). Now repeatedly unselect the most expensive edge, making sure the red graph is spanning and connected at each move. You're done once you've achieved a tree.
b. (Prim's Algorithm) start at one vertex. In this algorithm, you will repeatedly build up a bigger and bigger red graph. From the vertex you selected, add the least expensive edge. This creates a red graph on two vertices. Now add the least expensive edge from these two vertices to the rest of the graph. Then you have three vertices -- add the least expensive edge going to the rest of the graph. Repeat this process until there are no more vertices left to add.
3. Try dragging around the points to create a new position. Is it possible to arrange the points so that he MWST is
a. A path?
b. A "star"? (A start is a tree where all the vertices are leaves except one)
c. There are multiple MWST that tie for minimum cost?