# 欧拉图

# 定义

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

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

# 欧拉图

假定 $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_0e_1v_1\cdots e_iv_i$ 已经确定，按如下方法从 $E-\{e_1,e_2,\cdots,e_{i}\}$ 选一个 $e_{i+1}$：
  • $e_{i+1}$ 与 $v_i$ 相关联；
  • 除非没有其他边可选，否则 $e_{i+1}$ 不能是 $G_i=G-\{e_1,e_2,\cdots,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^*$ 总权值最小” 相矛盾

# 半欧拉图最优欧拉环游

一个非负权的边赋权图 $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\geq3$ 时，完全图 $K_n$ 是否为哈密尔顿图？ 是
• 当 $n\geq2$ 时， 方体 $Q_n$ 是否为哈密尔顿图？ 是
• 若完全二部图 $K_{a,b}$ 为哈密尔顿图，$a$ 和 $b$ 需满足什么条件？$\Rightarrow a=b\geq2$！
• 是否存在一个具有奇数个顶点的连通图，它既是二部图，也是哈密尔顿图？ 不存在，否则二部图中出现了奇圈
• 若二部图是哈密尔顿图，则它的二部划分 $(X,Y)$ 满足什么条件？$\Rightarrow|X|=|Y|$！

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

# 必要条件

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

$$\omega(G-S)\leq|S|$$

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

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

# 充分条件

# Dirac

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

$$\delta(G)\geq\frac{n}{2}$$

那么 $G$ 是 $H$ 图。

# Ore

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

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

那么 $G$ 是 $H$ 图。

# Bondy

# 引理

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

# 闭图

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

# 引理

若 $G_1$ 和 $G_2$ 是同一个点集 $V$ 的两个闭图，则 $G_1\cap G_2$ 是闭图，但 $G_1\cup G_2$ 不一定是闭图。

# 闭包

称 $\overline G$ 是图 $G$ 的闭包，如果它是包含 $G$ 的极小闭图，即对 $∀H$，若有 $G\subseteq H \subset\overline G$，则 $H$ 不是闭图。

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

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

# 闭包定理

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

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

# Chavatal

度序列判定法

$H$ 图充分条件

设简单图 $G$ 的度序列是 $d(d_1,d_2,\cdots,d_n)$，这里，$d_1≤d_2≤⋯≤d_n$，并且 $n≥3$。若对任意的 $m<\frac{n}{2}$：

• 或有 $d_m>m$；
• 或有 $d_{n-m}≥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)$$