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

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

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

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

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

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

7、, Ce單點度限制生成樹求滿足單點度限制的最小生成樹即：其中某一個特定節(jié)點度數(shù)有限制例如: deg(v0) k擴展:多點度限制單點度限制生成樹先不考慮v0, 求出G - v0 的最小生成森林不同的連通塊僅能通過v0連接若塊數(shù)超過k則誤解現(xiàn)在加入 v0對于每一個連通塊, 選擇一條連向v0邊權(quán)最小的邊現(xiàn)考慮逐步增大v0的度數(shù)置換邊： 置換一次O(n)時間復(fù)雜度: O(mlogn + kn)最小直徑生成樹無權(quán)圖帶權(quán)圖求一棵生成樹, 使得其直徑最短再引入一些概念偏心距: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圖的絕對中心絕對中心： 中心未必要在原圖的點上可以在邊上到最遠點距離最小最小直徑生成樹就是絕對中心的最短路樹偏心距最小 直徑最小無權(quán)圖：枚舉絕對中心帶權(quán)圖的MDST求絕對中心帶區(qū)間的最短路算法最小直徑最小生成樹雙連通圖的固定中心生成樹給定一個雙連通圖和一個頂點s，求一棵以s為中心的生成樹。雙連通:連通圖, 且圖中沒有割點即, 刪除任意單個節(jié)點都不會導(dǎo)致圖不連通雙連通圖的固定中心生成樹算法：設(shè)t為s的任意一個相鄰頂點。找到一組標(biāo)號D

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

10、開始DFS，求出每個節(jié)點v的Low(v)。COUNT=1。將t和s依次壓入棧S，并將s,t和(s,t)標(biāo)記為已訪問。取出棧頂元素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上所有節(jié)點和邊標(biāo)記為已訪問。Most Vital Edge on Spanning Tree刪除一條邊可能導(dǎo)致圖的最小生成樹變大Most Vital Edge:刪掉哪條邊使得圖的最小生成樹變大得最多基于可并堆合并黑板Most Vital Edge on Spanning Tree生成樹的計數(shù)給定無權(quán)圖，求生成樹的個數(shù)擴展: 給定帶權(quán)圖，求最小生成樹的個數(shù)生成樹計數(shù)無權(quán)圖的生成樹計數(shù)行列式：列出圖G的Kirchhoff矩陣C：若i=j，則Cij=-degree(vi)；若ij，則Cij為vi與vj之間的邊的個數(shù)。然后去掉C的任意第r行第r列得到的新矩陣Cr，Cr的行列式的絕對值即為生成樹的個數(shù)。生成樹計數(shù)帶權(quán)圖的最小生成樹計數(shù)性質(zhì)：在求最小生成樹的過程中，若我們只用邊權(quán)小于x的邊，我們得到的是森林。由于選擇的邊不同，會得到不同的森林，但是森林的連