请以“一笔画”与“周游一遍顶点”为直觉,说明欧拉图、哈密顿图的定义及常用判定(充分/必要条件)。
欧拉图(Eulerian):存在经过每条边恰好一次的回路(欧拉回路),即“一笔画且回到起点”。
哈密顿图(Hamiltonian):存在经过每个顶点恰好一次的回路(哈密顿回路),即“周游所有城市一圈”。
- 必要条件:若图有 n≥3 个顶点且哈密顿,则对任意非空真顶点子集 S,有 ω(G−S) ≤ |S|(去掉 S 后连通分支数不超过 |S|)。
- 充分条件(Dirac 定理):n≥3 的简单图中,若每个顶点度数 ≥ n/2,则必为哈密顿图;Ore 定理:对任意不相邻 u,v 有 deg(u)+deg(v) ≥ n 则哈密顿。
核心区别:欧拉关注“边覆盖一次”,哈密顿关注“顶点覆盖一次”;前者有简洁充要条件,后者判定困难。经典类比:欧拉=邮差送信走遍每条路,哈密顿=旅行商走遍每座城。
题目与答案就在本页;收藏、批注和错题重练在应用内