[问题] 关于 Kruskal's algorithm 证明的问题

楼主: imprazaguy (Wayne)   2008-09-25 22:19:56
版上没什么文章,PO的问题麻烦知道的人解答一下。
老师投影片上有关 Kruskal's algorithm 的证明有段叙述如下:
(无法打下标,将就一下)
insert ek into T*: a cycle is formed, and there is one edge, denoted by e*,
that is not in T and c(e*)>c(ek).
我的问题是:
可以确定一定找得到一e*不在T上,
但如何说明e*在cycle上?
麻烦大家解决我的疑问,谢谢!

Links booklink

Contact Us: admin [ a t ] ucptt.com