Graph Theory and Network Algorithm 3 Euler图和Hamilton图

发表于 2020-11-22 更新于 2022-04-08 分类于 UCAS ， Courses 阅读次数：

图论与网络算法 (070105M04003H)，Euler图和Hamilton图。

Euler图和Hamilton图

概念

Euler闭迹：经过图$G$每条边恰好一次的闭迹。
Euler迹：经过每条边恰好一次的迹。
Euler图：有Euler闭迹的图。
可一笔画的图：存在Euler迹或Euler闭迹的图。（$\Longleftrightarrow$至多有$2$个奇度顶点的图）
可k笔画的图：可分解为$k$条迹或闭迹的并的图。

Hamilton路：经过图$G$每个顶点恰好一次的路。
Hamilton圈：经过图$G$每个顶点恰好一次的圈。
Hamilton图：具有Hamilton圈的图。
闭包（closure）：$C(G)$，反复连接$G$中度之和$\ge\upsilon(G)$的不相邻顶点对所得的图。
- $G$的闭包$C(G)$是唯一确定的。（反证，设两个闭包，取出第一条相异边，由其端点度数和推出矛盾。）
度序列：设简单图$G$的顶点度为$d_1\le d_2\le...\le d_\upsilon$，称序列$(d_1,d_2,...d_\upsilon)$为$G$的度序列。

定理

Theorem 4.1.1 (Euler, 1736)

一个非空连通图时Euler图$\Longleftrightarrow$它没有奇度顶点。

$\Longrightarrow$ $\forall v\in V(G)$，Euler闭迹每经过$v$一次，就有两条与$v$关联的边被使用；

$\Longleftarrow$ 不妨设$\upsilon(G)>1$，因$G$连通，故至少有一条边。反证，设$S=\{G|G$是至少有一边的连通图，无奇度顶点，且不是Euler图$\}\ne\varnothing$，取$S$中边最少的一个图记为$G'$，因$\delta(G')\ge2$，故$G'$含圈，设$C$是$G'$中最长的闭迹，考虑$G'-E(C)$的非空连通分支记为$G_0，$则$G_0$有Euler闭迹$C_0$，且$V(C)\cap V(C_0)\neq\varnothing$，故可取出$G'$的一条更长的闭迹$C+C_0$，矛盾；

$\Longleftarrow$ 也可用数学归纳法证明。

Theorem 4.1.2

一个连通图有Euler迹$\Longleftrightarrow$它至多有两个奇度顶点。

$\Longrightarrow$ 设Euler迹$T$，在始末顶点间添加一条边$e$（若其有边相连，则$e$为重边），则$T+e$有Euler闭迹，故没有奇度顶点，则原图至多有两个奇度顶点；

$\Longleftarrow$ 若$G$无奇度顶点，则有Euler闭迹；若否，则在两点间添加一条边$e$，则$G+e$有Euler闭迹，故$G$有Euler迹。

一个连通图可用不超过$k$笔画成$\Longleftrightarrow$它至多有$2k$个奇度顶点。

Theorem 4.1.3 (Toida, Mckee)

一个非平凡连通图$G$是Euler图$\Longleftrightarrow G$每条边含在奇数个圈上。

头也大，磨叽。

Theorem 4.1.3

若$G$是Euler图，则Fleury算法终止时得到的是$G$的Euler闭迹。

Theorem 4.2.1 设$C$是一条经过赋权连通图$G$每条边至少一次的闭途径，则$C$是$G$最优邮路$\Longleftrightarrow C$对应的最优邮路Euler图$G^*$满足：

$G$每条边在$G*$中至多重复出现一次；
$G$的每一个圈上，在$G^*$中重复出现的边权之和不超过该圈总权的一半。

Theorem 4.2.2 设$G$是赋权连通图，$G$中有$2k$个奇度顶点。$G^*$是$G$的一个最优邮路Euler图，令$E'=\{e|e\in E(G)$，在由$G$得到$G^*$时，$e$被添加重复边$\}$。则边导出子图$G[E']$是以$G$的奇度顶点为起点和终点的$k$条无公共边的最短路之并。

Theorem 4.3.1 $G=(X,Y)$，$G$为$H$图$\Longrightarrow G$有偶数个顶点。

注意到$G$若有$H$，则顶点必再$X,Y$间交替出现。

Theorem 4.3.2 $G$是$H$图$\Longrightarrow \forall S\subset V(G),S\ne\varnothing:w(G-S)\le|S|$。

设$C$为$G$的$H$圈，则$\forall S\subset V(C),C\ne\varnothing:w(C-S)\le|S|$，
又$C-S$是$G-S$的生成子图，故$w(G-S)\le w(C-S)\le|S|$。

Theorem 4.3.3 (Dirac, 1952) (度型条件) 简单图$G$，$\upsilon(G)\ge3,\delta(G)\ge\frac{\upsilon(G)}{2}\Longrightarrow G$是$H$图。

反证，令$A=\{G|\upsilon(G)\ge3,\delta(G)\ge\frac{\upsilon}{2}$，且$G$非$H$图$\}\ne\varnothing$，取$S$中边最多的一个图记为$G$。（因为$\upsilon$阶图边数够多时必为$H$图，故这样的$G$存在）因$G$非$H$图，故一定不是完全图。$\forall u,v\in V(G):uv\notin E(G),G+uv$是$H$图，且其$H$圈经过$e=uv。$于是$G$中存在$H$路$v_1,v_2,...,v_\upsilon:v_1=u,v_\upsilon=v$。考虑$d(u)+d(v)$，设$S=\{v_j|uv_{j+1}\in E(G)\}$，$T=\{v_i|v_iv\in E(G)\}$，则$|S\cup T|<\upsilon(G$（$v_\upsilon\notin\cup T$），$|S\cup T|=0$，故$d(u)+d(v)=|S|+|T|=|S\cup T|+|S\cap T|<\upsilon(G)$，矛盾。

Theorem 4.3.4 (Ore, 1960) (闭包型条件) 简单图$G,u,v\in V(G):uv\notin E(G), d(u)+d(v)\ge\upsilon(G)$，$G$是$H$图$\Longleftrightarrow G+uv$是$H$图。

$\Longrightarrow$ 显然；

$\Longleftarrow$ 与Theorem 4.3.3证法相同。

Theorem 4.3.6 (Bondy & Chvátal, 1976) (闭包型条件) 简单图$G$，$G$是$H$图$\Longleftrightarrow C(G)$是$H$图。

构造闭包过程中反复运用Theorem 4.3.4。

简单图$G:\upsilon(G)\ge3$，$C(G)$是完全图$\Longrightarrow G$是$H$图。

Theorem 4.3.7 (Chvátal, 1972) (度序列条件) 简单图$G:\upsilon(G)\ge3$，其度序列为$(d_1,d_2,...,d_\upsilon):d_1\le d_2\le...\le d_\upsilon$。$\nexists m<\frac{\upsilon(G)}{2}:d_m\le m,d_{\upsilon-m}<v-m \Longrightarrow G$是$H$图。

下用反证法证明$C(G)$是完全图。假设$C(G)$不是完全图，设$u,v\in V(G):uv\notin E(G),\bar{d}(u)\le\bar{d}(v),\bar{d}(u)+\bar{d}(v)$尽可能大，记$\bar{d}(u)=m$。（$\bar{d}$表示在闭包中的度）令 \[ \bar{N}(u)=\{w\in V-\{u\}|w在C(G)中与u不相邻\} \\ \bar{N}(v)=\{w\in V-\{v\}|w在C(G)中与v不相邻\} \] 分析$\bar{N}(u)\cup\{u\}$和$\bar{N}(v)$在$C(G)$中的顶点个数和顶点度上界$...$

此定理说明了若图$G$满足：有某些顶点的度较小，则就有相应另一些顶点的度足够大，那么$G$就会成为$H$图。

算法

求Euler图中的Euler闭迹

Fleury算法
- 思想：$\forall v\in V(G)$作为起点，逐次选边加入迹（待添加的边需要与当前迹$T$相邻，且尽可能不选$G-T$的割边）。
- 复杂度：

中国邮递员问题

图上作业法
- 思想：先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。
- 复杂度：大
Edmonds-Johnson方法
- 思想：计算原图奇度点间最短路，以此构造赋权完全图，求出该图的一个最小权完美匹配，并将相应的边加到原图里再求其Euler闭迹。
- 复杂度：$O(\upsilon^3)$

旅行商问题

1-邻近点法（近似算法）
- 思想：总是选择尚未经过的邻点中最近的一个前行，直至遍历$K_n$的所有顶点后返回出发点。（深度优先搜索）
- 复杂度：$O(n_2)$
- 近似比：$\max\limits_{I}|\frac{A(I)}{Opt(I)}|\rightarrow\infty$
最小生成树法（近似算法）
- 思想：先求$K_n$最小生成树$T$，给$T$没边加一重边，然后求出$T$的Euler闭迹，若沿此闭迹前行时遇到的顶点已被访问，则跳过它直接访问闭迹的下一个顶点，直至遍历$K_n$的每个顶点。
最小权匹配法（近似算法）（Christofides算法）
- 思想：先求$K_n$最小生成树$T$，对$T$中的所有奇度顶点，求出它们在$K_n$中的最小权完美匹配，将所得匹配边添加到$T$上，然后求出$T$的Euler闭迹，若沿此闭迹前行时遇到的顶点已被访问，则跳过它直接访问闭迹的下一个顶点，直至遍历$K_n$的每个顶点。

练习

证明：一个连通图可用不超过$k$笔画完$\Longleftrightarrow$它至多又$2k$个奇度顶点。

$\Longrightarrow$ 则可添加至多$k$条边将这$k$笔首尾相接；

$\Longleftarrow$ 添加若干边使其无奇度顶点，作Euler闭迹后再把它拆开。

连通图$G$使Euler图$\Longleftrightarrow G$可表成彼此无公共边的圈的并。

$\Longrightarrow$ 因$\delta(G)\ge2$，故$G$含圈，可依次拆出一串圈；

$\Longleftarrow$ $\forall v \in V(G)$，$v$都含在若干个圈上，故度为偶数。

给出一个算法，用于在又Euler迹的图中求一条Euler迹。

把Fleury算法的第一步改为尽可能选择奇度点作为初始点。

多米诺骨牌每一块上有$0,1,2,3,4,5,6$七个数字之一（$0$用$O$表示，其它数字用点数表示）。将标有不同数字的多米诺骨牌组成骨牌对子（无序对），如$(0,1)$，$(0,2)$，$(2,4)$等，共可组成$\frac{7\times 6}{2}$个不同的对子。现要将这$21$个对子首尾相接连起来，使得对任何两个相邻的对子，前一个对子的尾数与后一个对子的首数相等。试用图论方法考虑：是否能按上述规则将这$21$个骨牌对子连成一个圆圈？

$K_7$使Euler图，故可。

$k\ge2$，证明顶点数为$2k-1$的k-正则简单图是$H$图。

$\upsilon=2k-1\ge3,\delta=k\ge\frac{2k-1}{2}=\frac{\upsilon}{2}$，由度型条件得证；

由闭包型条件和度序列条件都可证得。

证明：若图$G$有$H$路，则$\forall S\subset V(G),S\ne\varnothing:w(G-S)\le|S|+1$。

% label primary@设$P$为$G$的$H$路，则$\forall S\subset V(C),C\ne\varnothing:w(C-S)\le|S|+1$， %}又$P-S$是$G-S$的生成子图，故$w(G-S)\le w(P-S)\le|S|+1$

加一边构成$H$图后使用Theorem 4.3.2也可证得。

设围一张圆桌坐着至少$6$个人，试用图论方法证明：一定可以调整他们的坐位，使得每个人两侧都挨着新邻居。

把可调整路线作为边构造图，用度型条件可证其为$H$图。

总结

证明Euler图和Hamilton图度型条件都用到的方法：设$\{G|G$满足条件但$G$不满足结论$\}$，取出此集合中边数最少/长的图分析。
要证简单图为$H$图，想度型条件，闭包条件和度序列条件。