哈尔滨师范大学吧 关注：191,706贴子：5,229,855
- 41回复贴，共1页
其实这个用到了图论的知识，
可以将题转化为如这两个图：
根据题意，其实就是看这个图是不是一个汉密尔顿图[1]
汉密尔顿图有一个ore的推论：
设 G=(V, E) 是具有 n 个节点的简单无向图，如果对于任意两个不相邻的节点 u, v∈V，均有 deg(u)+deg(v)≥n-1，则 G 中一定存在 Hamilton 回路
但这个推论不完整，因为这里的说的是一定存在汉密尔顿回路。。
所以就得引申出另外一个推论：
设 G=(V, E) 是具有 n 个节点的简单无向图，n≥3，如果对于任意的 u∈V，均有 deg(v)≥n/2，则 G 是 Hamilton 图
其实判断一个图是否是汉密尔顿图确实是蛮麻烦的一件事，你可以先看看图论入门[2]
然后就会看到小时候的那个七桥问题[3]
然后你就会看到这个汉密尔顿图了
或者可以写一个这个图的遍历程序。会发现，这个图不是汉密尔顿图
注：
[1]http://en.wikipedia.org/wiki/Hamiltonian_path
[2]http://wenku.baidu.com/view/9a42ca0979563c1ec5da71f9
http://baike.baidu.com/view/79350.htm
[3]http://zh.wikipedia.org/zh-cn/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98
可以将题转化为如这两个图：
根据题意，其实就是看这个图是不是一个汉密尔顿图[1]
汉密尔顿图有一个ore的推论：
设 G=(V, E) 是具有 n 个节点的简单无向图，如果对于任意两个不相邻的节点 u, v∈V，均有 deg(u)+deg(v)≥n-1，则 G 中一定存在 Hamilton 回路
但这个推论不完整，因为这里的说的是一定存在汉密尔顿回路。。
所以就得引申出另外一个推论：
设 G=(V, E) 是具有 n 个节点的简单无向图，n≥3，如果对于任意的 u∈V，均有 deg(v)≥n/2，则 G 是 Hamilton 图
其实判断一个图是否是汉密尔顿图确实是蛮麻烦的一件事，你可以先看看图论入门[2]
然后就会看到小时候的那个七桥问题[3]
然后你就会看到这个汉密尔顿图了
或者可以写一个这个图的遍历程序。会发现，这个图不是汉密尔顿图
注：
[1]http://en.wikipedia.org/wiki/Hamiltonian_path
[2]http://wenku.baidu.com/view/9a42ca0979563c1ec5da71f9
http://baike.baidu.com/view/79350.htm
[3]http://zh.wikipedia.org/zh-cn/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98
