特定图中哈密顿性与欧拉性的等价性探讨
特定图中哈密顿性与欧拉性的等价性探讨
嘿,最近我钻研图论的时候,脑子里突然冒出来一个问题。先跟大伙快速回顾几个基础定义,方便咱们后续讨论:
- 图:由顶点集合和弧集合构成,每条弧都对应恰好两个不同的顶点——换句话说,这里没有自环、无向弧以外的有向弧,也不存在同一对顶点之间的多条重复弧。
- 路径:由有限个相邻顶点组成的序列,每两个连续顶点之间都有图中的弧相连;而且规则是,如果序列里某个顶点重复出现了,那后面的顶点就不能再重复啦(简单说就是路径里没有重复的弧)。
- 回路:起点和终点是同一个顶点的路径。
- 简单路径:除了起点和终点可能重合之外,序列里没有其他重复顶点的路径。
- 环:属于简单路径范畴的回路(也就是除了首尾顶点,其他所有顶点都不重复的回路)。
- 哈密顿图:存在哈密顿环的图,也就是能找到一个包含图中所有顶点的环。
- 欧拉图:存在欧拉回路的图,也就是能找到一个包含图中每条弧(每一对相邻顶点的连接)的回路——我还没把这个定义说完,核心就是要覆盖所有的弧啦。
我现在的疑问是:有没有某一类特定的图,它的哈密顿性和欧拉性是等价的?也就是说,在这类图里,只要它是哈密顿图,就一定是欧拉图;反过来,只要是欧拉图,也必然是哈密顿图?
备注:内容来源于stack exchange,提问作者Amanda Wealth
相关产品推荐
相关产品推荐

