算法概论作业5.21 5.22 5.32

算法概论作业

5.22

a) 设这个环的顶点集为 C ，最大权边为 e u v ( , ) 。设在某一时刻， C 被 cut 成两
个部分
s s 1 2 , ，其中 s1包含 u ，而 s2 包括 v 。因 C 是一个环，所以连结 s s 1 2 , 的
边至少有两条，其中至少有一条不为 e 的边 e'，其权不大于 e ，由 cut property
可知，存在不含有 e 的最小生成树。
b) 因为每次删除的都是图 G 中权最大的环边，由题述中的性质可证。
c) 参考 Ex.3.11。
d) O E ( )