哈密顿图

1. 定义

1.1 哈密顿通路 & 哈密顿回路

• 经过图（无向图或有向图）中所有顶点一次且仅一次的通路称作哈密顿通路。

• 经过图（无向图或有向图）中所有顶点一次且仅一次的回路称作哈密顿回路。

1.2 哈密顿图 & 半哈密顿图

• 具有哈密顿回路的图称作哈密顿图。

• 具有哈密顿通路但不具有哈密顿回路的图称作半哈密顿图。

【注】规定平凡图是哈密顿图。

2. 性质

【注】$p(G)$ 表示 $G$ 的连通分支数。

• 设无向图 $G = \lt V,E \gt$ 是哈密顿图，则对于任意的 $V_1 \subset V$ 且 $V_1 \ne \varnothing$，均有

$$\begin{array}{c} p(G-V_1) \leq |V_1| \end{array}$$

• 设无向图 $G = \lt V,E \gt$ 是半哈密顿图，则对于任意的 $V_1 \subset V$ 且 $V_1 \ne \varnothing$，均有

$$\begin{array}{c} p(G-V_1) \leq |V_1| + 1 \end{array}$$

• 设 $G$ 是 $n$ 阶无向简单图，若对于 $G$ 中任意不相邻的顶点 $u,v$ 均有

$$\begin{array}{c} d(u) + d(v) \geq n-1 \end{array}$$

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

• 设 $G$ 是 $n(n \geq 3)$ 阶无向简单图，若对于 $G$ 中任意不相邻的顶点 $u,v$ 均有

$$\begin{array}{c} d(u) + d(v) \geq n \end{array}$$

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

• 设 $u,v$ 为 $n$ 阶无向简单图 $G$ 中两个不相邻的顶点，且 $d(u) + d(v) \geq n$，则 $G$ 为哈密顿图当且仅当 $G \cup (u,v)$ 为哈密顿图。

• $n(n \geq 2)$ 阶竞赛图中都有哈密顿通路。