※ 引述《imprazaguy (Wayne)》之铭言：
: 版上没什么文章，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上？
: 麻烦大家解决我的疑问，谢谢！
不知道我有没有误会你的问题
在T中找到一个edge ek 不在T*中
将ek加到T*中会形成一个cycle
而在这个cycle上存在一个edge e*并且c(e*) > c(ek)
如果c(e*) < c(ek) < c(ek*) 则e*会是某个edge ei 1<=i<k
如果cycle上的所有edge的cost均小于c(ek)
如此一来ek就会在T中行成一个cycle 违反T是spanning tree这个前提
所以必定可以在cycle上找到edge e*且c(e*) > c(ek)
希望这样有回答到你的问题^^