引言
我们假设读者熟悉有限简单无向图、顶点的度、路径,以及将图中的一些边替换为另一些边的想法。
问题很容易提出:给定一个有限整数列,例如 ,是否存在一个简单图,其顶点的度恰好是这些数?如果存在,怎样构造这样的图?
有些序列因明显的原因不可能实现,有些则需要更细致的分析。Havel–Hakimi 定理能解决每一种情形:它把长度为 的序列的问题化为长度为 的同类问题。这个化简是构造性的,因此只要存在符合要求的图,它也能给出一个。
可图化序列
本节中的图都是有限简单无向图,没有自环或重边。记 为一个有 个带标号顶点的集合。
定义 8.2.1
(可图化序列与实现)
设 , 是整数列。如果存在顶点集为 的简单图 ,满足
则称 可图化。这样的 称为 的一个实现。
定义中有三点值得注意。
- 空序列可图化。 当 时,空图没有顶点,关于其顶点的所有条件均空真成立。
- 全零序列可图化。 长度为 的 由 个顶点且没有边的图实现。
- 标号有意义,但重新标号不改变可图化性。 第 项 指定顶点 的度。若 是 的置换,则 可图化当且仅当 可图化:只需重新标记一个实现的顶点。因此排序不改变可图化性;但如果要构造原标号下的实现,就必须记录每一项对应的顶点。
含负数的序列不可图化,因为度数计算的是边数,至少为 。
两个必要条件
假设 可图化, 是它的一个实现, 有 条边。
命题 8.2.2
(度数的必要条件)
若 可图化,且它的实现 有 条边,则
所以各项之和是偶数;并且
证明
(数边的端点与可能的邻居)
握手定理给出的奇偶性。 每条边对其两个不同端点的度各贡献 ,所以各度数之和是边数的两倍。
度的界。 简单图的顶点 只能与另外 个顶点相邻,且每个最多相连一次。
两者都是必要条件。单独满足任一条件不充分,同时满足两者也不充分。
反例模式
各项有界且和为偶数,仍不可图化
取 ,。各项之和为偶数 ,每项都介于 和 之间,两个必要条件均成立。
假设 是一个实现。顶点 的度为 ,故它与 全部相邻; 同理,与 全部相邻。于是 同时与 和 相邻,故 ,这与 矛盾。所以 不可图化。
由此可见,奇偶性与度界只是局部的计数约束,可图化性还取决于大度数之间如何相互影响:两个大度顶点会迫使其他顶点与它们相连。
Havel–Hakimi 定理
直觉是贪心的:先满足需求最大的顶点,并把它连接到剩余需求最大的顶点,因为后者往往最难在之后满足。固定这些边后,这个顶点的需求已经满足,可以删除,剩下一个较短的剩余需求序列。
定理 8.2.3
(Havel–Hakimi 定理)
设 ,整数列 满足
定义长度为 、指标为 的剩余序列 :
也就是说,删除 ,并把接下来的 项各减 。那么 可图化当且仅当 可图化。特别地,如果 含有负数,则 不可图化。
条件 保证 ,因此 都存在。剩余序列不一定有序;排序不改变可图化性,因此再次使用定理前可先排序。
证明
记 ,,则 。证明只用到 的以下性质: 中每个顶点的度,至少与 外每个顶点的度一样大。
证明
(加入顶点;换边后再删去)
逆向( 可图化 可图化)。 设 是 在 上的一个实现,即 。因为 可图化,其各项非负。在 中加入新顶点 ,再加入 条边 ,其中 ,得到 。
新边的另一端互不相同,因此它们互不相同;,因此没有自环; 是新顶点,因此这些边原先不存在。所以 是简单图。在 中, 的度为 ;每个 的度是 ;其他顶点的度仍为 。故 实现 。
正向( 可图化 可图化)。 首先证明 存在一个实现满足 ,其中 表示 的邻居集合。
关键步骤:一次换边。 设 是 的任意实现,且 。由于 ,存在 ,也存在 。于是 ,;又因为 而 ,所以 。
令 ,。无论 是否为边,两个度数都减去相同的修正量,因此
现在 不含 (没有自环),不含 (由定义),也不含 (因为 ),故 。另一方面,,所以 。因此 在 内的邻居组成 ,其大小为 。
所以 。存在顶点 满足:
- 与 相邻;
- 与 不相邻;
- 。
四个顶点 两两不同。在 中:
- 和 是边;
- 和 不是边。
删去 和 ,加入 和 ,得到 。
仍是简单图: 且 ,所以新边不是自环;它们原先都不存在,且彼此不同。各顶点的度不变:
- 失去邻居 ,得到邻居 ;
- 失去 ,得到 ;
- 失去 ,得到 ;
- 失去 ,得到 。
所以 仍实现 。
进展。 的邻居只发生两处变化:移除 ,加入 。原先已在 中的邻居都保留,且
最多为 ,因此重复换边,至多经过 次便得到 的一个实现 ,满足 。
删除。 从 删除 。每个 恰好失去一个邻居,其他顶点不失去邻居。所得简单图的顶点集为 ,各顶点度为 。因此 可图化。特别地,若 可图化,则 不含负项。
证明透视
最大度数的选择用在哪里
逆向只是记账:一个连到 的新顶点恰好把先前减去的度数加回去。全部内容都在正向,而且集中在一步:保持度数不变的换边,把边 换成 。
“ 由剩余度数最大的顶点组成”这一假设只用了一次,就是 。它的作用是找出第四个顶点 :由于 , 在 以外必有一个邻居不是 的邻居。没有这个不等式, 未必存在。在关于减去较小项的练习中,取 与路径 ,选 、 便得 ,无法换边。
四个顶点互异,以及两条边、两条非边的模式,保证 仍是简单图且度数不变。每次换边使 增加一,而它至多为 ,所以过程终止。论证说明的是:贪心选出的邻域总能成为某个实现的一部分,而不是每个实现都包含它。
相同度数、终止性与构造算法
相同度数。 如果有多个项等于 ,可以任意选一个对应顶点作为 。如果 且边界处有相同项,即 ,可以任选剩余度数最大的 个顶点减一。证明只用到 中每个顶点的度至少与 外的每个顶点一样大。因此“可否图化”的判断不依赖如何处理相同项,但构造出的图可能不同。
带标号实现算法。 维护一个由(剩余度数,顶点标号)组成的列表,以及初始为空的边集 。
- 输入检查。 如果某项为负,或某项超过 ,则拒绝。如果 ,接受并输出 。
- 若所有剩余度数均为 ,则接受并输出 ;这包括列表已变空的情形。
- 按剩余度数从大到小排列各对。设第一对为 ,当前有 对;若 ,则拒绝。
- 移除 。对其后的 对 ,分别将 改为 ,并把边 加入 。
- 若出现负的剩余度数,则拒绝;否则返回步骤 2。
终止性。 每次执行步骤 4 都使列表缩短一项,故至多执行 次。
正确性。 对列表长度归纳,每一步应用定理。还需注意:
- 是简单图的边集。 一旦移除就不会再出现,因此该步记录的每条边都把 连到一个不同的、仍在列表中的顶点。没有边被重复记录。
- 给出正确的度数。 固定顶点 ,设它被移除时剩余度数为 。它此前已得到 条边,在自身步骤中再得到 条,总计 条。若 从未被移除,接受时其剩余度数为 ,因此它已得到全部 条边。
输入检查之后,步骤 3 实际上不会触发:不变量是当前列表长度为 时,每个剩余项至多为 。初始时这正是输入的度界。若最大项 ,则每个剩余项至多为 ,故至多为 ;若 ,所有其他项都减一,也至多为 。所以在下一次长度为 时仍满足该界;步骤 5 另行拒绝负数。保留步骤 3 的检查并无妨碍。
运行时间。 将大小至多为 的度数的比较和算术运算视为单位开销,添加每条边的均摊开销为常数。每次使用耗时 的比较排序;每次还需要 次减一和插边操作,且至多执行 次。总耗时为
输出至多有 条边,也在此上界内。这是一个简单的多项式上界,我们不声称它最优。
概念视角组合
用不等式作凭证,而非逐步删点
对总和为偶数的非递增序列,可图化也等价于一组共 个不等式,即 Erdős–Gallai 条件:
必要性来自统计 上的边端:这些顶点之间的边至多贡献 ,每个外部顶点 至多贡献 。对 取 ,不等式变为 ,并不成立。算法构造实现;一个不成立的不等式则证明实现不存在。
例题
例题 8.2.4
(可图化序列及明确的边集)
设 对应 。度数之和为 ,故若存在实现,它有 条边。
- 第 1 轮。 移除 (度为 ),将 的剩余度数各减一。记录边 。剩余:。
- 第 2 轮。 排序为 。移除 ,将 减一,记录 。剩余:。
- 第 3 轮。 排序为 。移除 ,将 减一,记录 。剩余 ,全为零,接受。
边集为
检查各顶点的度:
- 与 相邻,度为 。
- 与 相邻,度为 。
- 与 相邻,度为 。
- 与 相邻,度为 。
- 与 相邻,度为 。
共有 条边,正如预期。
下面的互动图在度序列上逐轮重演带标号的 Havel–Hakimi 算法,结果是一个已验证的边集,或是证明序列不可图化的负剩余度数。
例题 8.2.5
(偶数和序列因出现负项而被拒绝)
再看 。
- 第 1 轮。 移除 (度为 ),将 减一,得到 。
- 第 2 轮。 排序为 。由于 ,通过度界检查。移除 并将 减一,得到 。
出现负项,所以 不可图化。由定理, 也不可图化,与前面的直接论证一致。
负项的具体含义是:若要满足 和 ,则 和 将不得不接受超过其要求数量的边。
例题 8.2.6
(同一序列的非同构实现)
令 。
- 第 1 轮。 移除 ,将 减一,记录 。
- 第 2 轮。 排序后先是 (各为 ),再是 (各为 )。移除 ,将 减一,记录 。
- 第 3 轮。 的剩余度数均为 。移除 ,将 减一,记录 。
- 第 4 轮。 剩余 。移除 ,将 减一,记录 。剩余项全为零,接受。
输出是两个不相交的三角形,顶点分别为 和 。
六边形圈 也实现 。这个圈是连通的,而两个三角形组成的图不连通,因此二者不同构。
可图化序列不能决定什么
须区分三个概念。
- 可图化性。 它是序列的一个是非性质,定理能判定它。
- 带标号的实现。 即使每个标号顶点的度固定,也可能有多个实现。 恰有三个带标号实现,分别对应 的三个完美匹配。这三个带标号图不同,但互相同构。
- 同构类型。 度数的多重集不能唯一决定图的同构类型,前面关于同一列表的非同构实现的例子已经说明。反过来, 和 的多重集相同,但标号不同;它们分别由路径 和 实现,作为带标号图不同,作为图则同构。
可以:同一带标号序列的任意两个实现,都能通过有限次保持度数的换边互相转化。
自然的下一个问题
任意两个实现能否通过换边互相转化?
可以:同一带标号序列的任意两个实现,都能通过有限次保持度数的换边互相转化。
正向证明已经完成了大部分工作。设 与 都实现 ,换边可以把两者分别变成 的邻域恰为 的实现。删去 后得到 的两个实现;对 归纳,它们可由不涉及 的换边连接。再把作用在 上的换边倒序还原,就得到从 到 的换边序列。特别地,前面两个不相交的三角形与六边形圈也是这样连接的。
常见错误
前文已遇到两种错误:误以为奇偶性和度界已经充分, 已给出反例;以及允许自环或重边,而本节所有图都排除它们。
常见错误
(减错项)
定理要求把接下来的 个最大项减一。关于减去较小项的练习说明,若减去较小的项,可能错误地拒绝一个可图化序列。
常见错误
(忘记重新排序)
剩余序列可能不再有序,下一轮必须从最大项开始。在第一个例题中,剩余 必须重新排序,第二轮才会把 减一。
常见错误
(换错边)
换边是删除 和 ,加入原先不存在的 和 。删除 没有意义,因为它不是边。
练习
快速检查
(判断 是否可图化。)
解答
各项和为偶数 ,各项均不超过 。
- 第 1 轮。 删除 ,把接下来的四项减一,得到已排序的 。
- 第 2 轮。 删除 ,把接下来的三项减一,得到 。
出现负项,所以原序列不可图化。
也可直接论证:五个顶点中有两个度为 ,它们均与所有其他顶点相邻。于是剩余每个顶点的度至少为 ,但 。
快速检查
(证明 可图化。用算法构造带标号实现,并检查每个度数。)
解答
- 第 1 轮。 移除 (度为 ),将 减一,记录 。剩余 的度均为 。
- 第 2 轮。 移除 ,将 减一,记录 。剩余 。
- 第 3 轮。 排序为 。移除 ,将 减一,记录 。剩余项全为零,接受。
边集为
逐一检查:
- 与 相邻,度为 。
- 与 相邻,度为 。
- 与 相邻,度为 。
- 与 相邻,度为 。
- 与 相邻,度为 。
共有 条边,与度数和 一致。
快速检查
(设 。证明任何由 个两两不同整数组成的序列都不可图化。)
解答
假设 可图化且 个项两两不同。每项均属于恰有 个元素的集合 。由于这 项不同,集合中的每个数都出现。特别地,存在顶点 的度为 ,顶点 的度为 ;由于 ,二者不同。
与所有其他顶点相邻,包括 。因此 ,矛盾。
快速检查
(序列 可图化,请证明。然后将 连到 和 ,而不是连到剩余度数最大的顶点,证明所得剩余序列不可图化,并解释为何这不与定理矛盾。)
解答
路径 在 处的度分别为 ,故 可图化。
现在将 连到 和 ,剩余序列为 ,即 。对它应用定理得到 ,所以 不可图化。
这并不矛盾。定理只保证把 连到 个最大度数顶点时的等价性;这里应连到 和 中的一个。这样得到 或 ,二者均可图化。正向证明需要对 、 有 。若 ,集合外的 度严格更大,因此换边论证不适用。