发帖
雷达卡
23.1-5
证明:设C=v0, v1,…,vk是一个圈,其中边e=(v0, vk)是权值最重的边。只需要构造一棵不包含e=(v0, vk)的MST即可。设T是一棵包含e=(v0, vk)的MST，则删除e会使T变成两个连通分支V1，V2，v0V1，vkV2。依次检测顶点v1,…,vk，找到第一个在V2中的顶点vi(这样的vi一定能找到，因为vkV2)，从而e’=(vi-1, vi)是穿过割(V1,V2)的一条边，并且w (v0, vk) w(vi-1, vi)。则T’=T-e+e’是一棵新的MST。
23-4(a)
证明: 设T中的边按照权值非递减顺序依次为e1, e2,…, en-1,即算法依次保留边e1, e2,…, en-1。设边集Ai ={ e1, e2,…, ei}，1in-1则只需要证明每个Ai 都是某棵最小生成树的子集。用归纳法证明。i=1时，设T’是一棵最小生成树，如果(u, v)=e1T’, 结论自然成立。如果e1T’，则在T’中存在u到v的路径p。因为删除e1会使图不连通，即删除e1会使顶点集合V划分为两个子集V1和V2，其中uV1，vV2。则 ...
京公网安备 11010802022788号
