动机
添上一条缺失的边,可能使哈密顿(Hamilton)圈更容易被看出来,却并不改变哈密顿圈是否存在。如果这条边的两个端点的度之和已经足够大,那么一个使用了新边的圈可以被修补成只使用旧边的圈。反复进行这种安全操作,就得到一个闭包图。
闭包还解释了一个通过排序度序列表述的、不那么显然的充分条件。一个封闭的非完全图必然在互补的位置上暴露出一对度数不足。如果原图的度序列排除了每一种这样的不足,那么闭包就是完全图,原图是哈密顿图。
下文的判据都是充分性证书;闭包不完全,或度检验失败,都不被当作哈密顿性的完整否定判定。
定义
定义 4.2.1
(安全加边与闭包)
设 是 个顶点上的有限简单无向图。哈密顿圈恰好访问每个顶点一次,然后回到起点。对于不相邻的一对顶点 ,当它们的当前度满足 时,可进行一次合格的闭包加边,即连接 。
重复进行合格的加边,直到不再有可加的边为止。处于此停止点的图称为闭的:每一条剩余的非边,其端点度之和至多为 。度数和合格性是在演化中的图里重新计算的,而不是固定在初始值上。
定义 4.2.2
(度序列条件)
把原图的度按非递减顺序写成 。本笔记中的度序列条件是:对每个满足 的整数 ,
这两个选项属于同一个指标检验;要求两者同时成立,会是比定理所用条件更强的条件。该序列只记录度数,而不记录哪些顶点具有这些度数。
定理/命题
引理 4.2.3
(合格的边在两个方向上都保持哈密顿性)
若 不相邻且 ,则 是哈密顿图当且仅当 是哈密顿图。使用新边的哈密顿圈,可以沿所得的生成路径通过两条交叉边显式地转化为 中的哈密顿圈。
定理 4.2.4
(闭包与加边顺序无关)
所有极大的合格加边序列都得到同一个最终图,即 的闭包。图与其闭包同为哈密顿图或同不为哈密顿图。特别地,完全的闭包证明了哈密顿性,并可由此恢复原图中的一个圈。
用邻接矩阵的直接构造需要 次初等运算;一旦给出闭包中的一个圈,保存加边历史即可在额外 的工作量内恢复原图中的圈。这些是初等界,并不是最快实现的断言。
定理 4.2.5
(度序列条件保证存在哈密顿圈)
每个阶数至少为三且满足上述排序度条件的有限简单图都是哈密顿图。该条件在加边下是单调的,并且迫使其闭包为完全图。
作为推论,最小度至少为 蕴含哈密顿性,因为它使第一个选项在每个所需指标上都成立。度序列条件不成立,并不一定意味着哈密顿性不成立。
概念视角结构
闭包强化了表示,同时保持一个是非性质不变
安全加边可能改变图的许多特征,但保持哈密顿性。度序列提供了一个单调的充分检验,迫使这一被强化的表示变为完全图。正面的闭包证书可通过局部修补转移回原图;而否定性的结果没有可与之相比的、通向非哈密顿性的一般转移。
证明思路或证明
证明
(两条交叉边把生成路径闭合)
加边引理的一个方向是显然的:旧的哈密顿圈在扩大后的图中仍然存在。对于逆命题,取 中的一个圈。若它不含新加的边,则无需修补。否则去掉该边,得到一条生成路径
其所有的边都属于 。
在指标集 中,令 由使 与 相邻的指标 组成, 由使 与 相邻的指标组成。它们的大小分别是 和 :路径列出了所有顶点,而缺失的边使相对的端点不出现在任一邻点列表中。
它们的总大小至少为 ,超过了可用的 个指标,所以必有某个指标同时属于两者。该指标不可能是 或 ,否则就需要用到缺失的边。因此序列
是 中的哈密顿圈。它的两条交叉边来自这个交集,其余每条边都属于该生成路径。所有顶点在返回之前恰好出现一次。这样就构造性地证明了局部等价。
证明透视
邻点指标集必须在生成路径上重叠
度的假设只在从圈中去掉新加的边之后才被使用。剩下的是一条生成路径 ,其边都属于 ;只有沿这样的路径,邻点才能转化为指标。关键的一步是错开一位: 的邻点 记在指标 , 的邻点 也记在指标 。于是一个共同指标同时给出两条交叉边 与 ,再把 这一段反转,圈便闭合。
抽屉计数 正是门槛发挥作用之处。 不相邻这一点,用来排除共同指标为 或 ,因为两者都需要缺失的边。门槛不能降到 :在路径 中,两端点的度之和为 ,加入 得到三角形,但路径本身没有哈密顿圈。
为什么最终的闭包不依赖于选择
证明
(每个闭的母图都包含每次合格的加边)
每次加边都使度增加,而缺失的边只有有限条,所以每个合格加边序列都会终止。每一步由引理都保持哈密顿性。
设 是任意与原图同顶点且包含其全部边的闭图。任何合格序列中所加的每条边都必须属于 。沿该序列用归纳法证明这一点。较早加入的边由归纳假设属于 ,因此 中的度至少与下一条边变为合格时的度相同。若该下一条边不在 中,则它在 中的端点度之和仍然至少为 ,这与 是闭的矛盾。
把此结论应用于取 为另一序列的最终图。每个最终闭包都包含于另一个之中,从而相等。这也证明了闭包是一个良定义的图运算,而不仅仅是某一次任意执行的结果。
维护度数和邻接矩阵。对至多 个顶点对作一次完整扫描,可找到一条合格的非边,或证明不再有这样的边。加入它,更新它两个端点的度,然后重复。至多有 次加边,包括最后一次扫描在内总共需要 的工作量。矩阵使用 的存储,加边历史的大小量级相同。
如果闭包是完全图,则从其顶点的任一循环排列出发。按相反顺序处理各次加边。在每一步,从当前图中删去记录的那条边。若当前的圈不含它,则保留该圈。否则,在刚好加入该边之前的图中,应用引理中的路径修补。之后所有的加边都已被删去,因此修补只使用当前合法的边。借助矩阵查询,检验并重建一个圈及其交叉指标需要 的工作量,在整个历史上总共为 。
封闭的非完全图暴露出被禁止的度模式
证明
(度之和最大的非边使两个选项都不成立)
首先,加边时排序度条件得到保持。每个顶点的度都增加或保持不变,因此每个排序后的顺序统计量也是如此。例如,若新的第 小度小于旧的,则至少有 个顶点的新度低于该旧的阈值,而其中没有任何度减小;这与旧的排序矛盾。因此条件中的每个析取式仍然成立。
假设闭包 不是完全图。若它有孤立点,则每个度至多为 。在指标 处,第一个选项不成立,所要求的 同样不成立。因此满足该条件的图不可能出现这种情形。
否则,选取度之和最大的一对不相邻顶点 ,并标记使得 。不存在孤立点,所以 。闭性给出 ,从而 。
的每个非邻点(不含 自身)的度至多为 。若度更大,就会产生一条度之和比所选顶点对更大的非边。这样的顶点有 个。因此 中第 小的度至多为 。
同样, 的每个非邻点的度至多为 。这样的顶点有 个;再加上 自身,其度 同样至多为 。我们至少有 个度至多为 的顶点,所以第 小的度小于 。
度检验的两个选项在被允许的指标 处都不成立。这与原条件在取闭包下的保持性相矛盾。因此闭包必为完全图,再由局部等价定理,得到原图中的哈密顿圈。
最小度推论现在直接得出:若每个度都至少为 ,则对每个 ,连第 小的度也大于 。这样便通过更强的排序序列论证恢复了该充分条件,而不必把它当作未经证明的前提。
证明透视
为什么要在闭包中找矛盾
证明从不在原图中寻找不合格的指标。它先说明条件在每次加边后都保持,因此在闭包 中仍然成立,而 具有闭性可用。真正的想法是选取度之和最大的非边 :极大性把非邻点转化为度的上界, 的非邻点度至多为 , 的非邻点度至多为 。
闭性 一式两用:它保证 至少有 个非邻点;配合 ,又得到 ,所以 正是条件要检验的指标。单独处理孤立点的情形,只是为了保证 。
例题详解
例题 4.2.6
(初始非边和检验失败时,闭包仍可成功)
取 上的五顶点团,删去边 ,再添加第六个顶点 ,它只与 相邻。排序后的度为 。非边 的初始度之和为五,低于阶数六,所以要求每条原有非边都满足该界的条件不成立。
然而 是合格的,因为它的度之和为六。加入它之后, 的度为三,所以 和 可以加入;最后 也变为合格。闭包是完全图。度序列检验同样成功:仅有的指标是一和二,相应的度都大于这些指标。原图的一个哈密顿圈是 。
例题 4.2.7
(孤立点给出明确的早期序列失败)
取五个顶点上的团加一个孤立点,总阶数为六。其序列为 。在指标一处,第一个选项不成立,因为零不大于一;第二个选项也不成立,因为第五个度是四而不是至少为五。
每条非边都连接孤立点与一个度为四的顶点,所以没有一条是合格的。闭包仍不完全,并且该图不是哈密顿图,因为孤立点不可能位于生成圈上。在这里,两个否定性检验与另一个直接的障碍一致;这种一致并不是一般的逆定理。
例题 4.2.8
(把某一条具体的新加边修补回原图)
在第一个图中,只添加 。扩大后的图有圈 ,它使用了该新边。去掉它得到生成路径 ,其端点为 ,另一端点按引理的记号为 。
沿该带指标的路径,首端点的邻点指标集为 ,末端点的为 。它们共有的指标三给出修补后的圈 。所列的每条边都属于原图;新加的边 已经消失。
对于更长的加边历史,把同样的修补按相反顺序逐边应用。所维护的圈始终属于当前的图,所以最终输出只使用原有的边,而不会把闭包中的边当作一直存在的边。
常见错误
反例模式
非完全的闭包本身也可能是哈密顿的
五圈的每个顶点的度都是二。每条非边的度之和为四,低于五,所以其闭包不变且不完全。然而该图本身就是一个哈密顿圈。它的度序列检验在指标二处同样失败:第二个度不大于二,且第三个度低于三。两个检验都是充分的,而不是必要的。
常见错误
(把初始度数冻结)
检验加边时要使用当前的度。在第一个例题中, 起初度之和为五,未通过检验;要等 把 提高到三之后,它才变为合格。
常见错误
(把析取当成硬性要求)
不要把度序列的两个选项与对较大指标度的无条件要求互换。在最小度至少为 时,第一个选项在每个指标都成立,对 根本没有任何要求。
常见错误
(沿非生成的路径修补)
去掉所加的圈边而得到的生成路径,对于修补是必不可少的;任意的图路径未必包含所有顶点,把它闭合得到的圈会遗漏一些顶点。
总结
较大的端点度之和使得添加一条缺失的边对哈密顿性是安全的。反复加边得到与顺序无关的闭包,并可构造性地恢复圈。任何封闭的非完全图中度之和最大的非边,都迫使出现被禁止的排序度模式,由此证明了完整的度序列条件,并说明了失败检验的局限。
练习
快速检查
(直接证明:最小度至少为 使度序列条件中的每个指标检验都成立。)
所需的指标严格小于 。
解答 · 答案
每个排序后的度都至少为最小度,因而至少为 。对每个允许的整数 ,这使得 。因此第一个选项成立,无需检查第二个。度序列定理在此假设下证明了哈密顿性。
快速检查
(为什么添加其他合格的边永远不会使先前合格的缺失边变为不合格?仅凭这一点能证明每个停止图都相同吗?)
第一个问题用度的单调性,第二个问题用同顶点闭图的包含关系。
解答 · 答案
加边不会使任一端点的度减小,所以合格的边在被加入之前一直保持合格。要证明停止图的唯一性,须与任意与原图同顶点且包含其全部边的闭图作比较。归纳地,它必须包含合格序列中的每条边,否则其端点的度就会与闭性矛盾。取两个停止图分别作为比较的闭图,即证明相互包含。单调性提供了度的比较;闭性提供了矛盾。
快速检查
(在最大和非边的证明中,分别解释为什么至少有 个度至多为 ,以及为什么至少有 个度至多为 。)
分别数这两个不同所选顶点的非邻点; 自身只在第二次计数中计入。
解答
因为 ,顶点 至少有 个非邻点。每一个的度至多为 ,否则它与 构成的顶点对会超过所选的最大和。这给出第一个顺序统计量的界。
顶点 有 个非邻点,由同样的极大性,每个的度至多为 。再加上 自身,因为 ,其度 不大于 。这给出 个符合条件的顶点和第二个顺序统计量的界。二者合起来在指标 处使两个选项都不成立。