期望线性复杂度最小生成树算法学习笔记

huangjiarui · 2023-01-22 18:33:03 · 个人记录

鉴于网上关于此算法的信息较少，故作此文。

本文大部分内容为原论文的摘要翻译。

1.预备工作

本算法事实上可以解决一个不一定联通的图上的最小生成森林（联通性与原图相同）（以下为简便均称作最小生成森林）。

为了方便，假定图中没有孤立点，边权两两不等，于是最小生成森林唯一。

以下是两个喜闻乐见的 Lemma。

Lemma 1.1(Cycle Property) 对于图中的一个环 C，C 中边权最大的边不在最小生成森林中。

Lemma 1.2(Cut Property) 对于点集的一个非空真子集 X，恰有一个端点属于 X 的边权最小的边属于最小生成森林。

记 w(x,y) 为边 (x,y) 的边权。对于图 G 的一个生成森林 F，若 x,y 在 F 联通，记 F(x,y) 为 x 和 y 在 F 中联通的路径，并记 w_F(x,y) 为 F(x,y) 中边权边权。若 x,y 在 F 中不连通则定义 w_F(x,y)=+\infty 。

我们称一条边 (x,y) 是 F-heavy 当且仅当 w(x,y)>w_F(x,y)，否则称其为 F-light。则：（1）F 中的任意边都是 F-light。（2）由 Cycle Property 知，对于任意的生成森林 F，没有 F-heavy 的边会在原图 G 的最小生成森林中。

对于原图 G 的一个给定的生成森林 F，可以在线性的时间求出 F_heavy 的边。有两种做法：第一种在原论文的参考文献中出现，是一种离线的做法；另一种出现于参考文献二的参考，通过实现O(n)-O(1)的在线链上最大值查询来得到。大致做法类似 Four Russians，先对树分块，然后块内和块间分别操作。

以下给出一个重要的 Lemma:

Lemma 1.3 对图 G 中每一条边独立地以 p 的概率选择，将选中的边和 G 的点集组成 G 的生成子图 H，记 H 为 G 的最小生成森林。则 G 中 F-light 的边的期望数量不多于 \frac np。

Proof 以如下的方式考虑 H 和 F 的产生：

初始置 F 的边集为空。按边权从小到大的顺序依次考虑 G 中的每一条边。假设当前考虑到边 e 若 e 是 F_light，那么以 p 的概率选择这条边加进 F。

那么：（1）若一条边在考虑时是 F-heavy，那么最终还是 F-heavy，因为 F 的边集只加不减。（2）若一条边在考虑时是 F-light，那么最终还是 F-light，因为在这条边后考虑的边的边权均大于当前边。于是最后的 F-light 的边即考虑时为 F-light 的边。

考虑的 F-light 边数量满足负二项分布，又因为最后选中在 F 中的边数不大于 n-1，则考虑的 F-light 边的期望数量，即 G 中 F-light 边期望数量不大于 \frac {n-1}p<\frac np❑

2.算法

在描述算法之前，先介绍 Borůvka 算法：

初始置每一个点为一个联通块。
对于每一个连通块，选择与之相连的边中边权最小的边。这部分的时间是 O(m)。
将选择的边两端的联通块合并为一个并删除两连通块间的其他边。因为每一条边至多被选择两次，故至少进行 \frac n2 次合并(n指当时联通块数量)，于是连通块数量至少减少一半。
若还有边的两端不属于同一个联通块，回到2。

易知这个求最小生成森林的算法的最坏复杂度为 \Theta(\min\{m\log n,n^2\})，最好时间复杂度为 \Theta(m)，平均时间复杂度本人不会（网上一些博客不附证明地说平均时间复杂度为 \Theta(m)，但这感觉很假）。特别的，在图为平面图时，该算法可以做到 \Theta(m)（这点本人也不会证，不确定是不是真的）。

我们称进行一次第二步和第三步为一次 Borůvka step，则一次Borůvka step的时间为 \Theta(m)。以下来叙述本算法的过程：

若边集为空，则直接返回。
运行两遍 Borůvka step。这一步会使点数减少至原来的 \frac14。
在收缩后的图 G 对每一条边独立地以 \frac12 的概率选取组成 G 的生成子图 H。调用该算法求出 H 的最小生成森林 F，找出所有 F-heavy 边并删除。
在剩余的图 G 中调用该算法求出最小生成森林 F。

正确性由归纳法知。通过 Cut Property，第二步中选的边一定在最小生成森林中。通过 Cycle Property，第三步删除的边一定不再最小生成森林中。

3.分析

我们将首先分析该算法的最坏情况，然后

先考虑单次该算法的调用。除了递归子问题外在第1-4步上的时间是关于边数线性的（其中第三步找出所有 H-heavy 边见前文），于是我们的目的是分析所有调用涉及到的边的总数。因为没有孤立点，所以 m\ge n/2。

每一次调用至多会产生两个子问题。考虑所有递归子问题形成的二叉树（后文记为子问题树）。对于一个特定的图的边集非空的子问题，我们称在第三步的第一个递归子问题为其左儿子，第四步的第二个递归子问题为其右儿子。在深度为 d，子问题树的节点数至多为 2^d ，且每个节点处理一个点数至多为 \lfloor\frac n{4^d}\rfloor 的图。因此，子问题树的深度至多为 \lceil\log_4n\rceil+1，在原问题和所有子问题中涉及到的节点总数少于 \sum_{k=0}^{+\infty}\frac n{4^d}2^d=2n

Theory 3.1 该算法的最坏时间复杂度为 \Theta(\min\{n^2,m\log n\})，不劣于 Borůvka 算法。

Proof 我们从两个不同的角度来说明这一点：

(1)深度为 d 的节点处理的图至多有 \frac{\lfloor\frac n{4^d}\rfloor(\lfloor\frac n{4^d}\rfloor-1)}{2} 条边，于是所有子问题的边数和小于 \sum_{k=0}^{+\infty}\frac12(\frac n{4^d})^22^d=O(n^2)，即该算法的最坏复杂度为 O(n^2)。

(2)考虑一个节点的图中的所有边。这些边可以分成三类：1.在第一步被删除的，不会在子节点的图中出现。2.未在第一步被删除，不在随机选边后生成子图 H 的最小生成森林 F 中的，只会在左子节点或右子节点中出现。3.在随机选边后生成子图 H 的最小生成森林 F 中的，会同时在左右子节点中出现。由于第三类边的数量严格不大于第一类边的数量，所以左右子节点中的边的总数严格不大于父节点的边的数量。故每一层的边的总数不大于初始图的边数 m，所以总边数不大于 O(m\log n)，即该算法最坏复杂度为 O(m\log n)

以上说明了该算法的最坏时间复杂度为 O(\min\{n^2,m\log n\})。同时这个上界可以被极端数据（和极端差的运气）卡到（构造方法略），于是最坏时间复杂度为 \Theta(\min\{n^2,m\log n\})❑

Theory 3.2 该算法的期望时间复杂度为 \Theta(m)

Proof 我们将子问题树分割成若干 left path。其中 left path 定义为从根节点或一个节点的右儿子开始，一直沿着左儿子向下走直到叶子节点的路径。我们设某一个特定节点的图的边数为 X，其左子节点的图的边数为 Y。因为节点中的一部分边在第一步被移去，另一部分以 \frac12 的概率进入左子节点，故 E(Y)\le \frac12E(X)。从而我们得到，对于一个 left path，若其顶端的节点的边数为 k ，则该 left path 的所有节点的边数和不大于 \sum_{t=0}^{+\infty}\frac k{2^t}=2k。

于是我们只要考虑根节点和所有右子节点的边数和的期望值。根据 Lemma 2.1，右子节点的边数的期望值不大于点数的2倍。故所有右子节点的边数和的期望值不大于 \sum_{k=1}^{+\infty}2*2^{k-1}\frac n{4^k}=n。于是所有子问题的边数和的期望值不大于 2(m+n)。结合前面的分析，因此该算法的期望时间复杂度为 \Theta(m)。❑

接下来，我们先补一些概率论的知识，然后默认我们都会切诺夫界。

Theory 3.3 该算法以 \Theta(m) 的时间运行的概率为 1-exp(-\Omega(m))。

Proof 我们先考虑所有右子节点的总边数。每一条右子节点的边，一一对应一条对应父节点的 F-light 边，一一对应一次 Lemma 1.3 中对 F-light 边的概率为 \frac12 的选择。而每一次选择成功，一一对应其父节点的左子节点的最小生成森林的一条边。而所有左子节点的最小生成森林的边数和小于所有左子节点的点数和。根据前文的分析，所有左子节点的点数和不大于 \frac n2。于是选择成功的次数不大于 \frac 12。因为总边数超过 3m 的概率不大于抛 3m 次硬币而正面向上次数不超过 \frac n2 的概率，而因为 m\ge \frac n2，后者的概率根据切诺夫界我们知道为 exp(-\Omega(m))。因此右子节点的总边数为 O(m) 的概率为 1-exp(-\Omega(m))

其次我们考虑所有左子节点的总边数。一个左子节点的边来源于其父节点的未被第一步删去的边的一次概率为 \frac12 的选择。换一个角度考虑，就想 Theory 3.2 的证明中那样，我们考虑每一条 left path。一条 left path 的顶端的节点的边通过抛一次硬币决定是否进入左子节点（比如正面向上表示进入），如果进入那么就继续抛硬币，直到不进入左子节点或者没有左子节点。所有左子节点的边都一一对应一次抛硬币正面向上。而所有正面向上的次数不超过所有右子节点和根节点的总边数，设其为 m_1，根据上文，m_1=O(m) 的概率为 1-exp(-\Omega(m))。而所有左子节点的总边数，即总抛掷次数不超过 3m_1 的概率，小于抛掷 3m_1 次硬币而正面向上次数不超过 m_1 的概率，而后者的概率根据切诺夫界可知为 1-exp(-\Omega(m))。

综合以上分析，所有节点的总边数为 O(m) 的概率为 (1-exp(-\Omega(m)))^2=1-exp(-\Omega(m))。综合前文分析即可得到该算法以 \Theta(m) 的时间运行的概率为 1-exp(-\Omega(m))。❑

Refrence

[1]Karger,Klein and Tarjan,1995.A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees

[2]博客magic！期望线性 MST！by Ntokisq