1、圖論專題之 生成樹清華大學 唐文斌 定義: 生成樹無向圖G=(V,E)G的一個生成樹T是G的一個子圖(樹)包含G的所有節點: V = V包含G的部分EE性質: 包含所有點, 無環生成樹: 最大的無環邊集生成樹: 最小的連接所有點的邊集包含所有的橋(割邊)更多定義樹的直徑:樹的直徑定義為樹上最遠兩點的距離樹的中心在樹上選擇一個點, 離其他所有點最遠點距離最小Q: 可能有多少個?性質: 一定是直徑路徑的中心點最小生成樹(MST)最小生成樹(Minimal Spanning Tree)帶權無向圖生成樹的權定義為所有樹邊的權值之和最小樹形圖(Minimum Arborescence)帶權有向圖從某一個

2、節點出發, 可以到達所有節點生成森林原圖不連通, 每一個連通塊的生成樹集合PrimPrim算法:與Dijkstra相近選任一點為根找不在樹上且離樹最近的點加入生成樹時間復雜度O(mlogn) /優先隊列優化KruskalKruskal算法:一開始所有的點為獨立連通塊按邊權從小到大檢查每一條邊如果這條邊連接了兩個不同的連通塊(即不形成環)則將這條邊加入, 并將兩個連通塊合并使用并查集進行連通塊判定O(mlogm + m(m)Borvkas algorithmBorvkas algorithm類似Kruskal的多路增廣版一開始所有點為獨立連通塊每一次:每一個連通塊尋找一條往外連接的最小權值邊將所

3、有的這些邊都加入邊權兩兩不同時可以保證不形成環若邊權有相同: (邊權, 點標號)一起判最小合并次數: 最壞情況logn次時間復雜度: 最壞O( (m+n) logn ), 隨機圖 O(n+m)最小瓶頸生成樹(Minimum Bottleneck Spanning Tree)一個無向圖中權重最大的邊最小算法一: Kruskal的最后一條邊就是瓶頸定理: 任意 MST 一定是 MBST.Why?所以任何MST的算法均可.注意MBST并不一定是MST存在更好算法?最小瓶頸生成樹(Minimum Bottleneck Spanning Tree)線性算法類似 快排分治 查找第k小數按照邊權的集合，選擇

4、當前的瓶頸值V尋找所有權值不超過V的邊，構成子圖若子圖連通, V是答案的上界, 繼續在權值較小的部分尋找若子圖不連通, 按當前連通性進行縮點, 在權值較大部分尋找時間復雜度: T(m) = O(m) + T(m/2)時間復雜度O(n+m)擴展: 最小瓶頸路徑查詢Q個query每次查詢a, b兩個點輸出a b點之間的最小瓶頸路徑的瓶頸值算法:先求生成樹在生成樹上做RMQ維護再擴展: 若加入動態修改邊權?動態樹次小生成樹求圖的次小生成樹擴展:嚴格次小生成樹次小生成樹先求出最小生成樹MST然后枚舉不在MST上的邊(u,v)，若將(u,v)替換掉MST上節點u與節點v之間權值最大的邊，那么得到的生成樹

5、的權值為w(MST)+w(u,v)-maxw(u,v)取最小值即得到次小生成樹。用Fi,j表示由節點i向上2j條邊中邊權的最大值，那么查詢兩點之間邊權最大值可以在O(log n)時間內解決。嚴格次小生成樹同最小生成樹做法，但有略微不同。先求出最小生成樹MST然后枚舉不在MST上的邊(u,v)，若將(u,v)替換掉MST上節點u與節點v之間權值最大的邊，若這條邊的權值與w(u,v)相同，那么替換后的樹不可能成為嚴格次小生成樹。所以我們要替換節點u與節點v之間邊權嚴格次大的邊，這樣得到的樹才有可能是嚴格次小生成樹。最小比率生成樹給定無向圖G每條邊e包含權值 ae, be求生成樹最小化樹中的權值之和

6、比率即 minimize: sum(a) / sum(b)最小比率生成樹二分答案求解 判定判定是否存在比率不超過x的生成樹Sume(ae) / Sume(be) xSume(ae) x * Sume(be)Sume(ae - x * be) 0判定方法: 以ae - x * be為權值求最小生成樹時間復雜度： MST * O(logW)最小乘積生成樹給定無向圖G每條邊e包含權值 ae, be求生成樹最小化樹中的a, b權值之和乘積即 minimize: sum(a) * sum(b)試題: Balkan 2011 TimeIsMoney最小乘積生成樹最小乘積生成樹擴展:三個參數 ae, be

7、, Ce單點度限制生成樹求滿足單點度限制的最小生成樹即：其中某一個特定節點度數有限制例如: deg(v0) k擴展:多點度限制單點度限制生成樹先不考慮v0, 求出G - v0 的最小生成森林不同的連通塊僅能通過v0連接若塊數超過k則誤解現在加入 v0對于每一個連通塊, 選擇一條連向v0邊權最小的邊現考慮逐步增大v0的度數置換邊： 置換一次O(n)時間復雜度: O(mlogn + kn)最小直徑生成樹無權圖帶權圖求一棵生成樹, 使得其直徑最短再引入一些概念偏心距:Ecc(i) = maxj d(i, j)給定點的最遠距離圖的直徑:d(G) = maxi,j d(i, j)圖的半徑r(G) = m

8、ini Ecc(i)無向圖的中心圖的一般中心： 離圖中最遠點最近的點一個圖可能有多個中心枚舉中心BFS樹(最短路徑樹)? 0 /| / | 1 / | 4-3-2-5圖的絕對中心絕對中心： 中心未必要在原圖的點上可以在邊上到最遠點距離最小最小直徑生成樹就是絕對中心的最短路樹偏心距最小 直徑最小無權圖：枚舉絕對中心帶權圖的MDST求絕對中心帶區間的最短路算法最小直徑最小生成樹雙連通圖的固定中心生成樹給定一個雙連通圖和一個頂點s，求一棵以s為中心的生成樹。雙連通:連通圖, 且圖中沒有割點即, 刪除任意單個節點都不會導致圖不連通雙連通圖的固定中心生成樹算法：設t為s的任意一個相鄰頂點。找到一組標號D

9、，滿足所有頂點被不重復地標為1n，并且D(s)=1,D(t)=n。對于每個頂點v(vs,t)，都存在兩個與v相鄰的頂點u和w，滿足D(u)D(v)D(w)。雙連通圖的固定中心生成樹將無向邊(u,v)定向為從標號小的連向標號大的。求出新圖中的以s為起點的BFS樹T。將t從T中刪除作為T的根，并將所有邊(v,t)(定向后的)加入隊列Q。重復以下步驟，直到T的高度和T的高度差不超過1。取出隊首節點(v,w)。若v為T的葉節點：將其從T中刪除，加入T中作為w的子節點，并將所有邊(u,v)加入隊列Q。最后將T和T用邊(s,t)連接得到以s為中心的生成樹。雙連通圖的固定中心生成樹如何找到一組標號D。先從t

10、開始DFS，求出每個節點v的Low(v)。COUNT=1。將t和s依次壓入棧S，并將s,t和(s,t)標記為已訪問。取出棧頂元素v，若所有v的相鄰邊都被訪問，則D(v)=COUNT+。否則找到Path=vv1v2vkw，滿足v和w是已訪問的，其余點和邊均是未訪問的。然后依次將vk,vk-1,v1,v壓入棧S。雙連通圖的固定中心生成樹尋找PathCase 1: 若存在一條未訪問的返祖邊(v,w)Path=vwCase 2: 若存在一條未訪問的樹邊(v,w)令Path=vww1w2wk，其中wk=Low(w)代表點。Case 3: 若存在一條未訪問的返祖邊(w,v)令Path=vww1w2wk，其

11、中wk為一個已訪問的點。找到Path后將Path上所有節點和邊標記為已訪問。Most Vital Edge on Spanning Tree刪除一條邊可能導致圖的最小生成樹變大Most Vital Edge:刪掉哪條邊使得圖的最小生成樹變大得最多基于可并堆合并黑板Most Vital Edge on Spanning Tree生成樹的計數給定無權圖，求生成樹的個數擴展: 給定帶權圖，求最小生成樹的個數生成樹計數無權圖的生成樹計數行列式：列出圖G的Kirchhoff矩陣C：若i=j，則Cij=-degree(vi)；若ij，則Cij為vi與vj之間的邊的個數。然后去掉C的任意第r行第r列得到的新矩陣Cr，Cr的行列式的絕對值即為生成樹的個數。生成樹計數帶權圖的最小生成樹計數性質：在求最小生成樹的過程中，若我們只用邊權小于x的邊，我們得到的是森林。由于選擇的邊不同，會得到不同的森林，但是森林的連