8.2 Outline

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

8.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.