Minimum Spanning Tree

Definition

在 $G=(V, E)$中，找尋一組$E$的subset $T$使 $w(T) = \sum_{(u,v) \in T} w(u, v)$，且$T$為acyclic，所以$T$必定是一顆tree。

Growing a MST

找尋MST的做法，可以用greedy的方式，演算法如下：

GENERIC-MST(G, w)
  A = ∅ 
  while  A does not form a spanning tree
    find an edge (u, v) that is safe for A
    A = A ∪ {(u, v)}
  return A

我們要證明的就是在這個步驟做完，形成的spanning tree就是一顆MST。

Proofs

在證明GENERIC-MST之前，我們先定義幾個term：cut & light edge。

Cut

一個undirected grpah $G = (V, E)$ 的一個Cut $(S, V - S)$，代表$V$的一個partition，也就是說 $\forall v \in V$，$v \in S$ or $v \in V-S$。

另外對於一個edge set $A$，如果$A$裡面的edge不cross (有一個edge $(u, v)$ ，其中 $u \in S$ and $v \in V - S$) 一個cut $C$ ，則我們稱 $C$ respects $A$。

Light edge

如果一個edge $(u, v)$ 是 cross 一個 cut $C$的edge裡面，weight 最低的edge，則被稱為light edge。

Theorem 1

Statement: Let $G = (V,E)$ be a connected, unidrected graph with a real-valued weight function $w$ defined on $E$. Let A be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V - S)$ be any cut of $G$ that respects $A$, and let $(u, v)$ be a light edge crossing $(S, V - S)$. Then, edge $(u, v)$ is safe for $A$.

Proof:

我們可以利用反證法(proof by contradiction)來證明。我們定義light edge $(u, v)$加入$A$形成的tree為$A'$，如果edge $(u, v)$不safe，則存在一個crossing edge $(u', v')$，$(u', v')$加入$A$形成$A''$，使得$w(A'') < w(A')$。

但$w(A'') = w(A) + w((u', v'))$，而$w(A') = w(A) + w((u, v))$，因為$w(A'') < w(A')$，可得到$w((u', v')) < w((u, v))$，而已知$(u, v)$是light edge，故任一crossing edge $(u', v')$，$w((u', v')) \geq w((u, v))$，因此$w(A'') < w(A')$與已知矛盾，故假設錯誤，因此light edge $(u, v)$對A safe。

Corollary 1

Statement: Let $G = (V, E)$be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let A be a subset of $E$ that is included in some minimum spanning tree for $G$, and let $C = (V_c, E_c)$ be a connected component (tree) in the forest $G_A = (V, A)$. If $(u, v)$ is a light edge connecting $C$ to some other component in $G_A$, then $(u, v)$ is safe for $A$.

Proof:

The cut $(V_C, V - V_C)$ respect $A$，所以根據theorem 1，light edge $(u, v)$ is safe for $A$。