- spanning tree
- Minimum spanning trees
- weighted graph
- Kruskal’s algorithm
- 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.
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.
If a graph is a tree with n vertices, then the number of edges is n − 1.