生成树相关

生成树有两个常用的性质

性质1:切割性质

若图G的所有边权值都不相同,设点集S是既非空集也非全集的点集V的子集,边e是顶点分别在S和∁vS集合中的所有边中权值最小的一个,则V中的所有生成树均包含e.

证明

是连接S和∁vS集合所有边权最短的边.若存在生成树不包含,连接,形成一个环,环上至少有一条不是的边能够连接集合V和∁vS ,其权值比大,用替换后,MST变小,矛盾!因此所有生成树均有边.

性质2:回路性质

若所有边权值都不相同.设C是G中的任意回路,边e是C上权值最大的边,则G中所有生成树均不包含e.

证明

若存在生成树包含C环上的最大权值边,删除后,变成两个连通块S和T,C环上u->v不经过边的路径中至少有一条边横跨S和T连通块,用该边替换后,生成树变小,矛盾!因此所有生成树均没有边.

生成树”们”

增量最小生成树

N个点的空图上依次加入M条带权边,求每加入一条后的MST权值.

解法1

每生成一个MST就把没有选的边删掉,加入一条新边就做一次(N-1)+1=N条边的Kruskal.
时间复杂度O(mnlogn).

解法2

我们发现,加入一条边e=(u,v)后,图中恰好包含一个回路,(u,v)在这个回路中.据回路性质,只需删除该回路上权值最大的边.
在加边之前的MST上用DFS找到u到v的唯一路径上权值最大的边,再和e比较,删除较大者即可.
时间复杂度O(mn).

最小瓶颈生成树

给出加权无向图,求一棵生成树,使最大边权值尽量小.

解法

由于只关心最大边权值,我们可以从一个空图开始,将边按照权值从小到大依次加入,当图第一次联通时,那棵生成树就是答案.
而这就是Kruskal算法,即原图的最小生成树就是一棵最小瓶颈生成树.

最小瓶颈路

给出加权无向图的两个结点u和v,求出从u到v的一条路径,使得路径上权值最大的边的权值尽量小.

解法1

二分+BFS.
二分最大边的权值,BFS跑一遍看这样的最大边权是否可以找到一条从u到v的路径.
时间复杂度O(logd*m) (d表示最大的边权的最大值).

解法2

可以像求“最小瓶颈生成树”一样思考.
最小瓶颈路便是最小生成树上的对应路径.

次小生成树

求权值之和是第二小的生成树的权值和.

预备结论

次小生成树一定可由MST更换一条边得到.

证明

让我们换种方式去看待这个结论(一个生成树可以通过换边得到另一个生成树).
T是某一棵MST,T0是任一棵异于T的生成树,通过变换T0->T1->T2->…->Tn(T)变成最小生成树.
所谓的变换是,每次把Ti中的某条边换成T中的一条边, 而且树T(i+1)的权小于等于Ti的权.

在Ti中任取一条不在T中的边uv.
把边uv去掉,就剩下两个连通分量A和B,在T中必有唯一的边u’v’ 连结A和B.
显然u’v’的边权比uv小 ,把u’v’替换uv即得树T(i+1).
T(n-1) 也就是次小生成树且跟T差一条边,结论得证.

解法1

枚举MST中不在次小生成树中出现的边(n-1次),每次在剩下的边里求一次MST.
时间复杂度O(nmlogm).

解法2

枚举新加的一条边(u,v),这时会出现一条回路,要删除的边必在u到v的路径上.
于是,我们可以处理出每对结点(u,v)的最小瓶颈路的最大边长f(u,v),删除这个边长即可.
时间复杂度O(mlogm+n²+m).

附PDF

显示 Gitment 评论