推 dreamoon:你問的問題第六行的"而e*=ei, i>=k"是不是應該改成 09/26 03:29
→ dreamoon:"而e*=ei*, i>=k"? 09/26 03:29
已修正
※ 編輯: imprazaguy 來自: 140.112.30.125 (09/26 10:11)
推 f54512:e*是否在T中並不影響證明 我們只是透過e*導到T*會形成矛盾 09/26 15:52
→ imprazaguy:謝謝回答 09/27 00:01
※ 引述《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)