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

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

定义了度极大非 $H$ 图后，我们来看关于它的作图方法。对于 $1 \le m < \frac{n}{2}$，$C_{m,n}$ 图定义为 $C_{m,n} = K_m \vee (\bar{K}_m + K_{n-2m})$，其中 $\vee$ 是图的联运算，具体可看子图、图运算、路与连通性。例如，对于 $C_{1,5}$，我们可以得到 $C_{1,5} = K_1 \vee (\bar{K_1} + K_{5-2 \times 1}) = K_1 \vee (\bar{K_1} + K_3)$，作图如下所示:

$C_{m,n}$ 图性质

$C_{m,n}$ 图有如下性质:

对于 $1 \le m \le \frac{n}{2}$ 的图 $C_{m,n}$，其不是 $H$ 图。

证明:

取 $S=V(K_m)$，则 $\omega(G-S) = m+1 > |S| = m$，因此由我们在哈密尔顿图讨论的关于 $H$ 图的性质可知，$G$ 不是 $H$ 图。

Chvátal 非 $H$ 图极图定理

Chvátal 证明了:

若 $G$ 是 $n \ge 3$ 的非 $H$ 简单图，则 $G$ 度弱于某个 $C_{m,n}$ 图，也即 $C_{n,m}$ 图族中每个图都是某个 $n$ 阶非 $H$ 单图的极图。

证明：

设 $G$ 是度序列为 $(d_1, d_2, ..., d_n)$ 的非 $H$ 简单图，且 $d_1 \le d_2 \le ... \le d_n$, $n \ge 3$。则由我们在哈密尔顿图一文中阐述过的度序列判定法，我们知道当 $G$ 是非 $H$ 图时，存在 $m < \frac{n}{2}$，使得 $d_m \le m$，且 $d_{n-m} < n-m$。于是，$G$ 的度序列必弱于如下序列: $$(\underbrace{m, m, ..., m}_{m个},\underbrace{n-m-1,n-m-1,...,n-m-1}_{n-2m个},\underbrace{n-1,n-1,...,n-1}_{m个})$$

原因是因为第 $m$ 个最小度 $d_m \le m$，因此我们令最小的 $m$ 个度都为 $m$; 然后有第 $n-m$ 个最小度 $d_{n-m}< n-m$，因此我们让从 $d_{m+1}$ 开始到 $d_{n-m}$ 的 $(n-m)-(m+1)+1=n-2m$ 个度数为 $n-m+1$，然后令剩下的 $m$ 个没有约束的度数为最大值，也即 $n-1$。综上可以得到上述度序列。

上面的度序列正好是图 $C_{m,n}$ 的度序列。

上述定理是充分条件而不是必要条件，也即 $G$ 度弱于某个 $C_{m,n}$ 图，不能说明它是非 $H$ 图。

下面有一个推论:

若 $G$ 是 $n \ge 3$ 的简单图，若 $|E(G)| > \begin{pmatrix} n-1 \\ 2 \end{pmatrix}+1$，则 $G$ 是 $H$ 图。
并且，具有 $n$ 个顶点，$\begin{pmatrix} n-1 \\ 2 \end{pmatrix}+1$ 条边的非 $H$ 图只有 $C_{1,n}$ 和 $C_{2,5}$。

证明:

首先我们证明满足条件 $|E(G)| > \begin{pmatrix} n-1 \\ 2 \end{pmatrix}+1$ 的图是 $H$ 图。

若不然，由 2 可知，图 $G$ 度弱于某个 $C_{m,n}$ 图，于是有: $$ \begin{align} |E(G)| &\le |E(C_{m,n})| \\ &= \frac{1}{2}[] \end{align} $$

TSP 问题

TSP (Travel Salesman Problem) 问题即旅行商问题，是应用图论中典型问题之一。问题提法为：一售货员要到若干城市去售货，每座城市恰好经过一次且要回到出发城市，问如何安排行走路线，使其行走的总路程最短。

在赋权图中求最小 $H$ 圈是 NP-hard 问题，也就是说 TSP 问题不存在多项式时间算法。

事实上近似算法(启发式算法)有很多，如最近邻算法、分枝定界法、贪婪算法、遗传算法和边交换技术等。

边交换技术

边交换技术的流程如下所示：

在赋权完全图中取一个初始的 $H$ 圈 $C=v_1,v_2,...,v_n,v_1$;
如果存在上图中的红色边，并且 $w(v_iv_{i+1})+w(v_jv_{j+1}) > w(v_iv_j)+w(v_{i+1}v_{j+1})$，则把 $C$ 修改为 $C_1=v_1v_2,...,v_i,v_j,...,v_{i+1},v_{j+1},...,v_n,v_1$
迭代 (2) 直到找不到满足 (2) 条件的交叉边

再次强调的是，上述算法只能保证获得一个近似最优解。为了得到进一步的优解，可以从几个不同的初始圈开始，通过边交换技术得到几个近似最优解，然后从中选取一个近似解。

最优 $H$ 圈的下界

给出 $H$ 圈下界的原因是因为我们不存在多项式时间的求解 $H$ 圈的方法，因此只能进行近似。而评估近似结果的方法就是将近似结果和最优 $H$ 圈的下界进行比较，因此我们需要对最优 $H$ 圈的下界进行研究。

求解最优 $H$ 圈的下界的方法如下:

在 $G$ 中删掉任意的一点 $v$ 得到图 $G_1$;
在图 $G_1$ 中求出一颗最小生成树 $T$;
在 $v$ 的关联变种选出两条权值最小的 $e_1$ 和 $e_2$;

若 $H$ 是 $G$ 的最优圈，则 $w(H) \ge w(T)+w(e_1)+w(e_2)$。

Zobin

度极大非哈密尔顿图和 TSP 问题