欧拉图与哈密顿图
欧拉图¶
定义¶
欧拉图存在欧拉闭迹，半欧拉图只存在欧拉迹
若能遍历完所有的边但是没法回到起始点，称为非欧拉图但是有欧拉迹
欧拉图¶
假定 \(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^*\) 总权值最小” 相矛盾
Abstract
这个必要性的证明给出了最优欧拉环游的构造方法
半欧拉图最优欧拉环游¶
一个非负权的边赋权图 \(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^*\)：
哈密顿图¶
定义¶
哈姆顿图¶
如果经过图 \(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\)，均有：
Info
💡 别忘了 \(\omega(...)\) 的意思是连通分支数，这里还容易得到 \(H\) 图不存在割点。
只是必要条件而不是充分条件，经典例子——彼得森图
用于判断非 \(H\) 图：\(\exists S\subset V,\ \ \omega(G-S)\gt|S|\) ，则 \(G\) 不是 \(H\) 图。
充分条件¶
Dirac¶
对于 \(n≥3\) 的简单图 \(G\) , 如果 \(G\) 中有：
那么 \(G\) 是 \(H\) 图。
Ore¶
对于 \(n≥3\) 的单图 \(G\) , 如果 \(G\) 中的任意两个不相邻顶点 \(u\) 与 \(v\) ，有：
那么 \(G\) 是 \(H\) 图。
Abstract
该定理证明和 Dirac 定理可以完全一致！
该定理的条件是紧的。例如：设 \(G\) 是由 \(Κ_{k+1}\) 的一个顶点和另一个 \(Κ_{k+1}\) 的一个顶点重合得到的图，那么对于 \(G\) 的任意两个不相邻顶点 \(u\) 与 \(v\)，有：
但 \(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\) 的最优圈，则有权值下界：