Spanning Tree

Spanning Tree

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

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

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

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

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

Minimum 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 k-Spanning Tree

Minimum k-Spanning Tree [NP-hard]
權重最小的生成子樹,剛好是k個點。

Steiner Tree [NP-hard]
權重最小的生成子樹,包含給定的k個點。

Minimum Spanning Tree Decomposition

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

Minimum Congestion Spanning Trees [P]
重疊的邊將額外增加權重,權重最小的k棵生成樹們。

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

Minimum Diameter Minimum Cost Spanning Tree

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

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

Minimum Ratio Spanning Tree

Minimum Ratio Spanning Tree

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

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

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

ICPC 3465 4326

Minimum Steiner Tree

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。

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

UVa 10605

Minimum Spanning Tree Decomposition

Minimum Spanning Tree Decomposition,邊無權重。

一張圖分解成數棵生成樹(生成森林)。分解方式:屢次從剩下的圖分離出生成森林。可能有許多種。

Arboricity:最少需要多少叢生成森林。

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

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

Minimum Spanning Tree 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

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

Laplacian matrix的任意一個cofactor,其行列式大小,就是各種生成樹的總數目。

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

請見本站文件「Incidence Matrix」。

UVa 10766