B

采用数学归纳法证明Fi(m)为Ti的边集:

  1. 当i = 1时。当前没有被使用的边的集合为L1(m),因为图连通,所以通过Kruskal算法插入L1(m)后,所得到的生成森林一定是一棵最小生成树,即T1。又因为F1(m)为通过Kruskal算法插入L1(m)后得到的生成森林的边集,所以F1(m)为T1的边集,命题成立。
  2. 假设i = k时,成立。则当i = k + 1时,当前没有被使用的边的集合为L1(m) \ F1(m) \ F2(m) \ ... \ Fk(m) = L2(m) \ F2(m) \ ... \ Fk(m) = Lk(m) \ Fk(m) = Lk+1(m)。因为图连通,所以通过Kruskal算法插入Lk+1(m)后,所得到的生成森林一定是一棵最小生成树,即Tk+1。又因为Fk+1(m)为通过Kruskal算法插入Lk+1(m)后所得到的生成森林的边集,所以Fk+1(m)为Tk+1的边集,命题成立。

综上所述,对于正整数i,Fi(m)为Ti的边集。

C

这个就不采用过于形式化的证明了。

题目想说的是,如果两个点(u, v)在(V, Fi(t))中属于同一连通分量,那么对于任意的j < i,(u, v)在(V, Fj(t))中也属于同一连通分量。

这个是由Kruskal算法造成的,Kruskal算法每次选一条边,判断这两个点是否在同一个连通分量中,如果在,则放弃这条边,如果不在,则将选择这条边,并将两个点合并到同一连通分量中。

(u, v)在(V, Fi(t))中属于同一连通分量,那么这条连接(u, v)的边一定是在(V, Fj(t))中被放弃过的,所以(u, v)在(V, Fj(t))中属于同一连通分量。

D

这道题实际上是找et+1这条边所属的最小生成树Tj。

由于我们知道D1(t), D2(t), ...,u't+1和v't+1,根据C的单调性条件,我们选择二分j,判断u't+1和v't+1是否在同一连通分量中,即可找到最小的j,使得u't+1和v't+1在同一连通分量中。

通过并查集判断是否在同一连通分量的复杂度为O(alpha(n)),二分的复杂度为O(logn),因此总的时间复杂度为O(alpha(n)logn)。

实际上这里的alpha(n)是反阿克曼函数,并查集的按秩合并+路径压缩的优化可以参考《算法导论》。

E

首先,对边集按权值从小到大排序。时间复杂度O(mlogm) = O(mlogn)。

接下来,对于每一条边按照D中的方法,找到它所属于的最小生成树Tj。如果还未建立第j个并查集,则动态申请第j个并查集,并进行初始化。将当前边插入第j个并查集中。

comments powered by Disqus