Re: [問題] 關於 Kruskal's algorithm 證明的問題
※ 引述《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中，沒有影響。
又要麻煩你了，謝謝。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.192.40
※ 編輯: imprazaguy 來自: 118.168.192.40 (09/26 01:19)
推
09/26 03:29, , 1F
09/26 03:29, 1F
→
09/26 03:29, , 2F
09/26 03:29, 2F
已修正
※ 編輯: imprazaguy 來自: 140.112.30.125 (09/26 10:11)
推
09/26 15:52, , 3F
09/26 15:52, 3F
→
09/27 00:01, , 4F
09/27 00:01, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：