[理工] Hamilton cycle的判断问题 ok8752665 PTT批踢踢实业坊

[理工] Hamilton cycle的判断问题

楼主: ok8752665 (dd8752665) 2019-06-21 21:21:44

http://i.imgur.com/dTItiFa.jpg
老师上课的时候说
如果里面有小cycle就不会有大cycle
所以不会有hamilton cycle
不过如果图长这样
http://i.imgur.com/sTLrlT3.jpg
里面的456型成一个小cycle
不过依然可以走1234561为一个hamilton cycle不是吗？
是我哪里理解错了？

作者: mistel (Mistel) 2019-06-23 17:55:00

从deg=2的点推应该会是比较稳妥的办法，或者你把你的图画成跟他同构的另一个图很明显他就有HC 好像没有回答到你的问题哈哈哈

楼主: ok8752665 (dd8752665) 2019-06-23 19:44:00

好吧看来这个找小cycle的方法不能用

作者: DLHZ ( ) 2019-06-24 01:22:00

要的话我认为要加上连接另一个cycle的点不得为adjacent

楼主: ok8752665 (dd8752665) 2019-06-24 09:04:00

什么意思?

继续阅读

[理工] 离散_关于排列fmtshk 离散 3-2 排列 3-17houallan5478 [理工] 线代笔记例题疑问（么正对角化）mistel Re: [理工] 资料结构_p37第9题s29441910 Re: [理工] 离散_p3-18范例5Honor1984 [理工] 离散_p3-18范例5fmtshk Re: [理工] 线代 1-74Honor1984 [理工] 线代 1-74paruru48 Re: 离散题库5-59题Honor1984 [理工] 向量空间的问题abcd012345