# Euler 图

# Euler 路 Euler 圈 Euler 图

设 G ＝ (V, E) 是连通的、无孤立点的图。

Euler 路是一条简单路 P，路 P 穿过图 G 中每条边一次且仅一次；
Euler 圈是一条简单圈 C，圈 C 穿过图 G 中每条边一次且仅一次；
含有 Euler 圈的图 G 称为 Euler 图 (简称为 E - 图)。

# Euler 定理

设 G ＝ (V,E) 是无孤立点的无向图。那么，
G 是 Euler 图 $\iff$ G 是连通的且 G 中无奇结点。

G 中无奇结点即是 G 中每个结点都是偶结点

# Euler 定理二

设 G＝(V,E) 是无孤立点的无向图。那么，
G 中有 Euler 路 $\iff$ G 是连通的且 G 中恰有两个奇结点。

# 割边 (cut edge)

设 G＝(V,E) 是无向图， $e\in E$ 。若 W (G\e)>W (G)，则称边 e 为图 G 的割边。
这里 W (G) 表示图 G 中的连通支数。

# Fleury 算法

寻找在两个奇结点间的一条 Euler 路的算法

从一个奇结点出发，每走一边标记一边；下次不走标记过的边；
在走边的过程中，除非割边 (cut edge) 割边 (cut edge) 没有其它选择时才走割边

# 定理 2

设 G＝(V,E) 是无孤立点的有向图。那么，
G 是 Euler 图 $\iff$ G 是连通的且 G 中每个结点的出度都等于进度。

# 定理 3

设 G＝(V,E) 是无孤立点的有向图。那么，
G 中有 Euler 路 $\iff$ G 是连通的且 G 中除两个结点外，其余每个结点的出度都等于进度。而这两个结点：一个结点的进度比出度大 1 (终点)，另一个结点的出度比进度大 1 (起点)。

# 应用

# 应用一：高效率计算机磁鼓的设计。

计算机旋转磁鼓的表面被等分成 $2^n$ 个部分，与 n 个电刷相接触。绝缘体 (空白部分) 不通电表示信号 0；导体 (阴影部分) 通电表示信号 1。从而 n 个电刷上就产生一 n 位二进制信号。
问题：如何合理的按排磁鼓表面上的空白与阴影部分，使得磁鼓转动 n 个位置，就可读出 $2^n$ 个不同的二进制数。

# 应用二：一笔画问题

对于一个给定的图，究竟需要多少笔才能画成？这里只讨论连通图的一笔画问题。因为假若一个图是不连通的，则此图的笔画问题就可以归结成对各连通支笔画的讨论。
连通图的笔画是由图中奇结点的个数决定的。
本章 §2 定理 2 已经证明过：图中奇结点的个数是偶数。所以奇结点是成对出现的，即为 2k 个。

当 k=0,1 时，此连通图是一笔画的；
当 k>1 时，此连通图是 k 笔画的 (更进一步地，存在着 k 条边不重的路)。

# 应用三：中国邮路问题

一个邮递员，每次送信，领取邮件，由邮局出发，要走遍他所负责的投递范围内的每一条街道，完成投递任务后，再返回邮局。
问题是：他应该沿着怎样的路线走，使所走的总路程最短？
这个问题抽象成图论语言就是：在给定的一个连通的带权图 $G=(V,E,w)$ (每条边上一个非负的权 $w(e)$ ) 中，要求解一个圈 $C$ ，过每条边至少一次，并使圈 C 上的总权和 $w(C)$ 达到最小。

当 $k=0$ 时 (即无奇结点)，这时 $G$ 是 Euler 图，有 Euler 圈，设其为 $C$ 。显然，若按 Euler 圈 C 走，每条边走且仅走一次，总权和 $w (C)$ 显然是最小的；
当 $k\geqslant 1$ 时 (即有奇结点)，解决问题的思路是给图 $G$ 增加一些重复边，
使其变成无奇结点的多重图 $G'$ 。由于图 $G$ 是连通的，故图 $G'$ 也是连通的。因而根据 Euler 定理可知，图 $G'$ 必有 Euler 圈，设其为 $C$ 。
现在由于圈 $C$ 穿过图 $G'$ 中的每条边一次且仅一次，因而 C 必定穿过图 G 中的每条边一次。而图 G 中各边的总权和 w (E) 是固定不变的，所以要使
Euler 圈 C 取得最小权值 $w(C)$
$\iff$ 平行边集 $E_1'$ 取得最小权值 $w(E_1')$
$\iff$ 边集 $E_1$ 取得最小权值 $w(E_1)$
因而，中国邮路问题就转化为：在一给定的带权图 $G=(V,E,w)$ 中，寻求这样一个边集 $E_1\subseteq E$ ，其对应的平行边集为 $E_1'$ ，使带权多重图 $G'= G\cup E_1'$ 无奇结点，并使 $\displaystyle w(E_1)=\sum_{e\in E_1} w(e)$ 达到最小。
称这样的边集 $E_1$ 是最优的。

# 定理 4.(管氏定理 (1962))

E1 是最优的
$\iff$ 在图 G 的每个初级圈 $C_i$ 上，都有 $E_1$ 的边 (要重复的边) 的长度之和不超过圈长的一半
$\iff$ 在图 G 的每个初级圈 Ci 上 $\displaystyle \sum_{e\in E_1\cap C_i} w(e)\leqslant \frac{1}{2}\sum_{e\in \cap C_i} w(e)$

定理的证明主要基于以下两点：

当某条边重复 $k(k\geqslant 2)$ 次后得到的图为 Euler 图时，则此边重复 $k(k\geqslant 2)$ 次得到的图也一定 Euler 图。
在图 G 的一个初级圈上，如果将原来的重复边都删去，而在原来没有重复边的边上都加上一条重复边，那么图中各结点的度数改变 0 或 2，所以，这种做法不会改变图 G 是 Euler 图的性质。由此可知：当 Euler 圈中重复边的长度之和超过此圈总长的一半时，如作上述改变，则重复边长度之和减少，而 Euler 圈的性质不变

# Hamilton 图

# Hamilton 图的引出及其定义

Hamilton 图是由威廉哈密顿 (Sir Willian Hamilton) 爵士于 1856 年在解决关于正十二面体的一个数学游戏时首次提出的。
Hamilton 爵士在 1859 年给他的朋友 Graves 的信中，将他的正十二面体数学游戏重新叙述为：
能否在全球选定的二十个都会城市 (据说有中国三个城市：北京、上海、西安) 中，从任一城市出发，作全球航行，经过这二十个城市一次且仅一次 (不能去其它城市)，然后回到出发点？这就是著名的环球航行问题或周游世界问题。

# Hamilton 路圈图

设 G＝(V,E) 是简单图。则

H - 路是一条初级路，它穿过图中每个结点一次且仅一次；
H - 圈是一条初级圈，它穿过图中每个结点一次且仅一次；
H - 图是含有 H - 圈的图

# 定理 1.(必要性定理)

设 G＝(V,E) 是简单无向图。则 G 是 H 图 $\implies (\forall S\subseteq V)(S\ne\varnothing \implies w(G \setminus S)\leqslant|S|)$ 。
其中： $w(G')$ 表示图 $G'$ 的连通支数 (分图个数)。

# 定理 2.(D.KÖnig 定理 (充分性定理))

设 G＝(V, E) 是简单无向图，且 $|V|=n$ 。则
对任意一对结点 $u,v\in V$ ，均有 $deg(u)+deg(v)\geqslant n-1$
$\implies$ G 中必有一条 H - 路

König 算法的操作实际上是三步

任走出一条初级路 P ，并延伸到尽头；

“改” 初级路 P 为初级圈 C；

改初级圈 C 为初级路 P (新)，并延伸到尽头；路长至少增 1

# 定理 3.(D.KÖnig 定理 (充分性定理))

设 G＝(V, E) 是简单无向图，且 $|V|=n$ 。则
对任意一对结点 $u,v\in V$ ，均有 $deg(u)+deg(v)\geqslant n\\\implies G$ 必是 H - 图。

# 推论 1.(G.A.Dirac 定理 (1952) (充分性定理))

设 G＝(V, E) 是简单无向图，且 $|V|=n$ 。则
对任意一对结点 $v\in V$ ，均有 $deg(v)\geqslant \frac{n}{2}$ ,
$\implies G$ 必是 H - 图。

# 定理 4.(充分性定理)

设 G＝(V, E) 是简单无向图，且 $|V|=n， |E|=m$ 。则
$m\geqslant \frac{1}{2}(n-1)(n-2)+2$
$\implies G$ 必是 H - 图。

# 图的闭包 (closure)

一个简单无向图 $G=(V,E)(|V|=n)$ 的闭包是一个图 $G^c=(V,E^c)$ 。其中：边集 $E^c$ 的定义如下

$E^c:=E\\ E^c:=E^c\cup\{(u,v)|(u,v)\notin E^c\land deg_{G^c}(u)+deg_{G^c}(v)\geqslant n\}$

# Bondy 及 Chvatal 定理 (1969)

简单无向图 G 是 H - 图 $\iff$ 图 G 的闭包 $G^c$ 是 H - 图。

# 竞赛图 (race-graph)

无向完全图的定向图称为竞赛图。

竞赛图中任何两个结点间都有且仅有一条有向边。

# Redei(1934)

设 G=(V,E) 是竞赛图，且 | V|=n 则
竞赛图 G 中必存在着一条有向 H - 路。