[求助]欧拉图和哈密顿图

AaronSpark

欧拉图和哈密顿图有什么区别？谁能解释一下，谢谢

雪缘

1736年瑞士著名数学家欧拉(Euler)解决了(立陶宛)哥尼斯堡城七桥问题：哥尼斯堡城被Pregel河分成了四部分，它们之间有七座桥， 如图所示。当时人们提出了一个问题： 能否从城市的某处出发，过每座桥一次且仅一次最后回到原处。


欧拉巧妙地解决了这个问题：把四块陆地设想为四个顶点，分别用A、B、C、D表示，而将桥画成相应的边，如图所示于是问题转化为该图中是否存在经过每条边一次且仅一次的回路。
欧拉经过研究，终于找到解决这类问题的一个简便原则，可以鉴别一个图(包括多重图)能否一笔画，并对七桥问题给出了否定的结论。

通过无向连通图G的每条边一次且仅一次的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。 定义包含多重图在内, 即欧拉回路中允许顶点重复出现。


1859年, 爱尔兰数学家哈密顿(Halmiton)提出一个“周游世界”的游戏, 它把图所示的正十二面体的二十个顶点当作是地球上的二十个城市, 要求旅游者从某个城市出发, 沿棱走过每个城市一次且仅一次, 最后回到出发点。图中粗线所构成的回路就是问题的答案。
定义通过图G的每个顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图。哈密顿通路是通过图G的每个顶点一次且仅一次的通路。


哈密顿图的性质：
1. 每个哈密顿图都一定是连通的且每个顶点的度均大于等于2。
2. 设G是有n个顶点的连通图, 则G的哈密顿通路是长度为n – 1的基本通路, 哈密顿回路是长度为n的回路。
3. 如果存在度为1的顶点, 那么G没有哈密顿回路。
4. 设v是G中度为2的顶点, 若G中有哈密顿回路, 则该回路必经过以v为端点的那两条边。
5. 设v是G中度大于2的顶点, 若G有哈密顿回路, 则该回路只使用以v为端点的某两条边。

雪缘

欧拉图和哈密顿图的区别在于
欧拉回路是简单回路，而哈密顿图是基本回路。
欧拉图遍历边，而哈密顿图遍历顶点。

它们之间几乎没有什么联系。
有的图只是欧拉图
有的图只是哈密顿图
有的图既是欧拉图又是哈密顿图
有的图则两者皆不是。

虽然欧拉回路和哈密顿回路都是遍历图
但两者的困难程度却大不相同
欧拉图已“彻底和漂亮”地解决了
对哈密顿图至今还没有找到简单的充要条件

AaronSpark

那这个问题是属于哪个领域的问题？如果想要了解的详细点应该看哪方面的资料？

simon21

这个是拓扑学的问题

simon21

找本代数拓扑学看看