1. 定义

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

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

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

1.2 哈密顿图 & 半哈密顿图

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

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

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

2. 性质

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

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

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

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

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

  • GGnn 阶无向简单图,若对于 GG 中任意不相邻的顶点 u,vu,v 均有

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

GG 中存在哈密顿通路。

  • GGn(n3)n(n \geq 3) 阶无向简单图,若对于 GG 中任意不相邻的顶点 u,vu,v 均有

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

GG 中存在哈密顿回路。

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

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