如何证明用 Kruskal's 算法生成的树是最小生成树
答案:1 悬赏:40
解决时间 2021-01-03 12:20
- 提问者网友：寂寞梧桐
- 2021-01-02 15:39
如何证明用 Kruskal's 算法生成的树是最小生成树
最佳答案
- 二级知识专家网友：罪歌
- 2021-01-02 17:02
为了避免最小生成树不唯一的问题，可以不妨假设这个图所有的边长都不相等
（注意最小生成树的总长度是原图边长的连续函数，所以可以这样加强条件）
然后用反证法，假定Kruskal算法中的第k步首次出现错误，算法选了E1，但实际上必须选另一条边E2才能得到最小生成树T0
E1连接了两个连通分支，这两个连通分支在最终的T0里是连通的，所以把T0和E1放在一起之后形成的图有一个环，在这个环里一定有k步或之后新选的边（如果没有的话仅凭前k-1条边和E1不会构成环），依照E1的定义，这个环里存在比E1长的边，用E1换掉这条边之后得到的树T1比T0更短，矛盾
（注意最小生成树的总长度是原图边长的连续函数，所以可以这样加强条件）
然后用反证法，假定Kruskal算法中的第k步首次出现错误，算法选了E1，但实际上必须选另一条边E2才能得到最小生成树T0
E1连接了两个连通分支，这两个连通分支在最终的T0里是连通的，所以把T0和E1放在一起之后形成的图有一个环，在这个环里一定有k步或之后新选的边（如果没有的话仅凭前k-1条边和E1不会构成环），依照E1的定义，这个环里存在比E1长的边，用E1换掉这条边之后得到的树T1比T0更短，矛盾
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯
| • 手机登qq时，显示手机磁盘不足，清理后重新登 |
| • 刺客的套装怎么选啊？ |