Section 9.2: Trees and Minimum Spanning Trees

9.2 Outline

  1. Trees
    1. definition
    2. spanning tree
  2. Minimum spanning trees
    1. weight
    2. weighted graph
    3. definition
    4. Kruskal’s algorithm
    5. number-of-vertices-and-edges-in-a-tree theorem


9.2 Essential Ideas

A tree is a graph which is connected and has no circuits. A tree that is created from another graph by removing edges, but keeping a path to each vertex is called a spanning tree. If the edges of a graph have weight, then we refer to graph as a weighted graph.

Minimum Spanning Tree

A minimum spanning tree is a spanning tree for which the sum of the numbers associated with the edges is a minimum.

Kruskal’s Algorithm

To construct a minimum spanning tree from a weighted graph:

Step 1: Select any edge with minimum weight.
Step 2: Select the next edge with minimum weight amount those not yet selected.
Step 3: Continue to choose edges of minimum weight from those not yet selected, but make sure you not select any edge that forms a circuit.
Step 4: Repeat this process until the tree connects all the vertices of the original graph.

Number-of-Vertices-and-Edges-in-a-Tree Theorem

If a graph is a tree with n vertices, then the number of edges is n − 1.