[問題] 關於 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