图论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 是哈密顿图
  • 强连通竞赛图是哈密顿图
  • 竞赛图有哈密顿路

Share