哈密顿图

哈密顿通路

经过图中所有顶点仅一次的通路.

指向原始笔记的链接

哈密顿回路

经过图中所有顶点仅一次的回路.

指向原始笔记的链接

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

具有哈密顿通路的且无哈密顿回路的图为半哈密顿图.

• 平凡图 是哈密顿图.
• 哈密顿通路是初级通路, 哈密顿回路是初级回路.
• 环和平行边不影响哈密顿性.

哈密顿图的实质是将图中所有顶点排在一个圈上.

定理 设无向图 $G=<V,E>$ 是哈密顿图, 对于任意 $V_1\subset V$ 且 $V_1\ne \varnothing$ 均有 $p(G-V_1)\le |V_1|$.

为哈密顿图的必要条件.

彼得松图 满足 $p(G-V_1)\le |V_1|$ 但不是哈密顿图.

推论 设无向图 $G=<V,E>$ 是半哈密顿图, 对于任意 $V_1\subset V$ 且 $V_1\ne \varnothing$ 均有 $p(G-V_1)\le |V_1|+1$.

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

为半哈密顿图的充分条件.

推论 设 $G$ 为 $n(n\le 3)$ 阶无向简单图, 若对任意不相邻顶点 $v_i,v_j$, 均有 $d(v_i)+d(v_j)\ge n$, 则 $G$ 中存在哈密顿回路, 为哈密顿图.

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

定理 若 $D$ 为 n 阶竞赛图, 则 $D$ 中具有哈密顿通路.