Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Spanning Tree

A spanning tree of a graph is a subgraph of that is a tree and includes all vertices of . It may leave out some edges of . With vertices it always has exactly edges.

Key facts:

  • has a spanning tree if and only if is connected
  • a graph can have many different spanning trees
  • "spanning tree" only makes sense together with a given graph

Minimum Spanning Tree

A minimum spanning tree (MST) of a weighted graph is a spanning tree with the minimum possible total edge weight. In the example below, one spanning tree has total weight while the MST has total weight .

Application

Each vertex is a city and each edge weight is the cost of laying a fibre optic link between two cities. The MST is the cheapest set of links that still connects every pair of cities, possibly through other cities.

MST versus Shortest Path Tree

These two trees are often confused:

  • an MST minimises the total weight of all edges in the tree, and has no start vertex
  • a shortest path tree minimises the path length from one start vertex to every other vertex, see Dijkstra's Algorithm

An MST is built greedily with Kruskal's algorithm.