IT 面试题库

欧拉图与哈密顿图有什么区别?判定的充要条件是什么?

中级简答题算法工程师机器学习工程师数据科学家欧拉图哈密顿图图论

题目

请以“一笔画”与“周游一遍顶点”为直觉,说明欧拉图、哈密顿图的定义及常用判定(充分/必要条件)。

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 75 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

欧拉图(Eulerian):存在经过每条边恰好一次的回路(欧拉回路),即“一笔画且回到起点”。

哈密顿图(Hamiltonian):存在经过每个顶点恰好一次的回路(哈密顿回路),即“周游所有城市一圈”。

- 必要条件:若图有 n≥3 个顶点且哈密顿,则对任意非空真顶点子集 S,有 ω(G−S) ≤ |S|(去掉 S 后连通分支数不超过 |S|)。

- 充分条件(Dirac 定理):n≥3 的简单图中,若每个顶点度数 ≥ n/2,则必为哈密顿图;Ore 定理:对任意不相邻 u,v 有 deg(u)+deg(v) ≥ n 则哈密顿。

核心区别:欧拉关注“边覆盖一次”,哈密顿关注“顶点覆盖一次”;前者有简洁充要条件,后者判定困难。经典类比:欧拉=邮差送信走遍每条路,哈密顿=旅行商走遍每座城。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题