欧拉图

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

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

判定定理

无向图

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

有向图

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

欧拉图的性质

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

非环非平凡欧拉图 $G$ 满足： $$\lambda(G) \geq 2$$ 即 $G$ 中没有桥。

哈密顿图

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

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

必要条件

设 $G = \langle V, E \rangle$ 是一个哈密顿图，则对于任意 $V_1 \varsubsetneq V$，且 $V_1 \neq \varnothing$，有： $$p(G - V_1) \leq \left|V_1\right|$$ 其中 $p(G)$ 表示 $G$ 的 连通分支数 。

设 $G = \langle V, E \rangle$ 是一个半哈密顿图，则对于任意 $V_1 \varsubsetneq V$，且 $V_1 \neq \varnothing$，有： $$p(G - V_1) \leq \left|V_1\right| + 1$$

充分条件

设 $G$ 是 $n$ 阶无向简单图，若对于任意不相邻的顶点 $v_i, v_j$，有： $$d(v_i) + d(v_j) \geq n - 1$$ 则 $G$ 中存在哈密顿通路。

若： $$d(v_i) + d(v_j) \geq n$$ 则 $G$ 中存在哈密顿回路。