Selected topics in finite mathematics/Minimum spanning trees

A minimum spanning tree for a graph is a subgraph that includes every vertex, is a tree, and has the smallest possible total edge weight.

Objectives

connect all vetices, avoid making a circuit, and create subgraph with the least weight

Details

Tree: A subgraph containing some of the vertices and edges, such that there are no cycles in the tree. The tree must also be connected.

Spanning: A subgraph spans the original graph if it includes every vertex.

Minimum Spanning Tree: a tree within a graph with the smallest possible total edge weights.

To find a minimum spanning tree, begin by putting the edge with the lowest weight in your tree. Make sure it doesn't create a cycle. Repeat this process until you have spanned the entire graph.