[圖論] Kruskal's和Prim's Algorithm一問

看板Math作者 (玩我豬)時間12年前 (2013/03/09 23:05), 編輯推噓4(4推 0噓 21→)
留言25則, 6人參與, 6年前最新討論串1/1
題目在這: http://uptow.net/yP2 (不如意思,要勞煩點進去) (a)部份我懂作啊, 但是(b)部份我想問答案是不是"False", 因為最少cost的edge應該不是唯一吧? 所以想向各位版友指教怎麼做了.謝謝. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 112.119.152.140
推
03/09 23:13, , 1F
我覺得是FALSE
03/09 23:13, 1F
→
03/09 23:14, , 2F
基本上若存在唯一的最小生成數的話每個邊都必須是唯
03/09 23:14, 2F
→
03/09 23:14, , 3F
一的重量
03/09 23:14, 3F
→
03/09 23:15, , 4F
我想問問怎麼寫證明呢?可以給給方向嗎?謝謝
03/09 23:15, 4F
→
03/09 23:16, , 5F
你是回答FALSE,只需要舉反立即可
03/09 23:16, 5F
→
03/09 23:16, , 6F
猛打錯字抱歉...
03/09 23:16, 6F
→
03/09 23:20, , 7F
先謝謝你的回答啊,是1條edge附上minimum weight,之後
03/09 23:20, 7F
→
03/09 23:21, , 8F
contradiction哪裡找到呢?
03/09 23:21, 8F
推
03/09 23:21, , 9F
你只要舉一個兩個相同重量的最小邊的圖就可以了
03/09 23:21, 9F
→
03/09 23:28, , 10F
但是這兩個spanning trees都是由同一G所得出啊?可否
03/09 23:28, 10F
→
03/09 23:28, , 11F
用小畫家給我一個例子呢?真是萬分感謝版友啊Orz
03/09 23:28, 11F
→
03/09 23:30, , 12F
給反例就是給一張圖G, 最小邊不唯一, 且兩種演算法求
03/09 23:30, 12F
→
03/09 23:30, , 13F
出來的生成樹相異
03/09 23:30, 13F
推
03/09 23:32, , 14F
每個邊都相同重量的圖就是反例了吧
03/09 23:32, 14F
推
03/09 23:32, , 15F
樓上你救了我ＱＱ
03/09 23:32, 15F
→
03/10 12:08, , 16F
若每邊的重量相同,那我用Kruskal's algorithm時就任
03/10 12:08, 16F
→
03/10 12:08, , 17F
取嗎?
03/10 12:08, 17F
→
03/10 12:09, , 18F
不好意思,我指是任取任何一條邊嗎?
03/10 12:09, 18F
→
03/10 16:41, , 19F
是的 MST要舉反例用這招馬上就解決了
03/10 16:41, 19F
→
03/10 23:24, , 20F
謝謝樓上各位版友熱心指導^_^
03/10 23:24, 20F
→
08/13 17:29, , 21F
猛打錯字抱歉... https://muxiv.com
08/13 17:29, 21F
→
09/17 15:23, , 22F
用小畫家給我一個例子呢 https://daxiv.com
09/17 15:23, 22F
→
11/10 11:30, , 23F
但是這兩個spanni https://daxiv.com
11/10 11:30, 23F
→
01/02 15:18, 7年前 , 24F
我想問問怎麼寫證明呢? https://daxiv.com
01/02 15:18, 24F
→
07/07 10:44, 6年前 , 25F
給反例就是給一張圖G, https://moxox.com
07/07 10:44, 25F
‣ 更多 playmypig 的文章
文章代碼(AID): #1HEq_CKW (Math)