推 imprazaguy:謝謝，我瞭解了 09/25 23:41
※ 引述《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)
希望這樣有回答到你的問題^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.94.1
※ 編輯: f54512 來自: 220.135.94.1 (09/25 22:59)