近似最短路径 (7)

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) 倍了。很赞的分析吧！