Section 9.2: Trees and Minimum Spanning Trees

by

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.