Graph Theory Lessons
Lesson 47:
Minimal Spanning Trees
We already know that a graph could have several spanning trees. Suppose we look at all the spanning trees of a weighted graph and rank them by the total weight of their edges. The tree with least weight, called the Minimal Spanning Tree, is particularly important. Actually, since we could have ties it is possible for a graph to have more than one minimal spanning tree.
Imagine the weighted graph to represent a railroad system with the weights being the cost of maintaining the tracks. Now suppose you wanted to minimize the maintenance costs without disconnecting the graph. Why would the minimal spanning tree be of interest? If the graph is disconnected you can't, of course, have a minimal spanning tree (why?) but the union of the minimal spanning trees of the individual components is called a Minimal Spanning Forest.
| |
|
Java Web Start activity:
The Java Web Start application below demonstrates Kruskal's
algorithm for finding a minimal spanning tree. As you draw your
graph on the left side the minimal spanning tree will be displayed
in red. To get a step by step explanation click on the button
labeled "Step".
Java Web Start activity:
Here is another Java Web Start application, this time to demonstrate
Prim's algorithm for finding a minimal spanning tree. Play with both
applications until you can see the difference between the two.
In the Petersen program you can run the two algorithms by clicking Properties | Spanning Trees | Minimal Spanning Trees and choosing Kruskal or Prim.
© C. Mawata
