※ 引述《f54512 (这不是柏良 这不是柏良)》之铭言：
: 不知道我有没有误会你的问题
: 在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)
: 希望这样有回答到你的问题^^
对了我又想到了一个问题。
老师证明中的k值，满足e1＝e1*, e2＝e2*, ..., e(k-1)＝e(k-1)*, ek≠ek*，
我认为i>=(k+1), ei与ei* 不一定相等。
如此一来，
当ek加入T*中形成cycle，cycle中可以找到一edge e* 使得 c(e*) > c(ek)。
而e*=ei*, i>=k
如何说明e*不会出现在T中？
e*在T中会影响证明吗？
事实上，从你的推论中，已经得出 c(e*) > c(ek) 且 e* 和 ek 位于 cycle 中，
所以将 ek 取代 e* 会产生出比 T* cost更小的spanning tree，造成矛盾。
因此我认为 e* 是否在T中，没有影响。
又要麻烦你了，谢谢。