【學習筆記】Kruskal 重構樹

這篇文章起源於學校裡讓寫的研究性學習，本文嚴禁轉載，請認準出處 https://www.cnblogs.com/linyihdfj/p/17067905.html，也請不要以本文作為研究性學習抄襲的證據，因為都是我寫的

1 相關概念

1.1 最小生成樹

設存在圖 \(G = (V,E)\)，每條邊有邊權 \(w(u,v)\)，從中選出邊集 \(T\) 使得 \(T\) 是連線所有點的無環邊集，那麼 \(T\) 就是圖 \(G\) 的一個生成樹。
定義的權值為 \(w(T) = \sum_{(u,v) \in T} w(u,v)\)，我們稱使得 \(w(T)\) 最小的生成樹為圖的最小生成樹

1.2 Kruskal 演演算法

常用 Kruskal 演演算法對最小生成樹進行求解，演演算法的具體流程如下：
①從待選擇的邊集中選擇邊權值最小的邊
②若這條邊連線的兩點未聯通，則將這條邊加入最小生成樹的邊集中
③重複上述過程，直到所有邊都被存取

1.3 瓶頸生成樹

定義無向圖 \(G = (V,E)\)，若存在一棵生成樹 \(T\) 使得對於任意兩點其在圖上的所有路徑的邊權的最大值的最小值都在其在生成樹 \(T\) 上的唯一路徑上，那麼稱這棵生成樹 \(T\) 為圖 \(G\) 的瓶頸生成樹

• 定理：最小生成樹一定是瓶頸生成樹
  證明：若最小生成樹不是瓶頸生成樹則一定存在兩個點使得這兩個點在最小生成樹上的路徑上不包含其路徑邊權的最大值的最小值，也就是一定包含比最小值更大的值，那麼將這個更大的值對應的邊從最小生成樹中刪去並加入最小值，最小生成樹的權值和一定變小，與原有假設其為最小生成樹矛盾。

2 Kruskal 重構樹

2.1 定義

在 Kruskal 演演算法的過程中，每次選擇一條邊，新建節點，將這條邊連線的兩個點對應的子樹分別置為新建節點的左右兒子，將新建節點的權值設為該邊的邊權，最後會形成一個樹的結構，這棵樹就是 Kruskal 重構樹。
下圖為原樹與其 Kruskal 重構樹的一個例子：

2.2 性質

• 性質一：Kruskal 重構樹一定滿足二元堆積性質
  證明：每次新建節點時合併兩個點，並將它們設為新建節點的左右兒子，所以對於每一個非葉子節點其有且只有兩個兒子也就是滿足是一棵二元樹；在合併邊時，將邊按照從小到大的順序排列，因為對於某一個節點來說，其父親節點合併的時間一定晚於當前節點，也就是對應的邊權一定大於當前節點，即滿足堆性質。

• 性質二：Kruskal 重構樹中葉子節點代表原樹的節點，非葉子節點代表原樹的邊
  證明：對於原樹的任意一個節點，都不會被作為根合併任意一個節點，所以 Kruskal 重構樹葉子節點一定是原樹的節點，原樹的節點也一定是 Kruskal 重構樹中的葉子節點；在合併一條的邊時候，新建節點併合並這條邊連線的兩個點，所以所有的新建節點都是非葉子節點，所有的非葉子節點也都是新建節點，也就是說 Kruskal 重構樹中非葉子節點代表原樹 的邊。

• 性質三：原圖中任意兩點之間的所有路徑中的邊權的最大值的最小值對應 Kruskal 重構樹上兩點的最近公共祖先。
  證明：Kruskal 重構樹上的非葉子節點對應的邊可以對應原圖的一棵最小生成樹，也就是一定是一棵瓶頸生成樹，而作為邊權的最大值的最小值，因為將邊按邊權從小到大選擇，所以這條邊一定最後被選擇，也就是加入這條邊後兩個點聯通，所以在 Kruskal 重構樹中，這條邊對應的點就是這兩個點的最近公共祖先。

• 性質四：對於原圖上的任意點，其只經過邊權小於等於 \(x\) 的邊，能到達的所有點一定對應 Kruskal 重構樹上的一棵子樹
  證明：對於任意兩點之間的路徑的邊權的最大值的最小值等於 Kruskal 重構樹上它們兩者的最近公共祖先的點權，所以我們可以找到該點的一個父親，使得這個父親的點權小於等於 \(x\)，那麼對於這個父親的子樹的所有節點與原節點的最近公共祖先只可能是這個父親或者子樹內的點，因為 Kruskal 重構樹滿足二元堆積性質，所以無論是哪個點都必然滿足其點權小於等於 \(x\)，也就是經過的邊權一定全部小於等於 \(x\)

2.3應用

在實際問題當中對於 Kruskal 重構樹的應用多為性質三的應用，因為可以使用性質三將原本的路徑查詢轉化為了點查詢，就可以以比較簡單地方式解決問題。以下面這道題為例考慮實際問題中是如何使用 Kruskal 重構樹的。

題目大意：
給出個 \(n\) 點 \(m\) 條邊的不帶權聯通無向圖，\(q\) 次詢問至少要加完編號前多少的邊，才可以使得編號在 \([l,r]\) 中的所有點兩兩聯通。
題目分析：
下文定義聯通時間為題目中詢問的答案。
可以發現從前到後每次加入一條邊就是類似合併兩個點，與 Kruskal 演演算法有相似之處，所以可以聯想到 Kruskal 重構樹。
那麼如果將邊的編號作為邊權，對處理後的圖建 Kruskal 重構樹的話，對於任意兩個點的最近公共祖先其實就是代表這兩個點的聯通時間，所以我們就可以對於一個區間詢問拆成\((l,l+1),(l+1,l+2)\cdots (r-1,r)\)這些點對聯通的時間的最大值，至此問題得到了解決。

參考資料：

[1]吳景嶽，最小生成樹演演算法及其應用
[2]汪汀，最小生成樹問題的拓展
[3]百度百科，瓶頸生成樹
[4]OIer某羅，Kruskal重構樹