Selected topics in finite mathematics/Minimum spanning trees

From Wikiversity
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.

Examples[edit | edit source]

Nonexamples[edit | edit source]

FAQ[edit | edit source]

Homework[edit | edit source]

Homework Solutions[edit | edit source]