ABSTRACT
You may remember from Chapter 3 that a tree is a connected graph with no cycles. Trees are one of the most popular classes of graphs, because they have so many applications in computer science and operations research and because they are so useful in pure mathematics proofs. We will see a pure mathematics use for trees in Chapter 11, and in this chapter, we will concentrate on aspects of trees that lead to applications. First we will investigate spanning trees-given a graph, can you find a subgraph that is a tree and covers all the vertices of (spans) the graph? If so, how? What if the graph has values assigned to the edges, and we want the lowest (or highest) total value in our spanning tree? Most of our approaches will involve a particular type of algorithm (called greedy, but parsimonious in nature), so we will briefly discuss its use across graph theory.
