- 最后登录
- 2024-3-28
- 在线时间
- 3998 小时
- 阅读权限
- 70
- 注册时间
- 2009-12-4
- 积分
- 5759
- 帖子
- 1934
- 精华
- 7
- UID
- 1244890
- 性别
- 男
- 兴趣爱好
- 破解
DIY
- 积分
- 5759
- 帖子
- 1934
- 精华
- 7
- UID
- 1244890
- 性别
- 男
- 兴趣爱好
- 破解
DIY
|
发表于 2017-10-26 15:58:04
|显示全部楼层
折翼蚂蝗 发表于 2017-10-23 00:28
占一楼,用于发布 穷举网状图 的修改版,以及回答6楼的问题。
----------------------------------------- ...
确实没有哈密顿回路
之前忘记了连通的2-正则图就是一个环路这么简单的判定。。。假设哈密顿回路存在,我们只要去掉一些度为3的点之间的连接就可以了。
容易看出,这个图里度为3的点是8个一组,分布在五个区域里的,所以“不走的边”只有红蓝两种选择。去掉蓝边会变成2个连通分支,去掉红边会变成5个连通分支,故哈密顿回路不存在。
|
|