图论-欧拉图与哈密顿图¶

知识点梳理¶

欧拉图¶

定义¶

通过所有的边一次且仅一次行遍所有顶点的通路称作哈密顿通路，通过所有的边一次且仅一次行遍所有顶点的回路称作哈密顿回路。

判别法¶

无向欧拉图：连通图且没有奇度顶点
无向半欧拉图：连通图且恰有两个奇度顶点
有向欧拉图：强连通的且每个顶点的入度等于出度
有向半欧拉图：单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大1，另一个顶点的出度比入度大1。其余顶点的入度等于出度。

欧拉图的结构¶

$G是非平凡的欧拉图\iff G是连通的且是若干个边不重的圈的并。$

求欧拉回路的方法¶

从欧拉图的结构入手¶

由于欧拉图可视作若干边不重的圈的并，因此对欧拉图进行划分，分解成若干圈后，就很容易得到一条欧拉回路。

构造性证明：Fleury算法¶

核心思想：能不走桥就不走桥。

有趣的结论：不存在顶点数为奇数边数为偶数的欧拉图

$Hint.握手定理,整除关系.$

哈密顿图¶

定义¶

经过所有顶点一次且仅一次的回路称做哈密顿回路，含有哈密顿回路的图叫做哈密顿图

注意：与判断欧拉图不同，至今人们还没有找到哈密顿图便于判断的充要条件。

必要条件¶

$设无向图G= <V,E>是半哈密顿图，则对于任意V_1\sub V \and V_1 \ne \emptyset,均有\\ p(G- V_1) \le |V| +1.$
$设无向图G=<V,E>是哈密顿图，则对于任意V_1\sub V \and V_1 \ne \empty,均有\\ p(G-V_1) \le |V_1|.$

充分条件¶

设G是n阶无向简单图，若对于G中任意**不相邻**的顶点u,v，均有 $d(u) + d(v) \ge n-1$ ，则G中存在哈密顿通路。
设G为n阶无向简单图，若对于G中任意两个**不相邻**的顶点u,v均有 $d(u) + d(v) \ge n$ ，则G中存在哈密顿回路。
n阶( $n \ge 2$ )竞赛图都有哈密顿通路。
n阶无向简单图中两不相邻的顶点 $u,v$ 若满足 $d(u) + d(v) \ge n$ ，则G为哈密顿图当且仅当 $G' = G \cup (u,v)$ 哈密顿图。

$Pf.$

必要性( $\Rightarrow$ )显然。

充分性：（证明思路类似于 $\forall u, v \in V, d(u) + d(v)\ge n \to 哈密顿图$ ）

简单来说，

存在通路 $\Gamma: uv_2v_3v_4\dots v_{n-1}v$ 为哈密顿通路

$\because d(u) + d(v) \ge n \therefore \exist v_{i_1} = v_2, v_{i_2}, \dots,v_{i_k}(k \ge 2)$ 与 $u$ 相邻

对于 $v,v$ 至少与 $v_{i_2}, \dots,v_{i_k}(k \ge 2)$ 中一个顶点的左邻居相连，（否则反证法：$d(u) + d(v) \le k + n-2 - (k-1)v = n-1 $矛盾）

这时画出图像，就能构造出一条哈密顿回路。

二部图的判别方法¶

设 $G = <V_1, V_2, E>$ 为二部图， $2\le |V_1|\le |V_2|$ ，则 $$ \begin{align} (1)& G是哈密顿图\iff |V_1| = |V_2|\ (2)& G是半哈密顿图\iff |V_2| = |V_1| + 1\ (3)& |V_2| \ge |V_1| + 2 \Rightarrow G既不是哈密顿图，也不是半哈密顿图. \end{align} $$

习题¶

判断欧拉图，求欧拉回路¶

注意：欧拉图是有充要条件的！因此可以直接由顶点的度来判断是否为欧拉图。
构造欧拉回路的方法：
直接法
划分若干边不重的圈
Fleury 算法
$n$ 阶有向完全图是欧拉图(√)

有向完全图是强连通的

欧拉图的性质¶

在 $k$ 个长度大于等于3的彼此分离的圈之间至少要加多少条新边才能使所得图成为欧拉图？

$k$ 条。

证明：有向欧拉图是强连通的。

$Pf.$ ： $$ D强连通\iff \exist经过每个顶点至少一次的回路.\ D是欧拉图\iff D中存在欧拉回路(经过每条边恰好一次，行遍所有顶点的回路). $$

设G是包含 $2k$ 个奇度顶点的无向连通图，证明：G中存在 $k$ 条边不重的简单通路 $\Gamma_1, \Gamma_2, \cdots ,\Gamma_k$ ，使得 $$ E(G) = \cup_{i = 1}^k E(\Gamma_i). $$

证明思路：对 $k$ 归纳。

判断哈密顿图，求哈密顿回路¶

判断哈密顿图的方法：

证明是
直接法：找到当然是
利用充分条件：任意两顶点度之和大于等于顶点数（注意：不满足充分条件的也可能是哈密顿图！）

注：这两种方法都很常用。充分条件的使用往往是对于比较规整的图（如完全二部图，对称图）。如果证明不出来，就必须找到一条哈密顿回路才可完成证明。

证明不是
证明不满足必要条件 $\forall V_1 \sub V \and V \ne \emptyset , p(G-V_1) \le |V_1|$
有n个人，已知他们中任意两个人合起来认识其余的n-2个人。证明：当 $n \ge 3 <span class="arithmatex"><span class="MathJax_Preview">时，存在哈密顿通路；当</span><script type="math/tex">时，存在哈密顿通路；当$ n \ge 4n \ge 4 时，存在哈密顿回路。
设G为n阶( $n \ge 3 <span class="arithmatex"><span class="MathJax_Preview">)无向简单图，边数</span><script type="math/tex">)无向简单图，边数$ m = {1\over 2} (n-1)(n-2) + 2m = {1\over 2} (n-1)(n-2) + 2,证明G是哈密顿图。

注意: 图论中最重要的两种证明方法: 递推(数学归纳法) 反证