哈密顿图

定义

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

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

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

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

设 $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_{2 k + 1} (k \geq 1)$ 中含 $k$ 条边不重的哈密顿回路，且这 $k$ 条边不重的哈密顿回路含 $K_{2 k + 1}$ 中的所有边。

完全图 $K_{2 k} (k \geq 2)$ 中含 $k - 1$ 条边不重的哈密顿回路，从 $K_{2 k}$ 中删除这 $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$ 具有哈密顿回路。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用