Selected topics in finite mathematics/Minimum spanning trees
Jump to navigation
Jump to search
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[edit | edit source]
connect all vetices, avoid making a circuit, and create subgraph with the least weight
Details[edit | edit source]
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.