哈密顿图

定义

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本页面最近更新：2023/5/6 19:22:00，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, Ir1d, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用