CHT9-Euler map and Hamilton map

Euler map

我们知道图论的一个著名问题就是哥尼斯堡七桥问题（一笔画问题），而欧拉图就是讨论是否存在这样的一个“路”，可以遍历所有的“桥”的。

[!定义 1 ]
欧拉图： 设 $G$ 是一个图，$G$ 中包含所有边的迹（即每条边恰好出现一次的路径）称为 Euler 迹，闭的 Euler 迹称为 Euler 闭迹或 Euler 回路，具有 Euler 回路的图称为 Euler 图，开的 Euler 迹称为 Euler 开迹，具有 Euler 开迹的图称为半 Euler 图。

[! ] 定理 1（Euler图的充要条件）
设 $G$ 是连通图，则 $G$ 是 Euler 图当且仅当 $G$ 的所有顶点均是偶顶点.

[! ] 定理 2（半Euler图的充要条件）
设 $G$ 是连通图，则 $G$ 是半 Euler 图当且仅当 $G$ 中恰有两个奇顶点.

[!定义 2 ]
设 $D$ 是一个有向图，$D$ 中包含所有弧的有向迹，称为 Euler 有向迹，闭的 Euler 有向迹称为 Euler 有向闭迹或 Euler 有向回路，具有 Euler 有向回路的有向图称为 Euler 有向图，开的 Euler 有向迹称为 Euler 有向开迹，具有 Euler 有向开迹的有向图称为半 Euler 有向图。
显然，一个 Euler 有向图，如果没有孤立点，则必是强连通的。

二分图当且仅当只有偶回路

Hamilton map

老师人还挺好，说是有的部分比较难选学，课上不讲了一笔带过，可以私信邮件要英文资料

Hamilton 在 1859 年发明了一种“环游世界”游戏，即在如图 2.1(a) 所示的 12 面体上，从一个顶点出发，沿棱行走，要求经过每个顶点恰好一次后返回出发点，这相当于在图 2.1(b) 中找出一条包含图中所有顶点的圈。

于是我们抽象出定义

[! 定义1 ]
设 $G$ 是一个图，$G$ 中包含所有顶点的圈称为 Hamilton 圈，含有 Hamilton 圈的图称为 Hamilton 图，$G$ 中含有所有顶点的路称为 Hamilton 路，含有 Hamilton 路的图称为半 Hamilton 图。

注意：Hamilton图关注的是不重复的遍历所有的顶点，而不是边，这是与欧拉图的核心区别。

Hamilton图的判定问题至今仍具有讨论价值，其难度远远高于欧拉图（后者的判定已经有了上节的定理1这个足够好用的充要条件）
它并没有好用的充要条件，只有几个重要的充分条件和必要条件。

Hamilton 回路的个数也是一个具有价值的问题。（围圈问题，圆周游戏问题均是在完全图的特例）

Hamilton图的判定

下面给出若干个充分条件和必要条件，必要条件可以用来判否，充分条件可以用来判真

[!（必要条件）定理 1 ]
设 $G$ 是 Hamilton 图，则对于顶点集 $V$ 的任一非空真子集 $S$，均有$\omega(G - S) \leq |S| .$

证明： 思路是设C为Hamilton回路，C=v1v2…vn,考虑“删去”的点在C中，的话，相当

[! 补充定义]
割点：删除此点后图的分支数增加

割边：删除此边后图的分支数增加

[! 推论1]
若图G有割点或割边（桥），则G不是 Hamilton图

证明：割点的证明很简单，运用定理1即得。割边转化为割点来讨论，设割边e=<u,v>,分类讨论该边是或不是悬挂边，是悬挂边则u是割点；不是悬挂边，则由于割边的定义，该边连接的两个顶点至少有一个是割点…

当然，即然这个定理给出的是一个必要条件，那么说明存在满足此条件的图不是hamilton 图，可以自己尝试构造（（bushi
一个例子就是Petersen图

这是一个连通性极强的图，去掉5个顶点后仍是联通的，但找不到hamilton回路。

考虑定义几个对象，对任意非hamilton图G，我们可以不断按照一定方式添加边，一定存在一个时刻使得它成为hamilton图（这个过程中也容易想到，因为成为hamilton图的方式有若干种，所以我们只好以下面这个方式来定义接近hamilton图，这保证了唯一性，使得定义良好）
我们定义一个及其接近具有hamilton回路的唯一对象

[! 极大非hamilton图]
任意两个不相邻的顶点间加上一条边，则成为hamilton图

(Q:所有非hamilton图都有对应的极大非hamilton图吗–是的吧…毕竟是这么定义的)

[! ] (充分条件) Dirac’s theorem （1952)
狄拉克定理：设 $G$ 是简单图，且 $n \geq 3$，$\delta(G) \geq \frac{n}{2}$，则 $G$ 是 Hamilton 图。

证明：

[! 定理] (充分条件)Ore‘s theorem(推广)（1960)
奥尔定理 ：设图G(n,m),n≥3,若G中任意两个不相邻的顶点u和v,均有deg(u)+ deg(v)≥n,则G有哈密顿回路。(是哈密顿图)

闭图

hamilton 图当然也是有 有向图的定义和问题的。我们暂时略过。

将来会遇到的类似“货郎担问题”的带权hamilton图问题，在算法中将会遇到。^^