作者mqazz1 (无法显示)
看板Math
标题[图论] Kruskal MST
时间Sat Jul 23 20:12:23 2011
第一页
http://ppt.cc/LTLs
第二页
http://ppt.cc/ysRj
第二页的第一行
请问为什麽这样会产生cycle?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.27.31
1F：推 suhorng :Kruskal弄出来的会是一棵G的生成树 既然是生成树那加 07/23 20:33
2F：→ suhorng :上任一条边就会形成环了 07/23 20:33
3F：→ mqazz1 :可以再请问为什麽第二页最後两行 会出现矛盾吗? 07/23 20:53
4F：推 suhorng :既然把e_k加入T*形成一个环,且环上又有比e_k大的边e* 07/23 21:20
5F：→ suhorng :(由之前的假设,倒数第四行),那麽,把e*拔掉之後,你会 07/23 21:21
6F：→ suhorng :得到另一个生成树,且此生成树的 cost 是 cost(T*) + 07/23 21:21
7F：→ suhorng :cost(e_k) - cost(e*) < cost(T*), 这与 T* 是一个最 07/23 21:22
8F：→ suhorng :小生成树的假设矛盾. 07/23 21:22