欧拉图与哈密顿图

欧拉图

• 欧拉通路：经过图中每条边一次且仅一次的通路称为欧拉通路。
• 欧拉回路：经过图中每条边一次且仅一次的回路称为欧拉回路。
• 欧拉图：包含欧拉回路的图称为欧拉图。
• 半欧拉图：包含欧拉通路但不包含欧拉回路的图称为半欧拉图。

规定平凡图是欧拉图。 欧拉通路与欧拉回路是简单通路与简单回路

判定定理

无向图

无向图 $G$ 是欧拉图的充要条件是 $G$ 是连通的且每个顶点的度数都是偶数。 无向图 $G$ 是半欧拉图的充要条件是 $G$ 是连通的且恰有两个顶点的度数是奇数。

有向图

有向图 $D$ 是欧拉图的充要条件是 $D$ 是强连通的且每个顶点的入度等于出度。 有向图 $D$ 是半欧拉图的充要条件是 $D$ 是强连通的且恰有两个顶点的度数是奇数。

欧拉图的性质

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

非环非平凡欧拉图 $G$ 满足：

$$\lambda (G)\ge 2$$

即 $G$ 中没有桥。

哈密顿图

• 哈密顿通路：经过图中每个顶点一次且仅一次的通路称为哈密顿通路。
• 哈密顿回路：经过图中每个顶点一次且仅一次的回路称为哈密顿回路。
• 哈密顿图：包含哈密顿回路的图称为哈密顿图。
• 半哈密顿图：包含哈密顿通路但不包含哈密顿回路的图称为半哈密顿图。

规定平凡图是哈密顿图。 哈密顿通路与哈密顿回路是初级通路与初级回路。

必要条件

设 $G=⟨V,E⟩$ 是一个哈密顿图，则对于任意 $V_1⊊V$，且 $V_1\ne \varnothing$，有：

$$p(G-V_1)\le \left|V_1\right|$$

其中 $p(G)$ 表示 $G$ 的连通分支数。

设 $G=⟨V,E⟩$ 是一个半哈密顿图，则对于任意 $V_1⊊V$，且 $V_1\ne \varnothing$，有：

$$p(G-V_1)\le \left|V_1\right|+1$$

充分条件

设 $G$ 是 $n$ 阶无向简单图，若对于任意不相邻的顶点 $v_i,v_j$，有：

$$d(v_i)+d(v_j)\ge n-1$$

则 $G$ 中存在哈密顿通路。

若：

$$d(v_i)+d(v_j)\ge n$$

则 $G$ 中存在哈密顿回路。