哈密顿图

定义

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

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

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

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

性质

设 是哈密顿图，则对于 的任意非空真子集 ，均有 。其中 为 的连通分支数。

推论：设 是半哈密顿图，则对于 的任意非空真子集 ，均有 。其中 为 的连通分支数。

完全图 中含 条边不重的哈密顿回路，且这 条边不重的哈密顿回路含 中的所有边。

完全图 中含 条边不重的哈密顿回路，从 中删除这 条边不重的哈密顿回路后所得图含 条互不相邻的边。

充分条件

设 是 的无向简单图，若对于 中任意不相邻的顶点 ，均有 ，则 中存在哈密顿通路。

推论 1：设 是 的无向简单图，若对于 中任意不相邻的顶点 ，均有 ，则 中存在哈密顿回路，从而 为哈密顿图。

推论 2：设 是 的无向简单图，若对于 中任意顶点 ，均有 ，则 中存在哈密顿回路，从而 为哈密顿图。

设 为 阶竞赛图，则 具有哈密顿通路。

若 含 阶竞赛图作为子图，则 具有哈密顿通路。

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

若 含 阶强连通的竞赛图作为子图，则 具有哈密顿回路。

---

最后更新: 2023年5月6日
创建日期: 2018年7月11日