圖論

看板Math作者 (小強)時間7年前 (2019/02/06 00:24), 編輯推噓3(3推 0噓 26→)
留言29則, 3人參與, 7年前最新討論串2/2 (看更多)
想請問除了實際去畫一條以外 有什麼方法能有效率的判斷是否有Hamilton cycle嗎？ 另外問2的a、b 題目不太清楚 另外對這種畫圖題，請問出發的概念都是什麼？ https://i.imgur.com/sy9Ywo8.jpg
https://i.imgur.com/MfNXism.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.200.194 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1549383889.A.AC8.html
推
02/06 02:45, 7年前 , 1F
你不是有那本圖論嗎 看看Hamilton被放到哪個單元吧
02/06 02:45, 1F
→
02/06 02:45, 7年前 , 2F
這個問題靠北難XD 說真的畫一個最快
02/06 02:45, 2F
→
02/06 02:48, 7年前 , 3F
2. 出題老師的靈感肯定是Ramsey number 這應該也有
02/06 02:48, 3F
→
02/06 02:48, 7年前 , 4F
一個單元 這個問題難到Erdos都在diss他XD 總之如(
02/06 02:48, 4F
→
02/06 02:48, 7年前 , 5F
a)(b)的情況 說實話畫一個也是最快了
02/06 02:48, 5F
→
02/06 02:50, 7年前 , 6F
不騙你 圖論的題目 叫你畫一個已經是不能再簡單的
02/06 02:50, 6F
→
02/06 02:50, 7年前 , 7F
題目了 要證明有一個或證明沒有 難度都是翻倍的ww
02/06 02:50, 7F
→
02/06 02:50, 7年前 , 8F
w
02/06 02:50, 8F
→
02/06 02:51, 7年前 , 9F
也不能這樣說吧 後面還是有畫一個需要特定演算法種
02/06 02:51, 9F
→
02/06 02:51, 7年前 , 10F
類
02/06 02:51, 10F
→
02/06 02:51, 7年前 , 11F
不過你問的hamilton和ramsey number剛好都沒有很有
02/06 02:51, 11F
→
02/06 02:51, 7年前 , 12F
效的演算法
02/06 02:51, 12F
推
02/06 02:54, 7年前 , 13F
噢 2. 的意思是 給你5個點 任兩點之間一定有一條線
02/06 02:54, 13F
→
02/06 02:54, 7年前 , 14F
但可以是藍的或紅的
02/06 02:54, 14F
→
02/06 03:29, 7年前 , 15F
我說的不准確 有效的演算法說不定有 但有效的判別
02/06 03:29, 15F
→
02/06 03:29, 7年前 , 16F
法是沒有的 hamilton我記得有幾個太明顯的特例可以
02/06 03:29, 16F
→
02/06 03:29, 7年前 , 17F
刪去 剩下真的很麻煩 ramsey我猜連有效演算法都沒
02/06 03:29, 17F
→
02/06 03:29, 7年前 , 18F
有 不然不會一個R(6,6)都算不出來
02/06 03:29, 18F
→
02/06 05:04, 7年前 , 19F
我看那本裡面也是沒有對hamilton有太多的描述 網路
02/06 05:04, 19F
→
02/06 05:04, 7年前 , 20F
上有查到一些簡單的方法 不過也是像大大說的沒有
02/06 05:04, 20F
→
02/06 05:04, 7年前 , 21F
辦法有效辨別
02/06 05:04, 21F
→
02/06 05:06, 7年前 , 22F
還有2的a和b的題目還是有點不懂QQ 請問您說的狀況
02/06 05:06, 22F
→
02/06 05:06, 7年前 , 23F
是指哪一個
02/06 05:06, 23F
推
02/06 05:15, 7年前 , 24F
(a) 5個點 兩點之間一定要畫實線或虛線 其中有三個
02/06 05:15, 24F
→
02/06 05:15, 7年前 , 25F
點成為實線三角形 有三個點成為虛線三角形
02/06 05:15, 25F
→
02/06 05:16, 7年前 , 26F
(b) 沒有實線三角形也沒有虛線三角形
02/06 05:16, 26F
→
02/06 08:25, 7年前 , 27F
NP-complete ... 找到高效解法你就等著拿百萬大獎惹
02/06 08:25, 27F
→
02/07 00:19, 7年前 , 28F
樓上我知道QQ 其實只是想問這種畫圖題的出發點該
02/07 00:19, 28F
→
02/07 00:19, 7年前 , 29F
怎麼走、感覺這種一定要拿可是我也都想不太到...
02/07 00:19, 29F
‣ 更多 samuel30214 的文章
文章代碼(AID): #1SMRZHh8 (Math)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
3
29
圖論 圖論
samuel30214
7年前, 02/06
1
4
圖論 圖論
winnie31927
7年前, 05/20
在新視窗開啟完整討論串 (共2篇)
‣ 更多 samuel30214 的文章
文章代碼(AID): #1SMRZHh8 (Math)