[理工] 离散证明 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 不存在