|
Study Guide
Tucker: Applied Combinatorics
§4.2 Minimal Spanning Trees
Dr. Lee Eimers |
|
|
Introduction: A spanning tree is a subgraph that is a tree and visits every vertex of
the original graph. A minimal spanning tree is a spanning tree
whose sum of edge lengths (costs) is the smallest possible.
Concepts and Vocabulary:
The following boldfaced
(or italic) terms and phrases introduced in this section.
| Kruskal's Algorithm |
Minimal spanning tree
|
Prim's Algorithm |
Points of Interest:
1. Be aware that
Kruskal's Algorithm and Prim's Algorithm will not always yield the same
minimal spanning tree, but they will usually have many edges in common.
Also, the fact that they are both minimal spanning trees guarantees
that they will have the same total length, even if the trees are different.
Homework Assignment:
Do to hand in: #1,3,5,6,12
Thought for the
Day
Make the most of the best
and the least of the worst.
--Robert Louis Stevenson--
Ninety percent of this
game is half mental.
Yogi Berra