最小生成树相关的种种

最小生成树有非常多的性质，这里通过一次作业题扩展一番。

最小生成树的重要性质 1

图上每个点邻接的边里权值最小的边肯定在最小生成树上。这个性质可以用来解决 ADS 中的一道题目。它的证明可以用 Kruskal 的流程来理解。我们考虑 Kruskal 加边的流程，一个点肯定会被它邻接的边中权值最小的那个给加到当前的图上。

更新最小生成树

最小生成树的更新是一个有趣的问题。给定一个图和这个图的某个生成树，现在新加一个点和这个点到其他点之间的新边，如何快速生成新的最小生成树呢？
这里我们首先证明一个引理：新的图的最小生成树中，一定存在某棵树只包含原最小生成树的边和新边。这个证明也可以继续用 Kruskal 的流程来理解。我们考虑到在 Kruskal 的过程中，有了新边的存在只会让相同阶段的连通程度更强。稍微严谨地说就是：对比新老 Kruskal 的流程，枚举到同一条边的时候，可以证明新 Kruskal 的连通程度更高。这里连通程度高是指：老图中此刻任意连通的两点在新图里也是连通的。更严格的证明可以通过归纳法说明。在此不展开。
于是乎我们此刻其实最多只需要考虑条边，即原树里的边和新边（新边最多只有条）。所以现在问题就变成了求这个非常特殊的图（有个点，条边）的最小生成树。如果我们继续用 Kruskal 就可以得到一个 复杂度的做法。这不算非常好，因为我们在边非常少的时候可以用一个很罕见的最小生成树算法： Cheriton-Tarjan 算法，它可以做到 的复杂度。但是这里还有一个非常好的做法，我找到了一篇论文其中包含了这个做法，非常简洁。
使用的方法和 Cheriton-Tarjan 算法很接近，就是每次利用 重要性质1 得到一些肯定在最小生成树里面的边。然后我们考虑一个新的图，点和原来一样，边就是这些通过 重要性质1 获得的边，那么这个图将会是一个森林。我们把森林里的每个树都缩点缩成一个点。显然每次缩点之后整个图的点数至少减少到一半（因为每个点都会属于森林中的某个树，而一个树至少包含两个点）。我们发现整个缩点的过程其实是就可以搞定的，其实严格的来说是和边数线性，但是这里边数和点数是同阶的。于是我们可以得到一个递推关系：

论文到这里没有更具体的介绍，但是其实这里有一个需要证明的东西，而且并不是非常显然。就是我们如何才能保证缩点的过程中边数可以一直保证和点数是同阶的呢？如果我们就直接缩点，那么其实边减少的速度是跟不上点减少的速度的。比如在第一次缩点的过程中我们减少了个点，我们其实也就减少了条边而已。如果要保证问题的规模也变成原来的一半我们其实要保证边也要变成原来的一半，也就是说现在最多只能有条边。这个证明在论文中没有提及，但是确实可以证明。
我们需要用到这个图的特殊性质：条边中有条是原来的树里的，有条边是新边。新边的特殊性质是，它们都是从新点一个点连出来的。此时我们考虑缩点之后的图，我们继续把图中的边分成两类：第一类是原来的生成树里的边；第二类是新边。我们把缩点之后的点也分成两类，第一类是包含了新点的那个点，记为（实际上只有一个点属于第一类），第二类是不包含新点的点。
我们接下来考虑第二类点之间最多有多少条边。显然，第二类点之间点边只包括第一类边，因为新边都是从连出来的。而且显然第二类点内部不可能存在环，因为如果存在环的话，说明缩点之前就有环，但是这是不可能的，因为缩点之前这些点和这些边都来自于最小生成树，树是不会有环的。所以第二类点之间的边最多只有条，因为第二类点最多只有个。然后我们考虑第一类点，也即这个点和其他点之间的边。就算缩点之后这个点和其他点之间有很多边，我们也可以通过去重的方式让它只有多只有条，因为其他点最多只有个，这个点和剩下的所有点最多每个连一条边（指去重之后）。
综上，我们很不优美的证明了：缩点后也可以把边的数量砍掉一半，这样就可以放心的使用递推式了。
Ref：
https://cs.wellesley.edu/~pmetaxas/algor.pdf
ON FINDING AND UPDATING SHORTEST PATHS AND SPANNING TREES