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棵生成樹們。

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α(V))。

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

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

UVa 10600 10462 ICPC 5713

minimum diameter spanning tree

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

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

證明（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)   切成兩條，分別ＰＫ。

  d(i, j)
≤ d(c, i) + d(c, j)   切成兩條，分別ＰＫ。
≤ 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

最小（大）比率生成樹。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就是最小生成樹。

ICPC 3271

degree-constrained minimum spanning tree

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

當上限規定為兩條邊，稱作spanning path，就是Hamilton path。

UVa 10605

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

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

matrix tree theorem

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

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

請見本站文件「incidence matrix」。

int adj[9][9]; // adjacency matrix int matrix[9][9]; // Laplacian matrix int count_spanning_tree() { memset(matrix, 0, sizeof(matrix)); for (int i=0; i<9; ++i) for (int j=0; j<9; ++j) if (i != j && adj[i][j]) { matrix[i][i]++; matrix[i][j] = -1; } // determinant return det(matrix, 9-1); }

UVa 10766