超哈密尔顿图

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.28 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

超哈密尔顿图和迹

超哈密尔顿图

    若图 $G$ 是非 $H$ 图, 但对于 $G$ 中任意点 $v$，都有 $G−v$ 是 $H$ 图，则称 $G$ 是 超 $H$ 图 (Hypohamiltonian)。

    下面有一个定理:

Peterson 图是超哈密尔顿图

    证明:

    证明 Peterson 图不是 $H$ 图的过程略。

    下面基于已知 Peterson 图不是 $H$ 图的结论，证明 Peterson 图是超 $H$ 图。

    由对称性可知，只需考虑 $G-v_1$ 的情形即可。如上图所示即是删去 $v_1$ 之后的图中存在的 $H$ 圈。因此，Peterson 图是超 $H$ 图。

超哈密尔顿迹的概念

    图 $G$ 称为是 可迹的 (Traceable) 如果 $G$ 包含一条 $H$ 路。

    若 $G$ 中没有 $H$ 路，但是对 $G$ 中任意点 $v$，$G−v$ 存在 $H$ 路，则称 $G$ 是 超可迹的 (Hypotraceable)。

欧拉图和哈密尔顿图的关系

    如下所示，$E$ 图和 $H$ 图之间似乎并不存在关系:

    本节将说明欧拉图和哈密尔顿图之间的关系。

线图的定义

    设 $G$ 是图，$G$ 的线图 $L(G)$ 定义为:

$V(L(G)) = E(G)$
$(e_1,e_2) \in E(L(G)) \Leftrightarrow$ 在 $G$ 中有 $e_1$ 与 $e_2$ 邻接

    上述定义的含义是，将 $G$ 中的各条边转换为 $L(G)$ 中的点。如果 $G$ 的两条边在 $G$ 中相邻，则它们所对应的点在 $L(G)$ 中相邻。

    再给出一个定义: $G$ 的 $n$ 次迭代线图 (n-th Iterated Line Graph) $L^n(G)$ 为: $L^n(G)=L(L^{n-1}(G))$，如上图所示。

线图的性质

    线图有如下性质:

1. 线图 $L(G)$ 顶点数等于 $G$ 的边数，若 $e=uv$ 是 $G$ 的边，则 $e$ 作为 $L(G)$ 的顶点度数为: $d(e)=d(u)+d(v)−2$;
2. 若 $G=(n,m)$，则线图 $L(G)$ 的边数为: $$m[L(G)]=-m+\frac{1}{2}\sum_{v \in V(G)}d^2(v)$$

    (1) 显然，下面对 (2) 使用两种方法进行证明:

    证法 1: 由线图 $L(G)$ 有 $m$ 个顶点，则对于 $G$ 中任一顶点 $v$，关联于该顶点的 $d(v)$ 条边将产生 $L(G)$ 中 $C_{d(v)}^{2}$ 条边 (i.e. 任两条边在 $L(G)$ 代表的点都是邻接的)，所以 $L(G)$ 中的总边数为: $$m[L(G)] = \sum_{v \in V(G)}C^2_{d(v)} = \frac{1}{2} \sum_{v \in V(G)} d(v) \cdot [d(v)-1] = -m + \frac{1}{2} \sum_{v \in V(G)} d^2(v)$$

    证法 2: 对线图使用握手定理，可得: $$m[L(G)] = \frac{1}{2} \sum_{uv \in E(G)} d_{L(G)}(uv) = \frac{1}{2} \sum_{uv \in E(G)} (d_G(u) + d_G(v) - 2) = \frac{1}{2} \sum_{uv \in E(G)}(d_G(u)+d_G(v)) - \frac{1}{2} \cdot 2|E(G)| = -m + \frac{1}{2} d_G^2(w) $$

    另外，有结论:

一个连通图同构于它的线图，当且仅当它是圈。

    另外：

若图 $G$ 和 $H$ 有同构的线图，则除了 $K_3$ 和 $K_{1,3}$ 外，$G$ 和 $H$ 同构。

剖分图

    图 $G$ 的 $n$ 次剖分图 (n-iterated Subdivision Graph)，是指将 $G$ 的每条边中插入 $n$ 个 $2$ 度顶点, 记为 $S_n(G)$。如上图所示是 $S_1(G)$。

    如果我们定义 $L_n(G)=L(S_{n-1}(G))$ (p.s. 注意和 $L^n(G)$ 区分)，则我们有:

一个图 $G$ 是 $E$ 图的充要条件是 $L_3(G)$ 为 $H$ 图。

$E$ 图和 $H$ 图的关系

    有如下关系:

若 $G$ 是 $E$ 图，则 $L(G)$ 既是 $E$ 图又是 $H$ 图

若 $G$ 是 $H$ 图，则 $L(G)$ 是 $H$ 图(i.e. 原因是因为 $G$ 中的任意一个顶点在线图中都是一个团)

    值得注意的是，上述定理的逆不成立。

若 $G$ 是具有 $n$ 个点 $(n \ge 3)$ 连通图且不是一条路，则当 $k \ge n‒3$ 时，图 $L^{k}(G)$ 是 $H$ 图

    基于上述定理，定义图 $G$ 的 哈密尔顿指数 (Hamiltonian Index) 是使得 $L^k(G)$ 是 $H$ 图的最小非负整数 $k$，记作 $h(G)$。对于一般图来说，求解 $h(G)$ 是 NP-Hard 的。