【OI之路】04图论-7生成树

生成树(MST)相关

最小生成树

性质1:
对于点集中的一个真子集a,其补集b
连接a和b的边中,最小的为t,则必定在最小生成树中出现
证明:
设有某种最小生成树并不包含t,因为联通,总有一条边连接a和b
替换为t后显然会更优,与【最小】相矛盾

性质2:
设f(生成树)=最大边权
则最小生成树一定有最小的f
证明:
设某个非最小生成树有更小的f,则总有一条边,
和最小生成树的f的连通性贡献相同(连接a和b点集)

性质3:
相同权值的边,对mst的贡献总是相同的
也就是mst的边权序列总是相同的
证明:
设两个mst,边权序列(升序)最前的不同位置,设a中的e更小
将e插入到b,形成了一个环,其中一定存在一条边 【权值>e】
(否则,因为e是第一个不同,更小意味着两棵树都有,则在a中形成环)
显然是可以替换掉的,违背【都是mst】
推论:【没有相同边权】的无向图,最小生成树唯一

性质4:
连通图上,a到b【最长边最小】的路径,总是在kruskal生成的mst上
证明:
感受一下,显然很对
首先,每个mst的贡献一定是一样的,这个很好推
然后这个知道以后,反证一个非mst,会使当前mst变小,用类似前面的方法即可

kruskal

并查集维护连通性,每次取最小的,连接两个森林的一条边
时间复杂度$O(m log_2 m)$

prim

维护一个树,开始只有一个节点1
加入n-1次,每次选择【加入这棵树的代价】最小的那个点
时间复杂度如果直接暴力是 $O(n^2)$ 的,如果加入二叉堆可以变成 $O(m log_2 n)$
如果logm和logn相差不大的话,写kruskal,否则显得更傻
所以说prim只适用于稠密图

练习

自行搜索tag

有意思的变形

CH6201 走廊泼水节

Boruvka

并查集维护联通块,然后不断进行下面操作:
枚举每条边,得到距离每个联通块最近的联通块,然后合并起来
这样联通块大小在i次后至少为 $2^i$ ,故只执行log次

这东西在解决【完全图,边权为位运算的极值mst】问题时非常方便,详见这里

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b399.html
转载请注明出处,谢谢!