欧拉图与哈密顿图

欧拉图¶

定义¶

欧拉图存在欧拉闭迹，半欧拉图只存在欧拉迹

若能遍历完所有的边但是没法回到起始点，称为非欧拉图但是有欧拉迹

欧拉图¶

假定 $G$ 是一个连通图，且是欧拉图，则下列命题等价：

$G$ 是欧拉图
$G$ 的每个点的度数是偶数
$G$ 的边集能划分为边不重的圈的并
（ $G$ 存在欧拉闭迹）

半欧拉图¶

假定 $G$ 是一个连通图，且是半欧拉图，则下列命题等价：

$G$ 是半欧拉图
$G$ 有且仅有 2 个点的度数是奇数
（ $G$ 存在欧拉迹）

小结论 💡¶

当 $n$ 满足什么条件时，完全图 $K_{n}$ 是欧拉图？ $n$ 为奇数
当 $n$ 满足什么条件时， $n$ 方体 $Q_{n}$ 是欧拉图？ $n$ 为偶数
若完全二部图 $K_{a, b}$ 为欧拉图， $a$ 和 $b$ 需满足什么条件？ $a, b$ 均为偶数
假设图 $G$ 恰好有两个连通分支，并且每个连通分支都是欧拉图，若要将 $G$ 变为欧拉图，最少需要添加几条边？ 最少需要添加 2 条边
欧拉图、半欧拉图是否存在割边？ 欧拉图不存在割边，半欧拉图存在割边

Fleury 算法¶

弗勒里算法解决了在欧拉图中求出一条具体欧拉环游的方法，核心思想是尽可能避割边行走

算法流程¶

（1）任意选取一个顶点 $v_{0}$ ，置 $w_{0} = v_{0}$ ；
（2）假设迹 $w_{i} = v_{0} e_{1} v_{1} \dots e_{i} v_{i}$ 已经确定，按如下方法从 $E - {e_{1}, e_{2}, \dots, e_{i}}$ 选一个 $e_{i + 1}$ ：
$e_{i + 1}$ 与 $v_{i}$ 相关联；
除非没有其他边可选，否则 $e_{i + 1}$ 不能是 $G_{i} = G - {e_{1}, e_{2}, \dots, e_{i}}$ 的割边；
（3）若（2）无法进行则算法停止

利用 Fluery 算法可以求一个半欧拉图的欧拉迹，半欧拉图有且仅有 2 个奇度顶点 $u, v$ ，在这 2 个点之间增加一条边 $m$ ，就可以得到一个欧拉图，然后从其中一个奇度顶点，例如 $u$ ，开始求欧拉环游。得到的欧拉环游去掉 $m$ 就是从 $u$ 到 $v$ 的欧拉迹。

欧拉图中扩展欧拉环游充要条件¶

设 $G$ 是非平凡的欧拉图，且 $v \in V (G)$ ，则 $G$ 的每条具有起点 $v$ 的迹都能扩展成 $G$ 的欧拉环游当且仅当 $G - v$ 是森林。

中国邮递员问题¶

1962，中国数学家管梅谷提出并解决了“中国邮路问题”

即最优环游问题：在一个连通具有非负权的赋权图 $G$ 中找到一条包含每条边（允许重复）且边权之和最小的闭途径，称之为最优(欧拉)环游

若图 $G$ 是一个欧拉图，则找出 $G$ 的欧拉环游即可
对一般图，其解法为：添加重复边以使 $G$ 成为欧拉图 $G^{*}$ ，并使添加的重复边的边权之和为最小，再求 $G^{*}$ 的欧拉回路

管梅谷的结论：

假定 $G^{*}$ 是在图 $G$ 中添加一些重复边得到的欧拉图，则 $G^{*}$ 具有最小权值的充要条件是：

$G$ 的每一条边最多被添加一次
对于 $G^{*}$ 的每个圈来说，该圈新添加的边的总权值不超过该圈总权值的一半

证明：必要性

若 $G$ 中某条边在 $G^{*}$ 中被添加的次数超过 1，则去掉其中两条重复的边，我们将得到一个总权值更小，且以 $G$ 为生成子图的欧拉图

上述与 “ $G^{*}$ 总权值最小” 相矛盾，因此每条边最多被添加一次

假定在 $G^{*}$ 中存在某个圈使得该圈新添加的边的总权值大于该圈权值的一半，不妨设为 $C$

那么在 $G^{*}$ 中，将 $C$ 上新添加的边全部去掉，然后将原圈未添加新边的边都添加一条重复边

这样的操作使得该圈所有点的度数不变或改变 2，相应的图仍然是欧拉图，但是权值更小，这与 “ $G^{*}$ 总权值最小” 相矛盾

Abstract

这个必要性的证明给出了最优欧拉环游的构造方法

半欧拉图最优欧拉环游¶

一个非负权的边赋权图 $G$ 中只有两个奇度顶点 $u$ 与 $v$ , 设计一个求其最优欧拉环游的算法如下：

(1) 在 $u$ 与 $v$ 间求出一条最短路 $P$ ； (最短路算法)
(2) 在最短路 $P$ 上，给每条边添加一条重复边得 $G$ 的欧拉图 $G^{*}$ ；
(3) 在 $G$ 的欧拉图 $G^{*}$ 中用 Fleury 算法求出一条欧拉环游；

证明

设 $u$ 与 $v$ 是 $G$ 的两个奇度顶点， $G^{*}$ 是 $G$ 的任意一个欧拉图。

考虑 $G^{*} [E^{*} - E]$ ，显然它只有两个奇数顶点 $u$ 与 $v$ ，当然它们必须在 $G^{*} [E^{*} - E]$ 的同一个分支中，因此，存在 $(u, v)$ 路 $P^{*}$ ：

\sum_{e \in E^{*} - E} w (e) \geq w (P^{*}) \geq w (P)

哈密顿图¶

定义¶

哈姆顿图¶

如果经过图 $G$ 的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称 $H$ 图。所经过的闭途径是 $G$ 的一个生成圈，称为 $G$ 的哈密尔顿圈，简称 $H$ 圈

半哈密顿图¶

不需回到出发点

如果存在经过 $G$ 的每个顶点恰好一次的路，称这样的图为半哈密尔顿图，称该路为 $G$ 的哈密尔顿路，简称 $H$ 路

小结论 💡¶

当 $n \geq 3$ 时，完全图 $K_{n}$ 是否为哈密尔顿图？是
当 $n \geq 2$ 时，方体 $Q_{n}$ 是否为哈密尔顿图？是
若完全二部图 $K_{a, b}$ 为哈密尔顿图， $a$ 和 $b$ 需满足什么条件？ $\Rightarrow a = b \geq 2$ ！
是否存在一个具有奇数个顶点的连通图，它既是二部图，也是哈密尔顿图？ 不存在，否则二部图中出现了奇圈
若二部图是哈密尔顿图，则它的二部划分 $(X, Y)$ 满足什么条件？ $\Rightarrow | X | = | Y |$ ！

哈密顿图目前为止没有充要条件，实际上图的 $H$ 性判定是 NP-困难问题，下面介绍一个必要条件和一些充分条件

必要条件¶

若 $G$ 是 $H$ 图，则对于 $V$ 的每个非空真子集 $S$ ，均有：

ω (G - S) \leq | S |

Info

💡 别忘了 $ω (. . .)$ 的意思是连通分支数，这里还容易得到 $H$ 图不存在割点。

只是必要条件而不是充分条件，经典例子——彼得森图

用于判断非 $H$ 图： $\exists S \subset V, ω (G - S) > | S |$ ，则 $G$ 不是 $H$ 图。

充分条件¶

Dirac¶

对于 $n \geq 3$ 的简单图 $G$ , 如果 $G$ 中有：

δ (G) \geq \frac{n}{2}

那么 $G$ 是 $H$ 图。

Ore¶

对于 $n \geq 3$ 的单图 $G$ , 如果 $G$ 中的任意两个不相邻顶点 $u$ 与 $v$ ，有：

d (u) + d (v) \geq n

那么 $G$ 是 $H$ 图。

Abstract

该定理证明和 Dirac 定理可以完全一致！

该定理的条件是紧的。例如：设 $G$ 是由 $Κ_{k + 1}$ 的一个顶点和另一个 $Κ_{k + 1}$ 的一个顶点重合得到的图，那么对于 $G$ 的任意两个不相邻顶点 $u$ 与 $v$ ，有：

d (u) + d (v) = 2 k = n - 1

但 $G$ 是非 $H$ 图。

Bondy¶

引理¶

对于单图 $G$ ，如果 $G$ 中有两个不相邻顶点 $u$ 与 $v$ ，满足： $d (u) + d (v) \geq n$ ，那么 $G$ 是 $H$ 图当且仅当 $G + u v$ 是 $H$ 图。

闭图¶

在 $n$ 阶简单图中，若对 $d (u) + d (v) \geq n$ 的任意一对顶点 $u$ 与 $v$ ，均有 $u adj v$ ，则称 $G$ 是闭图。

引理¶

若 $G_{1}$ 和 $G_{2}$ 是同一个点集 $V$ 的两个闭图，则 $G_{1} \cap G_{2}$ 是闭图，但 $G_{1} \cup G_{2}$ 不一定是闭图。

闭包¶

称 $\overset{―}{G}$ 是图 $G$ 的闭包，如果它是包含 $G$ 的极小闭图，即对 $\forall H$ ，若有 $G \subseteq H \subset \overset{―}{G}$ ，则 $H$ 不是闭图。

如果 $G$ 本身是闭图，则其闭包是它本身；
否则由定义可以通过在度和 $\geq n$ 的不相邻顶点对间加边来构造 $G$ 的闭图；加边之后还要继续检查是否需要加边。

图 $G$ 的闭包是唯一的。

闭包定理¶

由闭包定理也可以推出 Dirac 和 Ore 定理

图 $G$ 是 $H$ 图当且仅当它的闭包是 $H$ 图

Chavatal¶

度序列判定法

$H$ 图充分条件

设简单图 $G$ 的度序列是 $d (d_{1}, d_{2}, \dots, d_{n})$ ，这里， $d_{1} \leq d_{2} \leq \dots \leq d_{n}$ ，并且 $n \geq 3$ 。若对任意的 $m < \frac{n}{2}$ ：

或有 $d_{m} > m$ ；
或有 $d_{n - m} \geq n - m$ ；

则 $G$ 是 $H$ 图。（ $G$ 的闭包是完全图！证明也是证明这个）

TSP¶

边交换¶

最优 H 圈下界¶

可以通过如下方法求出最优 $H$ 圈的一个下界：(不是下确界，不一定达得到！)

(1) 在 $G$ 中删掉一点 $v$ (任意的)得图 $G_{1}$ ；

(2) 在图 $G_{1}$ 中求出一棵最小生成树 $T$ ；

(3) 在 $v$ 的关联边中选出两条权值最小者 $e_{1}$ 与 $e_{2}$ ；

若 $H$ 是 $G$ 的最优圈，则有权值下界：

W (H) \geq W (T) + W (e_{1}) + W (e_{2})