【学习笔记】Kruskal 重构树 - linyihdfj

这篇文章起源于学校里让写的研究性学习，本文严禁转载，请认准出处 https://www.cnblogs.com/linyihdfj/p/17067905.html，也请不要以本文作为研究性学习抄袭的证据，因为都是我写的

1 相关概念

1.1 最小生成树

设存在图 G=(V,E)G=(V,E)，每条边有边权 w(u,v)w(u,v)，从中选出边集 TT 使得 TT 是连接所有点的无环边集，那么 TT 就是图 GG 的一个生成树。
定义的权值为 w(T)=∑(u,v)∈Tw(u,v)w(T)=∑(u,v)∈Tw(u,v)，我们称使得 w(T)w(T) 最小的生成树为图的最小生成树

1.2 Kruskal 算法

常用 Kruskal 算法对最小生成树进行求解，算法的具体流程如下：
①从待选择的边集中选择边权值最小的边
②若这条边连接的两点未联通，则将这条边加入最小生成树的边集中
③重复上述过程，直到所有边都被访问

1.3 瓶颈生成树

定义无向图 G=(V,E)G=(V,E)，若存在一棵生成树 TT 使得对于任意两点其在图上的所有路径的边权的最大值的最小值都在其在生成树 TT 上的唯一路径上，那么称这棵生成树 TT 为图 GG 的瓶颈生成树

• 定理：最小生成树一定是瓶颈生成树
  证明：若最小生成树不是瓶颈生成树则一定存在两个点使得这两个点在最小生成树上的路径上不包含其路径边权的最大值的最小值，也就是一定包含比最小值更大的值，那么将这个更大的值对应的边从最小生成树中删去并加入最小值，最小生成树的权值和一定变小，与原有假设其为最小生成树矛盾。

2 Kruskal 重构树

2.1 定义

在 Kruskal 算法的过程中，每次选择一条边，新建节点，将这条边连接的两个点对应的子树分别置为新建节点的左右儿子，将新建节点的权值设为该边的边权，最后会形成一个树的结构，这棵树就是 Kruskal 重构树。
下图为原树与其 Kruskal 重构树的一个例子：

2.2 性质

• 性质一：Kruskal 重构树一定满足二叉堆性质
  证明：每次新建节点时合并两个点，并将它们设为新建节点的左右儿子，所以对于每一个非叶子节点其有且只有两个儿子也就是满足是一棵二叉树；在合并边时，将边按照从小到大的顺序排列，因为对于某一个节点来说，其父亲节点合并的时间一定晚于当前节点，也就是对应的边权一定大于当前节点，即满足堆性质。

• 性质二：Kruskal 重构树中叶子节点代表原树的节点，非叶子节点代表原树的边
  证明：对于原树的任意一个节点，都不会被作为根合并任意一个节点，所以 Kruskal 重构树叶子节点一定是原树的节点，原树的节点也一定是 Kruskal 重构树中的叶子节点；在合并一条的边时候，新建节点并合并这条边连接的两个点，所以所有的新建节点都是非叶子节点，所有的非叶子节点也都是新建节点，也就是说 Kruskal 重构树中非叶子节点代表原树 的边。

• 性质三：原图中任意两点之间的所有路径中的边权的最大值的最小值对应 Kruskal 重构树上两点的最近公共祖先。
  证明：Kruskal 重构树上的非叶子节点对应的边可以对应原图的一棵最小生成树，也就是一定是一棵瓶颈生成树，而作为边权的最大值的最小值，因为将边按边权从小到大选择，所以这条边一定最后被选择，也就是加入这条边后两个点联通，所以在 Kruskal 重构树中，这条边对应的点就是这两个点的最近公共祖先。

• 性质四：对于原图上的任意点，其只经过边权小于等于 xx 的边，能到达的所有点一定对应 Kruskal 重构树上的一棵子树
  证明：对于任意两点之间的路径的边权的最大值的最小值等于 Kruskal 重构树上它们两者的最近公共祖先的点权，所以我们可以找到该点的一个父亲，使得这个父亲的点权小于等于 xx，那么对于这个父亲的子树的所有节点与原节点的最近公共祖先只可能是这个父亲或者子树内的点，因为 Kruskal 重构树满足二叉堆性质，所以无论是哪个点都必然满足其点权小于等于 xx，也就是经过的边权一定全部小于等于 xx

2.3应用

在实际问题当中对于 Kruskal 重构树的应用多为性质三的应用，因为可以使用性质三将原本的路径查询转化为了点查询，就可以以比较简单地方式解决问题。以下面这道题为例考虑实际问题中是如何使用 Kruskal 重构树的。

题目大意：
给出个 nn 点 mm 条边的不带权联通无向图，qq 次询问至少要加完编号前多少的边，才可以使得编号在 [l,r][l,r] 中的所有点两两联通。
题目分析：
下文定义联通时间为题目中询问的答案。
可以发现从前到后每次加入一条边就是类似合并两个点，与 Kruskal 算法有相似之处，所以可以联想到 Kruskal 重构树。
那么如果将边的编号作为边权，对处理后的图建 Kruskal 重构树的话，对于任意两个点的最近公共祖先其实就是代表这两个点的联通时间，所以我们就可以对于一个区间询问拆成(l,l+1),(l+1,l+2)⋯(r−1,r)(l,l+1),(l+1,l+2)⋯(r−1,r)这些点对联通的时间的最大值，至此问题得到了解决。

参考资料：

[1]吴景岳，最小生成树算法及其应用
[2]汪汀，最小生成树问题的拓展
[3]百度百科，瓶颈生成树
[4]OIer某罗，Kruskal重构树