第四章 欧拉图与哈密尔顿图

4.1 欧拉图

★欧拉图的定义

欧拉图

对连通图 $G$, 若 $G$ 中存在经过每条边的闭迹, 则称 $G$ 为欧拉图 (Eulerian graph, König 在专著中首次给出).

欧拉闭迹又称为欧拉环游 (Eulerian circuit).

半欧拉图

若非欧拉图 $G$ 存在欧拉迹, 则称为半欧拉图 (semi-Eulerian graph).

欧拉图的性质

★定理

下列陈述对于非平凡连通图 $G$ 是等价的:

• (1) $G$ 是欧拉图;

• (2) $G$ 的每个顶点的度均为偶数;

• (3) $G$ 的边集能划分为边不交圈的并.

证明:

(1)→(2)

由 (1), 设 $C$ 是欧拉图 $G$ 的任一欧拉环游, $v$ 是 $G$ 中任意顶点, $v$ 在环游中每出现一次, 意味在 $G$ 中有两条不同边与 $v$ 关联, 所以, 在 $G$ 中与 $v$ 关联的边数为偶数, 即 $v$ 的度数为偶数, 由 $v$ 的任意性, 即证明 (2).

(2)→(3) [Veblen Theorem, 1912/13, Annals of Mathematics]

由于 $G$ 是连通非平凡的且每个顶点度数为偶数, 所以 $G$ 中至少存在圈 $C_1$, 从 $G$ 中去掉 $C_1$ 中的边, 得到 $G$ 的生成子图 $G_1$, 若 $G_1$ 没有边, 则 (3) 成立. 否则, $G_1$ 的每个非平凡分支是度数为偶数的连通图, 于是又可以抽取一个圈. 反复这样抽取, $E(G)$ 最终划分为若干圈.

(3)→(1)

设 $C_1$ 是 $G$ 的边划分中的唯一的圈. 若 $G$ 仅由此圈组成, 则 $G$ 显然是欧拉图.

否则, 由于 $G$ 连通, 所以, 必然存在圈 $C_2$, 它和 $C_1$ 有公共顶点. 于是, $C_1\cup C_2$ 是一条含有 $C_1$ 与 $C_2$ 的边的欧拉闭迹, 如此拼接下去, 得到包含 $G$ 的所有边的一条欧拉闭迹. 即证 $G$ 是欧拉图.

推论1

连通图 $G$ 是欧拉图当且仅当 $G$ 的所有顶点度为偶数.

★推论2

连通图 $G$ 是半欧拉图当且仅当 $G$ 中恰有两个顶点度数为奇数.

例

下面图中哪个是欧拉图？非欧拉图但存在欧拉迹？非欧拉图且不存在欧拉迹？

解: $G_1$ 是欧拉图; $G_2$ 是非欧拉图, 但存在欧拉迹; $G_3$ 中不存在欧拉迹.

练习

(1) $n=?$ 时, 完全图 $K_n$ 是欧拉图;
(2) $n=?$ 时, 超立方图 $Q_n$ 是欧拉图;
(3) $m,n=?$ 时, $K_{m,n}$ 是欧拉图.

解:
(1) $K_n$ 每个顶点的度均为 $n-1$, $n$ 为大于等于 $2$ 的奇数时, $n-1$ 为偶数;
(2) $Q_n$ 是 $n$ 正则图, $n$ 为大于等于 $2$ 的偶数时, 每个顶点的度均为偶数;
(3) $m,n$ 都是偶数时, $K_{m,n}$ 每个顶点的度均为偶数.

例

求证: 若 $G$ 和 $H$ 是欧拉图, 则 $G\square H$ 是欧拉图.

证明: 由 Cartesian Product 的定义易知对任意 $u\in V(G),v\in V(H)$, 有: $d(u)+d(v)=d((u,v))$.

又 $G,H$ 是欧拉图, 所以 $G\square H$ 每个顶点的度均为偶数.

下面证明: $G\square H$ 是连通的.

由于 $G,H$ 都是欧拉图, 所以都连通. 设最短的 $u_1,u_2$ 路, 最短的 $v_1,v_2$ 路分别为:

$$u_1{x}_1{x}_2\cdots x_k{u}_2,v_1{y}_1{y}_2\cdots y_m{v}_2$$

那么, 由乘积图的定义: $\forall (u_1,v_1),(u_2,v_2)\in V(G\square H)$, 在乘积图中有路:

$$(u_1,v_1)(x_1,v_1)\cdots (x_k,v_1)(u_2,v_1)(u_2,y_1)\cdots (u_2,y_m)(u_2,v_2)$$

这样, 我们证明了 $G\square H$ 是连通的且每个顶点的度均为偶数. 即它是欧拉图.

Fleury 算法

该算法解决了在欧拉图中求出一条具体欧拉环游的方法. 方法是尽可能避割边行走.

Fleury 算法 (1883)

(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}$:

• 1) $e_{i+1}$ 与 $v_i$ 相关联.

• 2) 除非没有别的边可选择, 否则 $e_{i+1}$ 不能是 $G_i=G-\{e_1,e_2,\dots ,e_i\}$ 的割边. (避割边)

(3) 当 (2) 不能执行时, 算法停止.

例

在下面欧拉图 $G$ 中求一条欧拉环游.

解: 欧拉环游为 $adfhjihcfbgcegdbea$.

例

某博物馆的一层布置如下图, 其中边代表走廊, 顶点 $e$ 是入口, 顶点 $g$ 是礼品店,可以通过 $g$ 离开博物馆. 请找出从博物馆 $e$ 进入, 经过每个走廊恰好一次, 最后从 $g$ 处离开的路线.

解: 图中只有两个奇度点 $e$ 和 $g$, 因此存在起点为 $e$, 终点为 $g$ 的欧拉迹.

为了在 $G$ 中求出一条起点为 $e$, 终点为 $g$ 的欧拉迹, 在 $e$ 和 $g$ 间添加一条平行边 $m$.

用 Fleury 算法求出欧拉环游为: $gcfabchbdhgdjiejge$.

所以解为 $egjeijdghdbhcbafcg$.

例

证明: 若 $G$ 有 $2k>0$ 个奇度点, 则存在 $k$ 条边不重的迹 $Q_1,Q_2,\dots ,Q_k$, 使得

$$E(G)=E(Q_1)\cup E(Q_2)\cup \cdots \cup E(Q_k)$$

(回忆树中有类似结论, 习题2.4)

证明: 不失一般性, 只就 $G$ 是连通图进行证明.

设 $G=(n,m)$ 是连通图. 令 $v_1,v_2,\dots ,v_k,v_{k+1},\dots ,v_{2k}$ 是 $G$ 的所有奇度点.

在 $v_i$ 与 $v_{i+k}$ 间连新边 $e_i$ 得图 $G^{\ast }(1\le i\le k)$. 则 $G^{\ast }$ 是欧拉图, 因此, 由 Fleury 算法得欧拉环游 $C$.

在 $C$ 中删去 $e_i(1\le i\le k)$, 得 $k$ 条边不重的迹 $Q_i(1\le i\le k)$. 所以

$$E(G)=E(Q_1)\cup E(Q_2)\cup \cdots \cup E(Q_k)$$

4.2 ★中国邮递员问题

中国邮递员问题

(管梅谷, 1962) 一名邮递员从邮局出发派发邮件,要经过他所管辖区域的每一条街道最后返回邮局(每条街道可以经过不止一次). 如何安排路线, 才能使邮递员走过的总路程最短呢?

• 邮路图是欧拉图, 那么由 Fleury 算法, 可得到行走路线.
• 邮路图不是欧拉图, 如何重复行走街道才能使行走总路程最短?

定理: 管梅谷的结论

若 $W$ 是包含图 $G$ 的每条边至少一次的闭途径, 则 $W$ 具有最小权值当且仅当下列两个条件被满足:

• (1) $G$ 的每条边在 $W$ 中最多重复一次;

• (2) 对于 $G$ 的每个圈上的边来说, 在 $W$ 中重复的边的总权值不超过该圈非重复边总权值.

证明:

“必要性”

首先, 设 $G$ 是连通非欧拉图, $u$ 与 $v$ 是 $G$ 的两个奇度顶点, 把连接 $u$ 与 $v$ 的路上的边改为 $2$ 重边, 则路中的点的度数奇偶性没有改变, 仍然为偶数, 但 $u$ 与 $v$ 的度数由奇数变成了偶数. 如果对 $G$ 中每对奇度点都如此处理, 则最终得到的图为欧拉图. 设该图为 $G_1$.

其次, 对 $G_1$ 作修改: 如果在 $G_1$ 中, 边 $e$ 重复数大于 $2$, 则在 $G_1$ 中删掉 $2$ 条重复的 $e$ 边后, 所得之图仍然是包含 $G$ 的欧拉图. 在 $G_1$ 中, 对每组平行边都做上面的处理, 最后得到一个重复边数最多为 $1$ 的包含 $G$ 的欧拉图 $G_2$.

这说明, 若 $W$ 是包含 $G$ 的所有边的欧拉环游, 则 $G$ 中每条边至多在 $W$ 里出现两次. 这就证明了 (1).

又设 $C$ 是 $G_2$ 中任意一个圈, 在该圈中, 如果重复边的总权值超过该圈中非重复边总权值, 那么可以把该圈中平行边改为非平行边, 而把非平行边改为平行边, 如此修改, 得到的图仍然是包含 $G$ 的欧拉图, 但对应的欧拉环游长度减小了.

这就是说, 只要对 $G_2$ 的每个圈都作上面的修改, 最后得到的图仍然为包含 $G$ 的欧拉图, 而最后的图正好满足 (2).

“充分性” (略)

例

求下图 $G$ 的一个最优欧拉环游.

解: 由定理:

在两个奇度点之间加一条平行边.

不断寻找这样的圈: 重复边的总权值超过该圈中非重复边总权值, 那么可以把该圈中平行边改为非平行边, 而把非平行边改为平行边. 直到不存在这样的圈.

例

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

解:

1. 算法
(1) 在 $u$ 与 $v$ 间求出一条最短路 $P$; (最短路算法)
(2) 在最短路 $P$ 上, 给每条边添加一条平行边得 $G$ 的欧拉图 $G^{\ast }$;
(3) 在 $G$ 的欧拉图 $G^{\ast }$ 中用 Fleury 算法求出一条欧拉环游.

2. 算法证明 (证明算法求出的欧拉环游是最优的)
证明: 设 $u$ 与 $v$ 是 $G$ 的两个奇度顶点, $G^{\ast }$ 是在 $G$ 上添加重复边的基础上得到的任意一个欧拉图.
考虑 $G^{\ast }[E^{\ast }-E]$, 显然它只有两个奇度点 $u$ 与 $v$, 当然它们必须在 $G^{\ast }[E^{\ast }-E]$ 的同一个分支中, 因此, 存在 $(u,v)$ 路 $P^{\ast }$.
所以, ${\sum }_{e\in E^{\ast }-E}w(e)\ge w(P^{\ast })\ge w(P)$.
即证.

例

求下图的一条最优欧拉环游.

解:

最优欧拉环游: $xuywvzwyxuwvxzyx$.

中国邮递员问题的一个应用

在倡导节能减排的当下, 平时马路上的洒水车、铲雪车, 还有马路清扫怎么规划行车路线, 才能使得最节省能源呢?

实际上, 这类问题都可以转化为中国邮递员问题, 而Edmonds已经在1973年给出了中国邮递员问题的有效解法。

加拿大多伦多基于中国邮递员问题的算法对铲雪线路进行规划后, 铲雪费用比之前减少了三分之一, 每年节省了大约300万美元(约合2千万人民币).

4.3 哈密尔顿图

★哈密尔顿图的概念

哈密尔顿图, 哈密尔顿圈

图 $G$ 中存在经过每个顶点恰好一次的圈, 称 $G$ 为哈密尔顿图 (Hamiltonian graph), 简称 H 图.

该圈是 $G$ 的一个生成圈, 称为 $G$ 的哈密尔顿圈 (Hamiltonian cycle), 简称 H 圈.

例

正十二面体是 H 图.

思考

(1) $n=?$ 时, 完全图 $K_n$ 是 H 图; 有多少个?
(2) $n=?$ 时, 超立方图 $Q_n$ 是 H 图; 如何具体给出来?
(3) 证明: 对 $Q_n$ 的任一个边子集 $F$ 满足 $|F|=n-2(n\ge 2)$, 则 $Q_n-F$ 仍然是 H 图; Hint: 数学归纳法.
(4) $a,b=?$ 时, $K_{a,b}$ 是 H 图.

解:

(1) $n\ge 3$ 时, 完全图 $K_n$ 是 H 图;
第一个点固定, $n$ 个点排序, 有 $(n-1)!$ 种, 去掉两个方向重复的, 结果为 $\frac{(n-1)!}{2}$ 个.

(2) $n\ge 2$ 时, 超立方图 $Q_n$ 是 H 图.

(3)

(4) $a=b\ge 2$ 时, $K_{a,b}$ 是 H 图.

练习

证明: 若 $G$ 和 $H$ 是哈密尔顿图, 则 $G\square H$ 是哈密尔顿图.

例

下图 $G$ 不是 H 图.

证明: 因为在 $G$ 中, 边 $uv$ 是割边, 所以它不在 $G$ 的任意圈上, 于是 $u$ 与 $v$ 不能在 $G$ 的同一个圈上. 故 $G$ 不存在包括所有顶点的圈, 即 $G$ 是非 H 图.

哈密尔顿路

如果存在经过 $G$ 的每个顶点的路, 称该路为 $G$ 的哈密尔顿路 (Hamiltonian path), 简称 H 路, 称 $G$ 为可迹的 (traceable).

例如下图 $G$ 有 H 路.

哈密尔顿图的性质

★定理: 哈密尔顿图的必要条件

若 $G$ 为 H 图, 则对 $V(G)$ 的任一非空顶点子集 $S$, 有: $\omega (G-S)\le |S|$.

证明: $G$ 是 H 图, 设 $C$ 是 $G$ 的 H 圈. 则对 $V(G)$ 的任意非空子集 $S$, 容易知道: $\omega (C-S)\le |S|$.

所以, 有: $\omega (G-S)\le \omega (C-S)\le |S|$.

注:

(1) 不等式为 H 图的必要不充分条件, 即不等式不满足时, 可断定对应图非 H 图; 满足不等式, 但不能确定图是 H 图.

(2) 有割点 (不是分离点) 的图必不是 H 图.

(3) 不等部的二部图必不是 H 图.

(4) 考虑通过加强必要条件可能会得到充分条件. 例如考虑 $|S|\ge 2\omega (G-S)$.

图的坚韧度

图 $G$ 是 $t$-坚韧的 ($t$-tough) 如果对于每一个非空点集 $S$ 有 $|S|\ge t\omega (G-S)$.

图 $G$ 的坚韧度 (toughness) 是使得 $G$ 是 $t$-坚韧的最大 $t$ 值.

H 图是 $1$-坚韧的; Petersen 图是 $4/3$-坚韧的.

Conjecture (Chvátal, 1973) 猜想: 存在 $t$ 使得每个 $t$-坚韧图都是 H 图.

已经证明 t→9/4 不成立. 求一般图的坚韧度是 NP-困难的.

例

求证下图不是 H 图.

证明: 取 $S=\{2,7,6\}$, 则有: $\omega (G-S)=4>|S|=3$

由定理知, $G$ 为非 H 图.

例

Petersen 图非 H, 但它满足定理的不等式.

此画法由 A. Kowalewski 于 1917 年给出, 称 Kowalewski 图.

但是Petersen给出的” Petersen图” 的初始样貌是这样的:

Kowalewski图与Petersen图的同构关系是由德国数学家Gerhard Kowalewski (1876-1950, 导师是Sophus Lie) 于1930首次发现.

事实上, Kempe于1886年就构造出了一个图同构于Petersen图.

A. Kowalewski发现:

Petersen 图的一种定义:

五个点有两个点是红色, 共有 10 种排列, 构成图的 10 个顶点. 若两个顶点没有红色顶点在同一位置, 则相连.

H 路的必要条件

已知下图没有 H 圈, 但有 H 路 (红色边). 类似于 H 圈的必要条件, 给出 H 路的必要条件:

命题: 若 $G$ 包含 H 路, 则对 $V(G)$ 的任一非空顶点子集 $S$, 有: $\omega (G-S)\le |S|+1$.

证明类似于 H 圈的必要条件的证明, 留作练习.

下图不满足存在 H 路的必要条件, 因此不存在 H 路.

例

一只老鼠吃 $3\ast 3\ast 3$ 立方体乳酪. 其方法是借助于打洞通过所有的 $27$ 个 $1\ast 1\ast 1$ 的子立方体. 如果它从一角上开始, 然后依次走向未吃的立方体, 问吃完时是否可以到达中心点？

解: 如果把每个子立方体模型为图的顶点, 且两个顶点连线当且仅当两个子立方体有共同面. 那么, 问题转化为问该图中是否存在一条由角点到中心点的H路.

如果起点作为坐标原点, 那么 $27$ 个子立方体可以编码为: $(1,1,1)$, $(1,1,2)$, $(1,1,3)$, $(1,2,1)$, $(1,2,2)$, $(1,2,3)$, $(1,3,1)$, $\dots$, $(3,3,3)$.

容易知道: $G$ 是二部图, 且如果 $(1,1,1)$ 在 $X$ 中, 则中心点 $(2,2,2)$ 必在 $Y$ 中. (类似于超立方的编码方式)

又容易知道: $|X|=14,|Y|=13$.

$G$ 中不存在由点 $(1,1,1)$ 到点 $(2,2,2)$ 的 H 路. 否则, 将 $(1,1,1)$ 和 $(2,2,2)$ 连线后得到的图 $G_1$ 有 H 圈.

但是, $G_1$ 不能是 H 图. 因为在 $G_1$ 中, 取 $S=Y$, 则可得到: $14=\omega (G_1-S)>|S|=13$.

故, 老鼠最后不能到达中心点.

注: 两个部集大小不等的二部图一定不是H图.

哈密尔顿图的判定

图的 H 性判定是 NP-完全问题. 到目前为止, 有关的定理有300+, 但没有一个是理想的 (充分必要的).

下面, 介绍几个著名的定理.

★Dirac 定理

(Dirac,1952)

(1) 对于 $n\ge 3$ 的简单图 $G$, 如果 $G$ 中有:

$$\delta (G)\ge n/2$$

那么, $G$ 是 H 图.

(2) 设 $G$ 是 $2$-连通的 $n\ge 3$ 阶图. 若 $G$ 的每个顶点的度都不小于 $k$, 则 $G$ 中包含一条长度至少为 $2k$ 的圈或 H 圈.

证明 (1): 若不然, 设 $G$ 是一个满足定理条件的极大非 H 简单图. 显然 $G$ 不能是完全图, 否则, $G$ 是 H 图.

为什么假设 $G$ 是极大非 H 图呢?

反证法其实就是证明逆否命题. 亦即证明: 若 $G$ 不是哈密尔顿图, 则 $G$ 不满足 Dirac 条件. 既然 $G$ 不是哈密尔顿图, 那任意一个非哈密尔顿图都可以, 为了方便选择一个极大的 (不会影响结论). 另一方面, 极大非哈密尔顿图可以通过非极大的加边而得到. (因此假设是合理的!)

显然 $G$ 不能是完全图, 否则, $G$ 是 H 图.

于是, 可以在 $G$ 中任意取两个不相邻顶点 $u$ 与 $v$. 考虑图 $G+uv$, 由 $G$ 的极大性, $G+uv$ 是 H 图. 且 $G+uv$ 的每一个 H 圈必然包含边 $uv$.

所以, 在 $G$ 中存在起点为 $u$ 而终点为 $v$ 的 H 路 $P$. (真正目的)

不失一般性, 设起点为 $u$ 而终点为 $v$ 的 H 路 $P$ 为:

$$P=v_1{v}_2\cdots v_n,u=v_1,v_n=v$$

令:

$$\begin{array}{rlr}S& =\{v_i|u{v}_{i+1}\in E(G)\},& i=1,2,\cdots ,n-1\\ T& =\{v_j|v_{j}v\in E(G)\},& j=1,2,\cdots ,n-1\end{array}$$

($S$ 中是与 $u$ 相连的点的上一个点, $T$ 中是与 $v$ 相连的点)

对于 $S$ 与 $T$, 显然, $v_n\notin S\cup T$. 所以: $|S\cup T|<n$.

若 $S\cap T\ne \varnothing$, 则 $\exists v_i\in S\cap T$ 使得 $u{v}_{i+1},v{v}_i\in E(G)$, 即这样在 $G$ 中有 H 圈, 与 $G$ 是极大非 H 图矛盾！

若设 $S\cap T=\varnothing$, 则有 $d(u)+d(v)=|S|+|T|=|S\cup T|+|S\cap T|<n$.

这与已知 $\delta (G)\ge n/2$ 矛盾! 定理得证.

(2) 的证明类似.

注: 该定理是 H 问题的划时代的奠基性成果.

★Ore 定理

(Ore, 1960) 对于 $n\ge 3$ 的简单图 $G$, 如果 $G$ 中的任意两个不相邻顶点 $u$ 与 $v$, 有:

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

那么, $G$ 是 H 图.

注:

(1) 该定理证明和 Dirac 定理基本相同;

(2) Ore 定理的条件比 Dirac 定理弱, 因此比 Dirac 定理的适用范围广(见下图);

(3) Dirac 定理和 Ore 定理的条件都是紧的 (sharp). 例如考虑 $K_1˅2(K_3)$.

图 $G$ 不满足 Dirac 定理 ($\delta (G)\ge \lfloor n/2\rfloor$ 但 $\delta (G)<n/2$) 和 Ore 定理的条件 ($7=V(G)>d(u)+d(v)=6$), 没有 H 圈. 这说明两个定理的条件都是紧的.

引理1

对于简单图 $G$, 如果 $G$ 中有两个不相邻顶点 $u$ 与 $v$, 满足:

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

那么 $G$ 是 H 图当且仅当 $G+uv$ 是 H 图.

证明: 略 (必要性显然, 充分性由 Ore 定理反证易得).

闭图与闭包 $c(G)$

在 $n$ 阶简单图中, 若对 $d(u)+d(v)\ge n$ 的任意一对顶点 $u$ 与 $v$, 均有 $u\leftrightarrow v$, 则称 $G$ 是闭图 (closed).

反复连接 $G$ 中度和不小于 $n$ 的不相邻顶点对, 直到没有这样的顶点对存在为止, 得到的图称作 $G$ 的闭包 (closure), 记作 $c(G)$.

注:

(1) 如果 $G$ 本身是闭图, 则其闭包是它本身; 如果 $G$ 不是闭图, 则可以通过在度和大于等于n的不相邻顶点对间加边来构造 $G$ 的闭包. 例如:

(2) 不是任意图的闭包都是完全图. 如 $C_5$.

引理2

图 $G$ 的闭包 $c(G)$ 是唯一的. (证明略)

★闭包定理 (Bondy-Chvátal, 1976)

1976年, John A. Bondy 和 Václav Chvátal 在 Ore 定理基础上, 得到图 $G$ 和它的闭包间有相同的哈密尔顿性.

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

证明: “必要性”显然.

“充分性”: 假设 $G$ 的闭包是 H 图, 我们证明 $G$ 是 H 图.

假设 $G$ 的闭包和 $G$ 相同, 结论显然.

若不然, 设 $e_i(1\le i\le k)$ 是为构造 $G$ 的闭包而添加的所有边, 由引理1, $G$ 是 H 图当且仅当 $G+e_1$ 是 H 图, $G+e_1$ 是 H 图当且仅当 $G+e_1+e_2$ 是 H 图, …, 反复应用引理1, 可以得到定理结论.

注: Though IF AND ONLY IF, it doesn’t help much!

推论

由于完全图一定是 H 图, 所以由闭包定理有:

设 $G$ 是 $n\ge 3$ 的简单图, 若 $G$ 的闭包是完全图, 则 $G$ 是 $H$ 图.

推论

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

设 $G$ 是 $n\ge 3$ 的简单图.

​ (1) 若 $\delta (G)\ge n/2$, 则 $G$ 是 H 图 (Dirac定理);

​ (2) 若对于 $G$ 中任意不相邻顶点 $u$ 与 $v$, 都有 $d(u)+d(v)\ge n$, 则 $G$ 是 H 图 (Ore定理).

★Chvátal 定理: 度序列判定法

在闭包定理的基础上, Chvátal 进一步得到图的 H 性的度序列判定法.

(Chvátal, 1972) 设简单图 $G$ 的度序列是 $(d_1,d_2,\dots ,d_n)$, 其中, $d_1\le d_2\le \dots \le d_n$, 并且 $n\ge 3$. 若对任意的 $1\le i<n/2$, 有 $d_i>i$, 或 $d_{n-i}\ge n-i$, 则 $G$ 是 H 图.

(等价表述) 设简单图 $G$ 的度序列是 $(d_1,d_2,\dots ,d_n)$, 其中, $d_1\le d_2\le \dots \le d_n$, 并且 $n\ge 3$. 若不存在 $1\le i<n/2$, 使得 $d_i\le i$ 并且 $d_{n-i}<n-i$, 则 $G$ 是 H 图.

证明:

增加边不会使得度序列中的数值减小, 并且闭包与原图的 $H$ 性相同, 故考虑 $G$ 的闭包. 我们将证明 $G$ 的闭包 $c(G)$ 是 $K_n$, 则 $G$ 是 H 图.

若不然, 设 $u$ 与 $v$ 是 $c(G)$ 中不相邻且度和最大的两点, 不妨设: $d(u)\le d(v)$.

由于 $c(G)$ 是闭图, $u$ 与 $v$ 不相邻, 所以: $d(u)+d(v)<n$.

于是, 若取 $i=d(u)$, 则 $i<n/2$.

对于 $i$, 由于: $d(v)<n-d(u)=n-i$.

此即: $d(v)\le (n-1)-i$.

所以在 $c(G)$ 中至少有 $i$ 个点与 $v$ 不邻接.

由 $u$ 与 $v$ 的取法知: 与 $v$ 不相邻的 $i$ 个点中, $u$ 的度数最大. 这就意味着: $c(G)$ 中至少有 $i$ 个点的度数不超过 $i(=d(u))$, 即: $d_i\le i$.

另一方面, 由 $i$ 的选取, $c(G)$ 中有 $n-1-i$ 个点与 $u$ 不相邻 (因 $d(u)=i$ 可知). 而这些点中, $v$ 的度最大. 这意味着: 在 $c(G)$ 中有 $n-1-i$ 个与 $u$ 不相邻的点 (度数不大于 $v$ 的度数).

但是, 由: $d(v)<n-d(u)=n-i$.

再由假设, $d(u)\le d(v)$, 从而加上 $u$ 点后, 在 $c(G)$ 中至少有 $n-i$ 个点的度数严格小于 $n-i$, 即: $d_{n-i}<n-i$.

矛盾, 因此定理成立.

注: 的条件是充分不必要的. 例如 $C_5$.

例

求证下图是 H 图.

证明: 在 $G$ 中有:

$$\begin{array}{r}{d}_1=d_2=d_3=3\\ d_4=d_5=5\\ d_6=6\\ d_7=7\\ d_8=d_9=8\end{array}$$

因 $n=9$, 所以, $i=1,2,3,4$, $n-i=8,7,6,5$.

$d_5=9-4=5,d_6=9-3=6,d_7=9-2=7,d_8=9-1=8$.

所以, 由度序列判定法, $G$ 是 H 图.

例

下图的闭包是完全图, 且容易看出该图是 H 图. 但无法用 Chvátal 定理判定.

练习

确定下图是否 H 图?

哈密尔顿图研究简介

哈密尔顿问题一直是图论的研究热点. 历史大致情况如下:

1. 1952年Dirac定理是研究的奠基性结果;
2. 1962年Ore定理是Dirac定理的重要推进;
3. 1972年Chvátal度序列定理以及下面独立数判定定理;
   定理 (Chvátal, Erdös[1972]) 若 $\kappa (G)\ge \alpha (G)$, 则简单图 $G$ 是 H 图除非 $G=K_2$.
4. 1976年Bondy-Chvátal定理是Ore定理的重要推进;
5. 1984年福州大学的范更华教授对H问题的研究也取得重要成就, 他得出了”Fan-type theorem”(New Sufficient Conditions for Cycles in Graphs, J. Comb. Theory B 37 (1984) 221-227): 若图中每对距离为2的点中有一点的度数至少是图的点数的一半, 则该图存在哈密尔顿圈. 该成果获得中国2005年度国家自然科学二等奖.
6. 1996年美国乔治亚州立大学陈冠涛教授, Egawa (Graph Theory 编委) 和Saito (Graph and Combinatorics 主编) 等再进一步推进了Ore定理: n阶2-连通图G的每对不相邻的点x, y满足 $1\le |N(u)\cap N(v)|\le \alpha (G)-1$, 则G是Halmitonian的. (Discrete Math. 112 (1993) 253-258);
   另: 陈冠涛教授得到在平衡的k部图是哈密尔顿图的紧的最小度条件(G. Chen et al., Hamiltonicity in balanced k-partite graphs, Graphs Combin. 11 (1995), no. 3, 221–231).
7. 2007年, 美国西弗吉尼亚大学赖虹建教授统一了上面全部结果, 得到了更加一般化的结论 (App. Math. Lett 20 (2007) 116-122).

4.4 度极大非哈密尔顿图

★度极大非 H 图

图 $G$ 称为度极大非 H 图 (maximally non-Hamiltonian), 如果它的度不弱于 (degree-majorized) 其它非 H 图.

$C_{m,n}$ 图

对于 $1\le m<n/2$, $C_{m,n}$ 图定义为:

$$C_{m,n}=K_m\vee ({\bar{K}}_m+K_{n-2m})$$

例如: $C_{1,5}$ 与 $C_{2,5}$

$C_{m,n}$ 图的性质

引理: 对于 $1\le m<n/2$ 的图 $C_{m,n}$ 不是 H 图.

证明: 取 $S=V(K_m)$, 则 $\omega (G-S)=m+1>|S|=m$. 所以, 由 H 图的性质知 $G$ 不是 H 图.

定理: 度极大非 H 图的特征

(Chvátal, 1972) 若 $G$ 是 $n\ge 3$ 的非 H 简单图, 则 $G$ 度弱于某个 $C_{m,n}$ 图.

证明:

设 $G$ 是度序列为 ($d_1,d_2,\dots ,d_n$) 的非 H 简单图, 且 $d_1\le d_2\le \dots \le d_n$, $n\ge 3$.

由度序列判定法: 存在 $m<n/2$, 使得 $d_m\le m$, 且 $d_{n-m}<n-m$. 于是, $G$ 的度序列必弱于如下序列:

$$(\stackrel{m}{m,m,\dots ,m},\stackrel{n-2m}{n-m-1,n-m-1,\dots ,n-m-1},\stackrel{m}{n-1,n-1,\dots ,n-1}$$

而上面序列正好是图 $C_{m,n}$ 的度序列.

注:

• (1) 定理刻画了非 H 简单图的特征: 从度序列角度看, $C_{m,n}$ 图族中每个图都是某个 $n$ 阶非 H 单图的极图 (再添加一条边后就变成 H 图).
• (2) 定理的条件是充分条件而非必要条件.

例

当 $n=5$ 时, 其度极大非 H 图族是: $C_{1,5}$ 与 $C_{2,5}$

$C_{1,5}$ 的度序列是: $(1,3,3,3,4)$, $C_{2,5}$ 的度序列是 $(2,2,2,4,4)$.

而 $5$ 阶圈 $C_5$ 的度序列是: $(2,2,2,2,2)$, 它度弱于 $C_{2,5}$, 但 $C_5$ 是 H 图.

★推论

设 $G$ 是 $n$ 阶简单图. 若 $n\ge 3$ 且 $|E(G)|>\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+1$ , 则 $G$ 是 H 图;
并且, 具有 $n$ 个顶点, $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+1$ 条边的非 H 图只有 $C_{1,n}$ 以及 $C_{2,5}$.

证明:

先证 $G$ 是 H 图. 若不然, 由 Chvátal 定理知, $G$ 度弱于某个 $C_{m,n}$ 图, 于是有

$$\begin{array}{rl}|E(G)|\le \left|E\left(C_{m,n}\right)\right|& =\frac{1}{2}\left[m^2+(n-2m)(n-m-1)+m(n-1)\right]\\ & =\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+1-\frac{1}{2}(m-1)(m-2)-(m-1)(n-2m-1)\\ & \le \left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+1\end{array}$$

这与条件矛盾! 所以 $G$ 是 H 图.

对于 $C_{1,n}$, 有 $|E(C_{1,n})|=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+1$;
除此之外, 只有 $m=2$, $n=5$ 时有 $|E(C_{2,5})|=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+1$.

因此结论成立.

注:

(1) 推论的条件是充分非必要的. 例如 $C_5$.

(2) 亦可断言 $G$ 中不存在度和 $\ge n$ 的点对, 应用 Ore 定理反证.

4.5 ★旅行售货员问题

TSP 问题

TSP 问题 (Travelling Salesman Problem) 即旅行商问题 / 旅行售货员问题 (由 Whitney 命名), 是应用图论中典型问题之一. 问题提法为: 一售货员要到若干城市去售货, 每座城市恰好经过一次且要回到出发城市, 问如何安排行走路线, 使其行走的总路程最短.

在赋权图中求最小 H 圈是 NP-hard 问题. 也就是说 TSP 问题不存在多项式时间算法.

事实上近似算法 (启发式算法) 有很多, 如最近邻算法, 分枝定界法, 贪婪算法, 遗传算法和边交换技术等.

TSP 问题是组合优化中研究最多的问题之一, 被用来当作优化方法的标杆. TSP 问题的算法的应用非常广泛. 例如:

• 如何安排机器在一块电路板上钻孔, 使得机器钻孔花费时间最少(孔代表城市, 钻头从一个孔到另一个孔的时间代表距离);
• 在给定区域内收集投币式公用电话中的硬币的线路.

边交换技术

(1) 在赋权完全图中取一个初始 H 圈 $C=v_1{v}_2\dots v_n{v}_1$;

(2) 如果存在下图中红色边 (交叉), 并且 $w(v_i{v}_{i+1})+w(v_j{v}_{j+1})>w(v_i{v}_j)+w(v_{i+1}{v}_{j+1})$, 则把 $C$ 修改为: $C_1=v_1{v}_2\dots v_i{v}_j\dots v_{i+1}{v}_{j+1}\dots v_n{v}_1$.

例

采用边交换技术求赋权完全图的一个近似最优 H 圈.

解: 取初始圈为:

于是, 求出一个近似最优解为: $W(H)=192$.

注: 为了得到进一步的优解, 可以从几个不同的初始圈开始, 通过边交换技术得到几个近似最优解, 然后从中选取一个近似解.

最优 H 圈的下界

可以通过如下方法求出最优 H 圈的一个下界:

(1) 在 $G$ 中删掉一点 $v$ (任意的) 得图 $G_1$;

(2) 在图 $G_1$ 中求出一棵最小生成树 $T$;

(3) 在 $v$ 的关联边中选出两条权值最小者 $e_1$ 与 $e_2$.

若 $H$ 是 $G$ 的最优圈, 则:

$$W(H)\ge W(T)+W(e_1)+W(e_2)$$

例

估计最优 H 圈的下界:

解: 在 $G$ 中删掉点 $NY$, 求得 $G-NY$ 的一棵最优生成树为:

所以, $W(H)\ge 122+35+21=178$.

例

设 $G$ 是赋权完全图, 对所有的 $x,y,z\in V(G)$, 满足三角不等式: $W(xy)+W(yz)\ge W(xz)$ .证明: $G$ 中最优圈的权最多是 $2W(T)$, 这里 $T$ 是 $G$ 中一棵最小生成树.

证明: 设 $T$ 是 $G$ 的一棵最小生成树, 将 $T$ 的每条边添上一条平行边得图 $T_1$, 显然 $T_1$ 是欧拉图.

设 $Q$ 是 $T_1$ 的一个欧拉环游: $Q=v_{i1}{v}_{i2}\dots .v_{ik}{v}_{i1}$.

则: $W(T_1)=W(Q)=2W(T)$.

现在, 从 $Q$ 的第三点开始, 删掉与前面的重复顶点, 得到 $G$ 的顶点的一个排列 $\pi$.

由于 $G$ 是完全图, 所以该排列对应 $G$ 的一个 $H$ 圈.

在 $\pi$ 中任意一条边 $uv$, 在 $T$ 中有一条唯一的 $u,v$ 路 $P$, 而该路正好是在 $Q$ 中的 $u$ 与 $v$ 间的部分.

由三角不等式知: $W(uv)\le W(P)$.

由于将 $\pi$ 中的边 $uv$ 用 $T$ 中的 $uv$ 路 $P$ 来代替就得到 $Q$, 所以: $W(\pi )\le W(Q)=2W(T)$.

即最优圈 $H$ 的权值满足: $W(H)\le W(\pi )\le W(Q)\le 2W(T)$.

4.6 超哈密尔顿图

超 H 图

若图 $G$ 是非 H 图, 但对于 $G$ 中任意点 $v$, 都有 $G-v$ 是 H 图, 则称 $G$ 是超 H 图 (hypohamiltonian).

解决 TSP 问题的整数规划解中, 一此特殊的超 H 图代表了 TSP 多面体中的面.

定理

Petersen 图是超 H 图 (阶数最小的, Herz,Duby,Vigué,1967).

证明:

(1) 证明 Petersen 图不是 H 图.

(2) 证明对任意点 $v$, $G-v$ 是 H 图.

由对称性, 只需考虑下面情形: $G-\{1\}$.

$G-\{1\}$ 中有 H 圈: $54328(10)7965$, 因此 $G$ 是超 H 图.

可迹, 超可迹

图 $G$ 称为是可迹的 (traceable) 如果 $G$ 包含一条 H 路.

若 $G$ 中没有 H 路, 但是对 $G$ 中任意点 $v$, $G-v$ 存在 H 路, 则称 $G$ 是超可迹的 (hypotraceable).

定理

Thomassen 图是超可迹图.

证明:

(1) 证明 $G$ 不存在 H 路;

(2) 证明对 $G$ 中任意点 $v$, 有 $G-v$ 存在 H 路.

由对称性: 我们取 $b$ 和 Ⅲ 中顶点逐一分析即可. 例如:

综上所述: 得 Thomassen 图是超可迹图.

4.7 欧拉图和哈密尔顿图的联系

从表面上看, E 图与 H 图间没有联系. 考查下图: (1) E 图但非 H 图; (2) E 图且 H 图; (3) H 图但非 E 图; (4) 非 E 图且非 H 图.

★线图的概念

线图 (line graph) $L(G)$

首先由Hassler Whitney 于 1932 年提出概念并研究了连通性

设 $G$ 是图, $G$ 的线图 $L(G)$ 定义为:

• $V(L(G))=E(G)$
• $(e_1,e_2)\in E(L(G))$⇔在 $G$ 中有：$e_1$ 与 $e_2$ 邻接

注: 线图可以看作图 $G$ 的边集的交图.

$n$ 次迭代线图 $L^n(G)$

$G$ 的 $n$ 次迭代线图 (n-th iterated line graph) $L^n(G)$为:

$$L^n(G)=L(L^{n-1}(G))$$

练习: 画出 $K_5$ 的线图的补图.

线图的性质

定理

线图 $L(G)$ 顶点数等于 $G$ 的边数; 若 $e=uv$ 是 $G$ 的边, 则 $e$ 作为 $L(G)$ 的顶点度数为: $d(e)=d(u)+d(v)-2$.

定理

若 $G=(n,m)$, 则线图 $L(G)$ 边数为:

$$m(L(G))=-m+\frac{1}{2}\sum _{v\in V(G)}{d}^2(v)$$

证法一: 由线图的定义, $L(G)$ 有 $m$ 个顶点. 对于 $G$ 中任一顶点 $v$, 关联于该顶点的 $d(v)$ 条边将产生 $L(G)$ 中 $C_{d(v)}^2$ 条边. 所以 $L(G)$ 中的总边数为:

$$m(L(G))=\sum _{v\in V(G)}{C}_{d(v)}^2=\frac{1}{2}\sum _{v\in V(G)}d(v)(d(v)-1)=-m+\frac{1}{2}\sum _{v\in V(G)}{d}^2(v)$$

证法二: 对线图应用握手定理.

$$m(L(G))=\frac{1}{2}\sum _{uv\in E(G)}{d}_{L(G)}(uv)=\frac{1}{2}\sum _{uv\in E(G)}(d_G(u)+d_G(v)-2)=-m+\frac{1}{2}\sum _{w\in V(G)}{d}_G^2(w)$$

定理

一个连通图同构于它的线图, 当且仅当它是圈.

定理

若图 $G$ 和 $H$ 有同构的线图, 则除了 $K_3$ 和 $K_{1,3}$ 外, $G$ 和 $H$ 同构.

(H. Whitney, Congruent graphs and the connectivity of graphs, American Journal of Mathematics 54 (1932) 150–168)

从线图的角度考察 E 图与 H 图的关系

$n$ 次剖分图 $S_n(G)$

图 $G$ 的 $n$ 次剖分图 (n-iterated subdivision graph), 是指将 $G$ 的每条边中插入 $n$ 个 $2$ 度顶点, 记为 $S_n(G)$.

$L_n(G)$

$$L_n(G)=L(S_{n‒1}(G))$$

注: 一般地, $L_n(G)\ne L^n(G)$

定理

一个图 $G$ 是 E 图的充要条件是 $L_3(G)$ 为 H 图.

注: 若条件为 $L_2(G)$ 则不对. (如下图)

定理

(1) 若 $G$ 是 E 图, 则 $L(G)$ 既是 E 图又是 H 图;

(2) 若 $G$ 是 H 图, 则 $L(G)$ 是 H 图. ($G$ 中的任意一个顶点在线图中都是一个团)

注: 该定理的逆不成立.

定理 (G. Chartrand 1968)

若 $G$ 是具有 $n$ 个点 $(n\ge 3)$ 的连通图且不是一条路, 则当 $k\ge n-3$ 时, 图 $L^k(G)$ 是 H 图.

G. Chartrand, On Hamiltonian line-graphs, Trans. Amer. Math. Soc. 134 (1968) 559–566

例如 $G$ 不是 Hamiltonian 图, $L^3(G)$ 是 Hamiltonian 图.

哈密尔顿指数 $h(G)$

(G. Chartrand, 1968) 图 $G$ 的哈密尔顿指数 (Hamiltonian index) 是使得 $L^k(G)$ 是 H 图的最小非负整数 $k$, 记作 $h(G)$.

对于不是路的图 $h(G)$ 存在且 $h(G)\le n-3$. 一般地, 哈密尔顿指数不容易给出. 注意到, 对上例中“Y”型图 $h(G)=n-3$.

事实上, 2011年, Z. Ryjáček, G.J. Woeginger和L. Xiong证明了, 求一般图的哈密尔顿指数的问题是 NP-hard 的(Hamiltonian index is NP-complete, Discrete Appl. Math. 159 (2011) 246–250).