哈密顿图

定义

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

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

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

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

性质

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

推论：设 G=<V, E> 是半哈密顿图，则对于 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 具有哈密顿回路。

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments