11.6a 把樹合併起來

讓我們簡單描述一下把樹合併起來的過程，補上昨天 Peleg’s Distance Labelling 演算法的最後一塊拼圖。

試想一下，現在有 n 棵樹，這些樹都是以某個點往外走 L 步做出來的 BFS 樹，彼此可能有些重疊。如果我們隨意挑選一棵樹 T，並且將所有與之有交集的樹 (存在某個節點出現在T與該樹上) 全部都黏起來，得到比較大的樹 T’，這棵樹 T’ 的直徑，最多也只有 6L 而已。

重複上述步驟，將所有與 T’ 交集的 BFS 樹全部黏起來，得到 T’’，這棵 T’’ 的直徑，最多也只有 10L。換句話說，若我們重複了 k-1 次步驟，那麼樹的直徑最多會變成 (2k-1) * 2L。

氣球和氣球的外圍

假設 U 是目前我們關心的所有 BFS 樹形成的集合。
挑選一棵樹 T 以後，重複往外擴的步驟，得到一系列往外擴張的樹 T1, T2, …, Tk, ...。
擴張次數越多，直徑就會變得越大，距離標籤得到的誤差也就會越大。但是擴張次數越少，最後剩下的樹可能就會很多，也就需要更長的距離標籤才能記錄下所有的樹。因此，我們需要找出一個平衡。

我們在意的是每次擴張，可以合併多少棵樹。如果每次擴張，都能讓融合的樹的總量變成至少 R 倍以上，那麼我們就 "允許" 這次擴張，否則我們就停下來。換句話說，當我們停下來的時候 Tk 的直徑不超過 (2k-1) * 2L，如果這棵樹 Tk 融合了 X 棵樹，那麼與 Tk 有交集的樹(包含那X棵)的總數不超過 R * X。

極大獨立集的想法

Peleg 注意到，如果我們使用以下的貪婪演算法：每次挑選 U 中的任何一棵樹 T、不斷擴張直到有交集的樹不夠而停下來為止，那麼我們不妨將融合成 Tk 的 X 棵樹記錄下來、但是從母集合 U 移除所有與 Tk 有交集的樹。接著挑選新的樹、重複擴張的步驟直到 U 為空為止。

這麼一輪做完以後，那些被丟掉、但是又沒有被融合的樹們，我們將之重新蒐集回來，定義為新的 U’。重複整個貪婪演算法，直到所有的樹都被融合為止。有趣的是，所有的融合出來的樹就像是獨立集一樣，因為每次都把有交集的通通丟掉了，所以任何一個點只會出現在至多一棵融合完的樹上。

每次從 U 做完一次貪婪演算法，我們不難能證明 U’ 的大小不超過 (1-1/R) U。換句話說，貪婪演算法至多只需要重複 log |U| / log (1+1/(R-1)) ≈ O(R log |U|) 次，就會結束。也就是說，如果一開始 |U|=n、我們選取 R=2，那麼只需要 O(log n) 次貪婪演算法便能生出許多融合的樹，使得每一個點出現在至多 O(log n) 棵樹上。

這些融合的樹直徑如何？每一次至少要擴張 R=2 倍，也就是說這個擴張至多只會進行 log |U| / log R 次就會結束。因此樹的直徑不超過 (log |U| / log R - 1) * 2L，其誤差也就不超過 O(log |U| / log R) 倍了。很讚的分析吧！