Short note: Spanning tree and applications

A spanning tree of a connected graph G is a subgraph that contains all the vertices of G and is a tree (connected, with no cycles). Every spanning tree of a graph with n vertices has n − 1 edges. One can be found by removing edges from cycles until no cycles are left, or by a DFS/BFS traversal.

  G:  a --- b          one spanning tree:  a --- b
      |  \  |                              |      
      d --- c                              d --- c      (edges ab, ad, dc)

G (a square with diagonal ac) has 4 vertices and 5 edges; each spanning tree keeps 3 of them.

In a weighted graph, the minimum spanning tree has the least total weight. It is found by Kruskal's algorithm (repeatedly add the cheapest edge that does not create a cycle) or Prim's algorithm (grow the tree from a vertex using the cheapest connecting edge).

Applications:

• Designing the cheapest network of cables, pipes or roads connecting all sites.
• Network protocols: the spanning-tree protocol avoids loops in switched LANs; broadcasting and multicast routing.
• Approximating the travelling salesman problem.
• Image segmentation and clustering.