[理工] 離散 證明 Hamiltonian cycle 不存在

看板Grad-ProbAsk作者 (蜜蜂P助)時間5年前 (2018/09/29 17:31), 編輯推噓2(2推 0噓 3→)
留言5則, 3人參與, 5年前最新討論串1/1
https://i.imgur.com/I7Nrpjs.jpg
https://i.imgur.com/Hzmk2MI.jpg
請問這題的 c 解答裡只說明 3x3 沒有 Hamiltonian cycle 應該是不夠的吧？ 但如果 5x5 又不知道怎麼說明，還是只能說瑞凡我畫不出來？ 還請高手釋下，感恩~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.226.93.95 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1538213515.A.51C.html
推
09/29 18:03, 5年前 , 1F
3*3的圖中四個角上的點deg(v)皆為2 代表hamilton要走過這d
09/29 18:03, 1F
→
09/29 18:03, 5年前 , 2F
eg(v)為2的邊 但這些邊卻已連成一個無法連結內部點的環路
09/29 18:03, 2F
→
09/29 18:27, 5年前 , 3F
這個我知道，我的問題是只證明3x3是不是不夠@@
09/29 18:27, 3F
推
09/30 13:54, 5年前 , 4F
5x5必含3x3 所以沒有吧
09/30 13:54, 4F
→
10/03 00:10, 5年前 , 5F
樓上是說用 subgraph 來看嗎？
10/03 00:10, 5F
‣ 更多 befdawn 的文章
文章代碼(AID): #1RhqQBKS (Grad-ProbAsk)