Minimum Spanning Tree

A minimum spanning tree is a the minimum amount of edge weights that produce a spanning tree of graph G.

Properties

• Fully connected component, and any edge remove produces a disconnect

• Acyclic, and the addition of any edge produces a cycle.

• N-1 edges (where n = number of nodes)

  • Justification: Every node is connected to at least 1 other node, and 1 edge is used to connect 2 nodes.

• $\sum_{i=0}^n$ = minimum

Applications

• Graph point clustering

• Image segementation

• Circuit design

Kruskels vs Prims

• Prims: When you have a lot of edges relative to the number of nodes. E.g. (close to $n^2$ - dense graph)

• Kruskels: When you have a few amount of edges