哈密顿图

定义¶

通过图中所有顶点一次且仅一次的通路称为哈密顿通路。

通过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图。

具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。

设 \(G=\langle V, E\rangle\) 是哈密顿图，则对于 \(V\) 的任意非空真子集 \(V_1\)，均有 \(p(G-V_1) \leq |V_1|\)。其中 \(p(x)\) 为 \(x\) 的连通分支数。

推论：设 \(G=\langle V, E\rangle\) 是半哈密顿图，则对于 \(V\) 的任意非空真子集 \(V_1\)，均有 \(p(G-V_1) \leq |V_1|+1\)。其中 \(p(x)\) 为 \(x\) 的连通分支数。

完全图 \(K_{2k+1} (k \geq 1)\) 中含 \(k\) 条边不重的哈密顿回路，且这 \(k\) 条边不重的哈密顿回路含 \(K_{2k+1}\) 中的所有边。

完全图 \(K_{2k} (k \geq 2)\) 中含 \(k-1\) 条边不重的哈密顿回路，从 \(K_{2k}\) 中删除这 \(k-1\) 条边不重的哈密顿回路后所得图含 \(k\) 条互不相邻的边。

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

推论 1：设 \(G\) 是 \(n(n \geq 3)\) 的无向简单图，若对于 \(G\) 中任意不相邻的顶点 \(v_i, v_j\)，均有 \(d(v_i)+ d(v_j) \geq n\)，则 \(G\) 中存在哈密顿回路，从而 \(G\) 为哈密顿图。

推论 2：设 \(G\) 是 \(n(n \geq 3)\) 的无向简单图，若对于 \(G\) 中任意顶点 \(v_i\)，均有 \(d(v_i) \geq \frac{n}{2}\)，则 \(G\) 中存在哈密顿回路，从而 \(G\) 为哈密顿图。

设 \(D\) 为 \(n(n \geq 2)\) 阶竞赛图，则 \(D\) 具有哈密顿通路。

若 \(D\) 含 \(n(n \geq 2)\) 阶竞赛图作为子图，则 \(D\) 具有哈密顿通路。

强连通的竞赛图为哈密顿图。

若 \(D\) 含 \(n(n \geq 2)\) 阶强连通的竞赛图作为子图，则 \(D\) 具有哈密顿回路。