Spanning Tree

Spanning Tree / Spanning Forest

「生成樹」。從一張圖分離出一棵樹,包含圖上所有點。可能有許多種。

當一張圖完全連通,則有生成樹。當一張圖不連通,則沒有生成樹,而是許多棵「生成子樹」構成的「生成森林」。宛如DFS tree與DFS forest的關係。

生成樹也可以有權重。當圖上每條邊都有權重時,生成樹的權重為樹上每條邊的權重總和。

Minimum Spanning Tree

「最小生成樹」。權重最小的生成樹。可能有許多種。

Minimum Spanning Tree: Kruskal's Algorithm

用途

求出無向圖的其中一棵最小(大)生成樹。若是圖不連通,則是求出其中一叢最小(大)生成森林。

想法

一、一個單獨的點,可以視作一棵最小生成子樹MSS。

二、兩棵MSS連結成一棵MSS,以兩棵MSS之間權重最小的邊進行連結,顯然是最好的。

三、三棵MSS連結成一棵MSS,先連結其中兩棵連結權重最小的MSS,才連結第三棵,總是比較好。

由以上三點歸納出:以一張圖上權重最小、次小、……的邊,連結各棵MSS,總是比較好。

連結所有MSS,最後得到最小生成樹(森林)。

演算法

一、圖上每一個點,各自是一棵最小生成子樹MSS。
二、圖上所有邊,依照權重大小,由小到大排序。
三、嘗試圖上所有邊,作為最小生成樹(森林)的邊:
 甲、兩端點分別位於兩棵MSS,也就是產生了橋:
   用這條邊連結兩棵MSS,合併成一棵MSS。
   這條邊是最小生成樹(森林)上的邊。
 乙、兩端點皆位於同一棵MSS,也就是產生了環:
   捨棄這條邊。

亦可求出最大生成樹(森林):

精髓:不斷連結兩棵MSS、合併兩個集合。

時間複雜度

一、排序圖上所有邊。O(ElogE)。

二、連結MSS,採用「Disjoint-set Forest」。O(Eα(E,V))。

總時間複雜度為O(ElogE)。

如果兩點之間有多條邊,預先以Graph Traversal掃描一次所有邊,保留權重最小的邊,仍可求得正確答案。兩點之間只剩下一條邊,邊的總數至多C{V,2} = V(V-1)/2條。時間複雜度O(ElogE)可以改寫成O(ElogV²) = O(2ElogV) = O(ElogV)。

迴圈的部份也可以寫成這樣。

UVa 908 10369

Minimum Spanning Tree: Prim's Algorithm

用途

求出無向圖的其中一棵最小(大)生成樹。

演算法

仿效「Shortest Path: Dijkstra's Algorithm」。

差異:Dijkstra's Algorithm屢次找不在樹上、離根最近的點,Prim's Algorithm屢次找不在樹上、離樹最近的點。

另一個差異:選擇特定一點做為起點,得到不同的最短路徑樹;選擇任意一點做為樹根,得到相同的最小生成樹。

時間複雜度

圖的資料結構為adjacency matrix的話,便是O(V²);圖的資料結構為adjacency lists的話,還是O(V²)。

如同Dijkstra's Algorithm,使用Priority Queue、Fibonacci Heap可以得到更低的時間複雜度。

UVa 10034 10147 10307 10397 10842

© 2010 tkcn. All rights reserved.

Minimum Spanning Tree: Borůvka's Algorithm

用途

求出無向圖的其中一棵最小(大)生成樹。若是圖不連通,則是求出其中一叢最小(大)生成森林。

演算法

一、圖上每一個點,各自是一棵最小生成子樹MSS。
二、每棵MSS同時找權重最小、索引值最小的聯外邊,相互連接。
 口、聯外邊是MSS之間的邊,不是MSS之內的邊。
 口、聯外邊可能重複,無妨。
 口、聯外邊顯然不會形成環。
三、重複步驟二,直到形成最小生成樹(森林)。

找權重最小的聯外邊,以得到最小生成樹;當權重一樣小,則找索引值最小的聯外邊,以避免聯外邊形成環。聯外邊的索引值,可以改成聯外邊的兩端點索引值。

證明很簡單:圖上任意一只環,環上權重最大、索引值最大的邊,絕不會被選中。過程中無法形成環,只會形成樹。每一點都聯外,權重又最小,所以是最小生成樹。

時間複雜度

一、每回合尋找權重最小、索引值最小的聯外邊。O(V+E)。

二、連接MSS。採用「Disjoint-sets Forest」,每回合每個點都呼叫了union與find,森林結構維持在最佳狀態,union與find的總時間複雜度,從O(Eα(E,V))下降至O(E)。

三、回合數。最差情況:每回合MSS兩兩成對互連,MSS總數量僅下降一半,共logV個回合。平均情況:圖上的邊呈隨機分布,僅1至2個回合。【待補證明】

最差時間複雜度為O((V+E)logV),可以簡單寫成O(ElogV)。平均時間複雜度為O(V+E)。

Minimum Spanning Tree: Edmonds' Algorithm

用途

求出有向圖的其中一棵最小(大)生成樹。

有向圖上,以權重最小的邊,連結兩棵有向MSS,不見得形成有向MSS。直接套用無向圖的演算法,邊的方向亂七八糟,無法形成有向生成樹。必須設計其他演算法。

想法

生成樹的基本概念是:連接圖上各點的樹。從這個概念下手,並且考慮邊的方向性,得到兩個粗糙的演算法:

有向圖上,每一個點,如果要被連結到,都要至少有一條出邊,除了樹葉以外。
每一個點,找權重最小的出邊,會比較好。
有向圖上,每一個點,如果要被連結到,都要剛好有一條入邊,除了樹根以外。
每一個點,找權重最小的入邊,會比較好。

出邊有許多條,入邊只有一條,從入邊下手比較容易。

樹根是個例外,樹根沒有入邊。但是我們可以假定我們已經知道最小生成樹的樹根是哪個點,如此就不必顧慮例外了。設計好演算法之後,用試誤法嘗試各種樹根即可。

Minimum Arborescence

預先指定樹根的有向最小生成樹。個人感覺這個詞彙不太討喜。

水母【尚無正式名稱,因為像水母就把它叫做水母】

運氣好的時候,各點的最小入邊,剛好形成一棵生成樹,而且是最小生成樹。

運氣普通的時候,各點的最小入邊,通常形成許多隻水母。

各點各取一條入邊,一旦入邊們形成環,此環一定只有出邊、沒有入邊。環與出邊,形成一個特別的圖:很多棵樹,一只環串起了樹根。又像是太陽、又像是水母。

把水母改裝成最小生成子樹

最小生成樹不得有環。水母有環,是不合格的。

水母是權重最小的連結方式,最小生成樹的權重則略高、等高於水母。使用窮舉法,嘗試拆除水母的每一條邊,並且更改為另一條邊,從中找到權重增加最少的邊。

一、更改水母環的邊:
 甲、新邊是由其他水母連入:水母環消失。變成其他水母腳。很好!
 乙、新邊是由自身水母環連入:水母環變小。連結權重無故變大,不可取。
 丙、新邊是由自身水母腳連入:水母環變大。多了一些點可供聯外。
二、更改水母腳的邊:
  水母環不變,連結權重無故變大,不可取。

有好處的只有一甲、一丙。歸納出:只需要更改水母環的邊,讓水母環消失或者變大,從中選擇權重增加最少的拆除方式。

演算法

水母環的入邊,全部看過一遍,找到權重增加最少的入邊。

已經看過的入邊,修改成權重增加量,然後收縮水母環,就不用看第二遍了。

壹、刪去所有自環:自己連向自己的邊。
貳、圖上每一點嘗試做為樹根。
 一、刪去樹根的全部入邊。也可以將權重設定為無限大。
 二、判斷樹根能不能連到圖上各點。否則生成樹不存在。
 三、重複以下步驟,直到形成生成樹為止:
  甲、每一個點,找出權重最小的入邊。O(V+E)
    形成一群水母。
  乙、調整水母環的入邊的權重,修改成權重增加量。O(V+E)
    w(a, x) -= w(å, x),
    x是水母環上一點。
    åx是x點的最小入邊,也是水母環上的邊。
    ax是x點的其他入邊。
  丁、收縮水母環,成為一點。O(V+E)

Kruskal's Algorithm連結多個MSS。一旦發現造成環的邊,就直接捨棄;一旦發現造成橋的邊,就一定保留。

Edmonds' Algorithm連結多隻水母。總是留下造成環的邊(形成水母環),並且嘗試各種打開環的方式:有時候擴大水母環,有時候兩隻水母連結成一隻水母。

時間複雜度

一、每回合找出各點的最小入邊。O(V+E)。

二、回合數。最差情況是每回合產生一個水母,水母環只有兩點。水母環收縮之後,整張圖只減少一個點。圖上有V個點,最多收縮V-1次水母環,總共V-1個回合。

三、窮舉V個點,嘗試做為樹根。

時間複雜度為O(VVE)。

演算法

窮舉樹根,再仿效Dijkstra's Algorithm,時間複雜度為O(V³)。有差異的地方,不影響時間複雜度:

一、縮環最多V-1次(兩點縮成一點)。縮環得到的新點,最多V-1個。總點數最多2V,仍是O(V)。

二、縮環,採用Disjoint-sets Forest。O(Eα(E,V))。

如同Dijkstra's Algorithm,使用Priority Queue、Fibonacci Heap可以得到更低的時間複雜度。

UVa 11183

Minimum Bottleneck Spanning Tree

Bottleneck

一張圖上、一棵生成樹上、一條路徑上,權重最小的邊,稱作「瓶頸」。

然而,為了前後文連貫,此處將定義暫時更改為權重最大的邊。古早人也是如此定義。

Minimum Bottleneck Spanning Tree

一張圖的所有生成樹當中,權重最大的邊(瓶頸),其權重最小的生成樹,稱作「最小瓶頸生成樹」,可能有許多棵。

以下只討論無向圖。一個簡單的方式,是以最小生成樹MST,作為最小瓶頸生成樹MBST。

Kruskal's Algorithm造就MST的最後一條邊,就是瓶頸。

證明

既然膽敢宣稱MST是MBST,那麼也許MST與MBST當中有些相近的性質。有時不妨率由舊章,以現有的MST性質,推定未知的MBST性質。大膽假設、小心求證。

MST有著一個關鍵性質:以權重最小的邊,連接兩棵MST,可以構成一棵MST。依樣畫葫蘆,MBST或許也有著一個關鍵性質:以權重最小的邊,連接兩棵MBST,可以構成一棵MBST。

此處用中文囉哩囉嗦證明之。若用數學式子,也許只消兩行:

甲、連接的邊,權重大於等於原本兩棵MBST的瓶頸權重,則會成為新樹的瓶頸。由於選擇了權重最小的邊當作連接的邊,連接的邊又是新樹的瓶頸,新樹的瓶頸權重當然也最小──新樹是一棵MBST。

乙、連接的邊,權重小於原本兩棵MBST的瓶頸權重,則不會成為新樹的瓶頸。新樹的瓶頸由原本兩棵MBST的瓶頸二選一,選權重大的那個成為新樹的瓶頸。因為原本兩棵MBST的瓶頸權重已經最小了,新樹的瓶頸權重當然也最小──新樹是一棵MBST。

新性質是正確的!由於MST和MDST都可以用權重最小的邊構造而得,因此在每一種MST演算法當中,每個步驟的MST也隨時是MBST。

儘管MST一定是MBST,但是小心MBST不見得是MST。儘管兩棵MBST以權重最小的邊相連,一定是一棵MBST,但是一棵MBST移除權重最大的邊,不見得是兩棵MBST。

演算法

事實上MBST有一個O(V+E)的演算法。

一、二分搜尋法,搜尋圖上所有邊的權重,找出MBST的瓶頸。
  二分時,採用O(N)的中位數演算法。
二、每枚舉一個瓶頸,權重小於等於瓶頸的邊,皆可作為生成樹。
 甲、掃描一次,找出權重小於等於瓶頸的邊。
 乙、Graph Traversal,判斷圖上各點是否連通。
   若連通,則此瓶頸定可形成生成樹。反之則無法形成生成樹。
 丙、連通的點,合併為一點。以後就不需要重新遍歷了。
三、若要構造生成樹,在乙步驟,去掉形成環的邊(back edge)即可。
  MST與MBST相異之處就在於:
  MBST可以去掉環上任意一條邊,MST必須去掉環上權重最大的邊。

Minimum Bottleneck Path

一張無向圖上,兩點之間的所有路徑當中,瓶頸權重最小的一條路徑,稱作「最小瓶頸路徑」,可能有許多條。

最小生成樹上的所有路徑,都是原圖的最小瓶頸路徑。證明方式同前,只是把生成樹改成了路徑。

如果需要所有兩點之間的最小瓶頸路徑的其中一個瓶頸,則可以使用DP:從邊數為一的最小瓶頸路徑開始,逐步推導出更長的最小瓶頸路徑。O(V²)時間建表、O(1)時間查詢。

亦可利用「Lowest Common Ancestor」。O(VlogV)時間建表、O(logV)時間查詢。

有向圖的情況,就請讀者自行研究了。最簡單的作法是修改最短路徑演算法。

UVa 11354 12176 12655

Second-best Minimum Spanning Tree

一張無向圖,權重最接近最小生成樹的另一棵生成樹,稱作「次小生成樹」。可能與最小生成樹權重相等。可能有許多棵。

找到一棵次小生成樹,演算法共兩種。

一、求出一棵最小生成樹。(建議使用Kruskal's Algorithm)
二、窮舉每一條最小生成樹上的邊pq:
 甲、從圖上刪除此邊,重新求出一棵最小生成樹。(邊不必重新排序)
 乙、記下此樹。
三、剛剛得到的V-1棵樹,權重最小者便是次小生成樹。

窮舉不要的邊,刪除後再重找。時間複雜度O(VEα(E,V))。

一、求出一棵最小生成樹。
二、求出樹上所有兩點ij之間,權重最大的邊(瓶頸)。記為E(i,j)。
  (所有兩點間最小瓶頸路徑。)
三、窮舉每一條不在最小生成樹上的邊pq:
 甲、把邊pq添加到最小生成樹上,勢必形成環。
 乙、然後拆除邊E(p,q),勢必又形成樹,此樹權重已然盡量少。
 丙、記下此樹。
四、剛剛得到的E-(V-1)棵樹,權重最小者便是次小生成樹。

窮舉想要的邊,添加後再修正。步驟一與二各有數種演算法,時間複雜度也跟著改變。時間複雜度可達到O(ElogV)。

UVa 10600 10462 ICPC 5713

Minimum Diameter Spanning Tree

Minimum Diameter Spanning Tree

一張無向圖的所有生成樹當中,直徑最小的生成樹,可能有許多棵。

目前尚未有直接的演算法。目前是以絕對中心當作起點的最短路徑樹SPT,作為最小直徑生成樹MDST。關於絕對中心與最短路徑樹,可參考「Central Vertex」。

證明(Hassin & Tamir, 1995)

證明很簡單。在原論文中,證明過程可以寫成五行數學式子,閒來無事不妨朝聖一下。以下則是講得詳細一點:

甲、絕對中心的偏心距是最小的,位於SPT的直徑中央。半徑(偏心距)最短,所以直徑也是最短。把直徑拉成一直線來看,就清楚多了。

d(c, x) = d(c, y)

因為 d(c, x) 會盡量小,所以 2 d(c, x) = d(c, x) + d(c, y) 也會盡量小。

乙、絕對中心的SPT上面隨便一條路徑,都小於等於直徑長度。把路徑藉由絕對中心切成兩段,就清楚多了。

  d(p, q)
= d(c, p) + d(c, q)
≤ d(c, x) + d(c, y)   切成兩條,分別PK。
  d(i, j)
≤ d(c, i) + d(c, j)   切成兩條,分別PK。
≤ d(c, y) + d(c, y)

最短路徑樹不見得是最小直徑生成樹

各位也可以思考一下,為什麼絕對中心的SPT才是MDST,而一般中心的SPT並不見得是MDST。

G:
    0
   /|\
  / | 1
 /  |  \
4---3---2---5

MDST:
    0
    |
    | 1
    |  \
4---3---2---5

SPT, source is 0:
    0
   /|\
  / | 1
 /  |  \
4   3   2---5

SPT, source is 1:
    0
   /|\
  / | 1
 /  |  \
4   3   2---5

SPT, source is 2:
    0
     \
      1
       \
4---3---2---5

SPT, source is 3:
    0
    |\
    | 1
    |
4---3---2---5

SPT, source is 4:
    0
   / \
  /   1
 /
4---3---2---5

SPT, source is 5:
    0
     \
      1
       \
4---3---2---5

可以看到MDST的直徑長度是3,而SPT的直徑長度都是4和5。
也就是說,一般中心的SPT不一定就是MDST。

UVa 10805 Timus 1569 Sphere PT07C

Minimum Diameter Minimum Cost Spanning Tree

最小直徑最小成本生成樹。從所有最小生成樹當中,找到直徑最小者,是NP-complete問題。

至於從所有最小直徑生成樹中,找到權重最小者,我尚未找到相關文獻。

其他Spanning Tree

經典生成樹問題

Minimum (Cost) Spanning Tree [P]
權重最小的生成樹。

Minimum Bottleneck Spanning Tree [P]
權重最大的邊,使其權重最小的生成樹。
【註:此處Bottleneck定義為權重最大的邊。】

Minimum Diameter Spanning Tree [P]
直徑最短的生成樹。

Maximum Leaf Spanning Tree [NP-hard]
葉子最多的生成樹。

Minimum Degree Spanning Tree [NP-hard]
度數最多的點,使其度數最少的生成樹。

Minimum Routing (Cost) Spanning Tree [NP-hard]
所有兩點之間路徑,權重總和最小的生成樹。

Minimum Ratio Spanning Tree [NP-hard]
有兩種權重,分開計算。兩種權重比值最小的生成樹。

Minimum Edge-disjoint Spanning Trees [P]
邊不重疊,權重最小的k棵生成樹們。

Minimum Congestion Spanning Trees [P]
重疊的邊將額外增加權重,權重最小的k棵生成樹們。
Minimum k-Spanning Tree [NP-hard]
權重最小的生成子樹,剛好是k個點。

Steiner Tree [NP-hard]
權重最小的生成子樹,包含給定的k個點。
DFS Tree [P]
使用 Depth-first Search 找到的無向(有向)生成樹。

BFS Tree [P]
使用 Breadth-first Search 找到的無向(有向)生成樹。

Shortest Path Tree [P]
樹根到樹上各點都是最短路徑的無向(有向)生成樹。

Minimum Cut Tree [P]
任意兩點間路徑的瓶頸,形成兩點間最小割的無向生成樹。

Dominator Tree [P]
樹根到樹上各點的支配點,形成的有向生成樹。

Minimum Ratio Spanning Tree

最小(大)比率生成樹。NP-complete。

演算法類似於最小比率環,時間複雜度等同於求O(logR)次最小生成樹。

一、設定一比率r後,把原圖轉換成新圖,除法轉換成差值。
二、新圖上一棵權重為零的生成樹,就是原圖上一棵比率為r的生成樹。
  新圖上一只零環,就是原圖上一只比率為r的環。
三、當新圖上有一棵負權重的生成樹,表示這棵樹比率比r小:
 甲、比率設更小,設成r'之後,
   這棵樹就可以變成零權重生成樹,就是原圖上比率為r'的生成樹。
   找到了一棵比率更小的生成樹。
 乙、至於要找一棵負權重的生成樹,直接找最小生成樹就行了。

ICPC 3465 4326

Minimum Steiner Tree

一張無向圖,給定k個點,用圖上的邊連接這k個點,使得k個點相互連通,並且盡量減少這些邊的權重總和。為了減少權重,這些邊不需形成環,只需形成樹,稱作Steiner Tree,Steiner是人名。

注意到Steiner Tree並不是生成樹,只不過是概念近似於最小生成樹。

求出權重最小的Steiner Tree是NP-complete問題。

特殊情況:
當k = 1時,Minimum Steiner Tree就是一個點。
當k = 2時,Minimum Steiner Tree就是此兩點間最短路徑。
當k = V時,Minimum Steiner Tree就是最小生成樹。

http://www.prefield.com/algorithm/dp/steiner_tree.html

ICPC 3271

Degree-Constrained Minimum Spanning Tree

每個點限制連接邊數上限的最小生成樹。NP-complete。

當上限規定為兩條邊,就是Hamilton Path。

UVa 10605

Spanning Forest Decomposition

Spanning Forest Decomposition,無權重的圖。

一張圖分解成數叢生成森林,採用的分解方式是:屢次從剩下的圖分離出生成森林。分解結果可能有許多種。

無權重圖的情況下,直覺的方式是尋找O(V)次生成森林,尋找一叢生成森林需時O(V+E),總時間複雜度為O(VE)。較佳的方式是Maximum Cardinality Search,總時間複雜度為O(V+E)。

可以用來快速找到k-connected subgraph。

Spanning Forest Decomposition,有權重的圖。

有兩種分解方式,一種是讓第k叢生成森林的權重盡量小,另一種是讓前k叢生成森林的權重總和盡量小。

A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees. James Roskind and Robert E. Tarjan. Mathematics of Operations Research, 1985, 10(4), 701-708.

UVa 10807

Enumerate Spanning Trees

時間複雜度O(V+E+N),其中N是生成樹數目。

http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-50.pdf

Count Spanning Trees

Matrix Tree Theorem

Laplacian matrix的任意一個cofactor,其絕對值大小,就是各種生成樹的總數目。

cofactor就是隨便砍掉某一行與某一列,剩下來的矩陣,然後加上係數+1或-1。

http://en.wikipedia.org/wiki/Kirchhoff's_theorem

證明會用到一個性質:
給定一個無向圖,兩點之間最多只有一邊。
如果原圖是樹,Laplacian matrix 隨便砍掉一橫行之後,絕對值都是1。
如果原圖不連通,Laplacian matrix 隨便砍掉一橫行之後,絕對值都是0。
-
Laplacian matrix 可以寫成 FFᵀ 的形式,F是incidence matrix。
把F的隨便一個橫行給砍了,變成E,
然後用 Bxxx-Cxxx 展開 EEᵀ,
展開之後會變成兩兩(V-1)x(V-1)方陣相乘,然後相加。
所有E取V-1的各種可能都會被展開出來。(還沒証,不要問,很可怕)
每一種可能就代表V-1條邊,有可能成為生成樹,有可能不行。
-
兩個(V-1)x(V-1)方陣,乘出來,剛好就是V個點的 Laplacian matrix 砍掉某一橫行。
如果是生成樹的話就會是1,所以統統加一加,就是生成樹數目。

UVa 10766 Sphere MSTS