哈密顿图

图的基本概念#图的联通性

定义6.2.1 哈密顿图相关概念

设图$G=(V,E)$为有向图或无向图：

1. ​​哈密顿通路​​
   经过图中每个顶点​​一次且仅一次​​的通路

2. ​​哈密顿回路​​
   经过图中每个顶点​​一次且仅一次​​的回路

3. ​​哈密顿图​​
   具有哈密顿回路的图（Hamiltonian graph）

4. ​​半哈密顿图​​
   具有哈密顿通路但不存在哈密顿回路的图（Semi-Hamiltonian graph）

定理6.2.1 哈密顿图的必要条件

设无向图$G=(V,E)$是哈密顿图，则对于任意非空顶点子集$V_1 \subset V$，均有：

其中$p(G - V_1)$表示移除$V_1$后的连通分支数。

推论6.2.1 半哈密顿图的必要条件

设无向图$G=(V,E)$是半哈密顿图，则对于任意非空顶点子集$V_1 \subset V$，均有：

注6.2.1 二部图的哈密顿性分析

设二部图$G=(V_1,V_2,E)$满足：

可得以下结论：

1. ​​哈密顿图条件​​：若$G$是哈密顿图，则$|V_2|=|V_1|$
2. ​​半哈密顿图条件​​：若$G$是半哈密顿图，则$|V_2|=|V_1|$或$|V_2|=|V_1|+1$
3. ​​非哈密顿情形​​：若$|V_2| \geq |V_1| + 2$，则$G$既不是哈密顿图也不是半哈密顿图

定理6.2.2 哈密顿通路的充分条件

设$G$为$n$阶无向简单图，若对任意不相邻顶点$u,v$满足：

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

推论6.2.2 哈密顿回路的充分条件

设$G$为$n(n \geq 3)$阶无向简单图，若对任意不相邻顶点$u,v$满足：

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

定理6.2.3 哈密顿图的充要条件

设$u,v$为$n$阶无向简单图$G$中不相邻顶点且满足：

则：

定理6.2.4 竞赛图的哈密顿性

对任意$n(n \geq 2)$阶竞赛图$D$，必存在哈密顿通路。图的基本概念#度数、通路与回路