看板 [ DiscreteMath ]
討論串[問題] 關於 Kruskal's algorithm 證明的問題
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#3
Re: [問題] 關於 Kruskal's algorithm 證明的問題
推噓2(2推 0噓 2→)留言4則，0人參與, 最新作者imprazaguy (Wayne)時間17年前 (2008/09/26 00:57), 編輯資訊
0
0
0
內容預覽:
對了我又想到了一個問題。. 老師證明中的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*)
(還有215個字)
#2
Re: [問題] 關於 Kruskal's algorithm 證明的問題
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者f54512 (這不是柏良 這不是柏良)時間17年前 (2008/09/25 22:56), 編輯資訊
0
0
0
內容預覽:
不知道我有沒有誤會你的問題. 在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
(還有79個字)
#1
[問題] 關於 Kruskal's algorithm 證明的問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者imprazaguy (Wayne)時間17年前 (2008/09/25 22:20), 編輯資訊
0
0
0
內容預覽:
版上沒什麼文章，PO的問題麻煩知道的人解答一下。. 老師投影片上有關 Kruskal's algorithm 的證明有段敘述如下：. （無法打下標，將就一下）. insert ek into T*: a cycle is formed, and there is one edge, denoted
(還有64個字)
首頁
上一頁
1
下一頁
尾頁