FF's Notes
← Home

Minimum Spanning Tree

Nov 1, 2023
graph

Spanning Tree

Let $H = (V, T)$ be a subgraph of an undirected graph $G=(V,E)$. $H$ is a spanning tree of $G$ if $H$ is both acyclic and connected.

The following are equivalent:

  1. $H$ is spanning tree of $G$.
  2. $H$ is acyclic and connected.
  3. $H$ is connected and has $|V| - 1$ edges.
  4. $H$ is acylic and has $|V| - 1$ edges.
  5. $H$ is minimally connected.
  6. $H$ is maximally acyclic.

Minimum Spanning Tree

Spanning tree with minimum costs.

Cayley's theorem: The complete graph on $n$ nodes has $n^{n-2}$ spanning trees.

Cut Property

Let $S$ be any subset of nodes $S \neq V$. Let edge $e = (v,w)$ be the minimum cost edge with one end in $S$ and the other in $V-S$.

Then every MST contains the edge $e$.

Kruskal's Algorithm

  1. Starts without any edges and insert edges from $E$ in order of increasing cost.
  2. For edge $e_i$, insert it if it does not create a cycle with all inserted edges, and discard otherwise.

Prim's Algorithm

  1. Start with a root node $S = {s}$, and try to grow a tree from $S$
  2. Add the node $v$ connected with $S$ that can be attached as cheaply as possible.

Inspired by # Dijkstra's Algorithm with difference:

  1. Compare with every node in known set $S$, not root node. Thus no distance needed.

Cycle Property

Let $C$ be any cycle in $G$. Let edge $e$ be the most expensive edge on C. Then $e$ does not belong to any MST.

Reverse-Delete Algorithm

  1. Start with the full graph $(V,E)$ and being deleting edges in order of decreasing cost.
  2. Delete edges as long as doing do would not actually disconnect the graph.