[理工] 離散證明 Hamiltonian cycle 不存在 befdawn PTT批踢踢實業坊

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

作者: befdawn (橙花雨露) 2018-09-29 17:31:52

https://i.imgur.com/I7Nrpjs.jpg
https://i.imgur.com/Hzmk2MI.jpg
請問這題的 c 解答裡只說明 3x3 沒有 Hamiltonian cycle 應該是不夠的吧？
但如果 5x5 又不知道怎麼說明，還是只能說瑞凡我畫不出來？
還請高手釋下，感恩~

作者: muski (muski) 2018-09-29 18:03:00

3*3的圖中四個角上的點deg(v)皆為2 代表hamilton要走過這deg(v)為2的邊但這些邊卻已連成一個無法連結內部點的環路

作者: befdawn (橙花雨露) 2018-09-29 18:27:00

這個我知道，我的問題是只證明3x3是不是不夠@@

作者: silence0925 (小文青) 2018-09-30 13:54:00

5x5必含3x3 所以沒有吧

作者: befdawn (橙花雨露) 2018-10-03 00:10:00

樓上是說用 subgraph 來看嗎？

繼續閱讀

[理工] 線代 8-36頁AAQ8 Fw: [問題] BJT小訊號電路增益suspect1 [理工] 計組 performanceTampaBayRays [理工] 線代第八章證明AAQ8 [理工] 資結7-58！Aa841018 [理工] OS Safety Alg.jojoboy0115 [理工] 離散 3-1u0424064 [理工] 線代2-39！Aa841018 [理工] 離散等價關係 2-45 範例4QoGIVoQ Re: [理工] 計組MIPS assembly codeKWire

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

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