作者befdawn (蜜蜂P助)
看板Grad-ProbAsk
标题[理工] 离散 证明 Hamiltonian cycle 不存在
时间Sat Sep 29 17:31:52 2018
https://i.imgur.com/I7Nrpjs.jpg
https://i.imgur.com/Hzmk2MI.jpg
请问这题的 c 解答里只说明 3x3 没有 Hamiltonian cycle 应该是不够的吧？
但如果 5x5 又不知道怎麽说明，还是只能说瑞凡我画不出来？
还请高手释下，感恩~
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.226.93.95
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1538213515.A.51C.html
1F：推 muski: 3*3的图中四个角上的点deg(v)皆为2 代表hamilton要走过这d 09/29 18:03
2F：→ muski: eg(v)为2的边 但这些边却已连成一个无法连结内部点的环路 09/29 18:03
3F：→ befdawn: 这个我知道，我的问题是只证明3x3是不是不够@@ 09/29 18:27
4F：推 silence0925: 5x5必含3x3 所以没有吧 09/30 13:54
5F：→ befdawn: 楼上是说用 subgraph 来看吗？ 10/03 00:10