图论4-欧拉图,哈密顿图

摘要: 欧拉图和哈密顿图的相关概念和定理，参考徐俊明《图论及其应用》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文记录图论中的基本概念和定理，证明省略，本文是个备忘录，需要细节的时候再查相应的资料即可。

总览参考文章 图论导引，本文是基本概念的内容。

---

$1 欧拉迹，欧拉图

定义：遍历图中每条边的迹称为欧拉迹，一个图若包含闭欧拉迹，称为欧拉图。

• 定理(欧拉图判定定理)：$D$ 是欧拉图 $\Leftrightarrow D$ 是连通的平衡图
• 推论：$D$ 是非平凡连通图，则 $D$ 有欧拉 $(u,v)$ 迹 $\Leftrightarrow d_{D}^{+}(u) - d_{D}^{-}(u) = 1 = d_{D}^{-}(v) - d_{D}^{+}(v)$，且对任意 $x \in V \setminus \{u,v\}$ 均有 $d_{D}^{+}(x) = d_{D}^{-}(x)$
• 推论：一个 $G = (V, E)$ 是欧拉图 $\Leftrightarrow$ G 是连通图且没有奇度点
• 推论：一个非平凡图 G 包含欧拉迹 $\Leftrightarrow$ G 连通且奇度点不超过两个

两类著名的欧拉图：

1. de Bruijin 有向图：$B(d, n)$，主要应用在编码理论
2. Kautz 有向图：$K(d, n)$，主要应用在互联网络理论

---

$2 哈密顿路，哈密顿圈，哈密顿图

定义：经过图中所有顶点的路称为哈密顿路。闭哈密顿路称为哈密顿圈。包含哈密顿圈的图称为哈密顿图。

结论：完全二部图 $K_{m,n}$ 是哈密顿图 $\Leftrightarrow m = n$

与欧拉图的情况相反，至今尚未有哈密顿条件(图中存在哈密顿圈的充要条件)，以下有几个充分或必要条件。

必要条件

• 定理：图 $G = (V, E)$ 是哈密顿图，则 G 没有割点。即对 V 的任意非空子集 S，$G-S$ 至多有 $S$ 个连通分量
• 定理：图 $G = (V, E)$ 是哈密顿图，则 G 是强连通的
• 推论：奇阶二部图是非哈密顿图

充分条件

• 定理：对至少有三个点的简单图 $G = (V, E)$，若 $\delta(G) \ge |V| / 2$，则 G 是哈密顿图
• 定理：对 n 阶简单图 $G = (V, E)$，$n \ge 3$，若对任意不相邻的 $u,v \in V$，有 $d(u) + d(v) \ge n$，则 G 是哈密顿图

有向图的情况

• D 是强连通简单图，若对 D 中任意不相邻的 $u,v \in V$，均有 $d_{D}(u) + d_{D}(v) \ge 2|V| + 1$，则 D 是哈密顿图
• D 是简单图，若对 D 中任意不相邻的 $u,v \in V$，要么 $d_{D}^{+}(u) + d_{D}^{-}(v) \ge |V|$，要么 $(u,v) \in E$， 则 D 是哈密顿图
• D 是强连通简单图，若对 D 中任意$v \in V$，均有 $d_{D}(v) \ge |V|$，则 D 是哈密顿图
• D 是简单图，若$\min(\delta^{+}(D), \delta^{-}(D)) \ge |V|/2 > 1$，则 D 是哈密顿图
• 强连通竞赛图是哈密顿图
• 竞赛图有哈密顿路

---