$$\newcommand{\Ord}{\mathcal{O}}$$

次小生成樹演算法與證明

題目

考慮一張無向的加權圖 $G=\{V,E,w(s,t)\}$,求 $G$ 的生成樹中,權重非嚴格第二大的生成樹。

演算法

  1. 先找出 $G$ 的最小生成樹 $G_{M}=\{V_M,E_M,w_M(s,t)\}$
  2. 設 $S=\emptyset$
  3. 對於所有的邊 $e = \{s,t\} \in E-E_M$
    1. 找到 $G_M$ 中,點 $s$ 到點 $t$ 的路徑上,邊長最長的邊 $e’$
    2. 將 $G_M-e’-e$ 加入至集合 $S$ 中
  4. $S$ 中權重和最小的樹即為所求

證明

先考慮一個樸素作法,因為次小生成樹與最小生成樹至少有一條邊不一樣,因此,可以枚舉最小生成樹的邊,將其刪除之後,再求最小生成樹,那次小生成樹必然會是這$V-1$顆樹中的其中一種。

接下來,可以證明刪掉一條邊的圖,存在一個最小生成樹,與原來的最小生成樹只有一條相異的邊。考慮 Kruskal 演算法,如果把第 $i$ 個加入最小生成樹的邊 $e_i = (s_i, t_i)$ 刪除的話,並不影響加入第 $i$ 條邊之前的決策。接下來,將原來最小生成樹第 $i+1$ 條邊到 $V-1$ 條邊加入這一個新的樹中,那會得到兩個獨立的兩個連通塊 (原來MST砍掉 $s$ 到 $t$ 的邊 ),此時再找到一條最小的邊 $e’$ 將這兩個連通塊接在一起,就形成了一個最小生成樹,且這顆樹只有一條邊與原來的樹不一樣。

為什麼會是最小生成樹呢?因為 $e’$ 必然是 Kruskal 在 $e_i$ 以後才被考慮的邊,且 $e’$ 不會影響加入這一條邊之後的決策。考慮這兩條邊之間的其他邊 $e_m$ 的決策過程:

  1. 如果 $e_m$ 的兩端點不連接 $s_i$, $t_i$ 的連通塊的話,那這條邊的決策就不被影響
  2. 如果 $e_m$ 的兩端點連接 $s_i$, $t_i$ 的連通塊的話,那這條邊就是比 $e’$ 更小連接方法,那與 $e’$ 的定義矛盾,因此不存在這種情形。

因此這個方法會是 Kruskal 的決策過程,故作出來的樹是最小生成樹。因此就可以推出存在一的次小生成樹,是與其最小生成樹相差一條邊的樹。

時間複雜度

  • 步驟 1 若使用 Kruskal’s algorithm,複雜度為 $\Ord(E\log E)$
  • 步驟 3.1 若使用 最近公共祖先 (Lowest Common Ancestor, LCA) 的倍增法,單次可以在 $\Ord(\log V)$ 的時間求出 $e’$
  • 集合 $S$ 實作上,只需要紀錄加入及刪除哪一條邊即可,都可以在 $\Ord(1)$ 時間完成

故可以在 $\Ord(E\log E)$ 的時間求出次小生成樹