动机
边密度不等式可以迫使大团出现,却无法对每个图判定团是否存在。要确定精确阈值,我们需要一个达到该界的图,以及一个证明:没有任何无团图的边数更多。当阶数不能被部分数整除时,构造中的有限取整就变得至关重要。
完全多部图提供了候选者。它们的团至多能从每个部分中选取一个顶点,而让各部分大小均衡会使跨部分的边数最大。一个删团归纳法证明了该候选者在所有图中是最优的,而等号情形则揭示了整个多部结构。
这一结果把未取整的密度估计加强为精确的计数与分类。
定义
定义 10.6.1
(完全多部图与均衡边数)
设 与 为整数。完全 部图是指其顶点被划分为 个部分,所有跨部分的边都存在,而部分内部没有边。允许空部分,这包含 的情形。当任意两个部分的大小至多相差一时,称其为均衡的。
写 ,其中 。均衡的大小为: 个大小为 的部分,以及 个大小为 的部分。它们的边数为
该表达式是整数,因为它计数的是位于不同部分的无序点对。本章中的图均为有限简单无向图。
团是指由两两相邻的顶点构成的集合。若一个图没有该大小的团,则称其为 -free(不含 )。其独立数是不含任何边的顶点集的最大大小。这里的极值图是指在给定阶数下边数尽可能多的无团图。
图同构允许对顶点重新标号。等号情形的分类只在这种重新标号的意义下确定图,并不强制已有顶点集上存在某个特定的带标号划分。
定理/命题
定理 10.6.2
(均衡化唯一地使多部图的边数最大)
在 个顶点的完全 部图中,最大边数为 ,且恰好在各部分大小均衡时取到。对 ,
对 且 ,还有 。
定理 10.6.3
(精确的无团阈值及全部等号情形)
每个 个顶点的 -free 图至多有 条边。等号成立当且仅当该图是均衡完全 部图(在顶点重新标号及允许空部分的意义下)。
因此,边数多于 就必然含有大小为 的团。反向的判定命题是错误的:低于阈值的图仍可能含有该团。
定理 10.6.4
(互补的独立集问题有精确的最小值)
一个 个顶点且独立数至多为 的图至少有 条边。等号成立当且仅当该图是 个均衡团的不交并(允许空团)。
因此,同一个极值计数既度量了避免大团的最大边集,也度量了禁止大独立集的最小边集,图的补运算在两个问题之间互相交换。
证明思路或证明
证明
(均衡化与多部图递推)
对于和为 的各部分大小 ,跨部分边数为 。设有两个大小满足 。把一个顶点从较大的部分移到较小的部分,它们的平方和由 变为 ,减少了 ,从而边数增加。
重复这一有限的均衡化操作。每个不均衡的大小模式都可以被改进;每个均衡的模式都具有所示的 大小,因而边数相同。这就证明了最大值以及所有多部图的等号模式。展开其平方和即得公式的两种形式。
当 时,每个均衡的部分都非空。从每个部分中各删去一个顶点,剩余部分在 个顶点上仍是均衡的。被删去的顶点构成一个 团,而每个留存的顶点恰与其中 个顶点相邻。计数被删去的边即证明了定理中的递推式。
关于部分参数的严格递增:从 个顶点上的均衡 部图出发。至少有一个部分的大小不小于二。把该部分拆成两个非空部分,便得到它们之间乘积那么多的正数条新边,且至多使用 个部分。继续均衡化只会使结果进一步增大。因此,其原有最优边数严格小于 。
用两个相互关联的归纳证明极值上界
证明
(删团归纳)
的情形是显然的:不含二团的图没有边,恰是单部构造。对于更大的 ,假设定理的上界已对参数 在每个阶数上得证,并对 用归纳法证明当前的 。
若 ,则顶点数不足以容纳被禁止的团,最大的图是完全图,有 条边。现设 。若图中不含 团,则参数 的界给出边数至多为 。这一分支以严格不等式得到解决。
否则取一个大小为 的团 。 之外的任一顶点在 中至多有 个邻点,因为若与它们全部相邻就会产生一个 团。其余 个顶点上的图仍是 -free 的。于是对阶数的归纳将总边数界定为
每次调用要么使用更小的部分参数,要么在同一参数下使用更小的阶数。因此这两重归纳是良基的,并在每个阶数上证明了上界。均衡构造是无团的,因为团在每个独立部分中至多使用一个顶点,所以它达到了这个界。
等号迫使图本身是均衡多部图
证明
(等号重构各部分)
对于 ,等号情形是无边图。若 ,等号要求所有可能的边都存在,即由 个单点部分及其余空部分表示的完全图。考虑剩下的情形 。
无 团的分支严格低于该界,所以等号图含有这样的团 。边数取等迫使每个 外的顶点在 中恰有 个邻点,因此它恰好漏掉其中一个顶点。
把每个外部顶点划入其唯一未相邻顶点 所在的部分,同时也把 放入该部分。被划入同一部分的两个外部顶点不能相邻。若它们相邻,这两个顶点连同 中其余 个顶点就会构成一个 团。按定义,二者都不与各自被指派的 相邻,所以得到的每个部分都是独立的。
因此原图是这些部分上的完全 部图的子图。由均衡化定理,该完全图至多有 条边,而原图已恰有这么多条边。所以每条允许的跨部分边都必须存在,且各部分必须是均衡的。这就证明了完整的等号分类,而无须假设较小的导出子图的分类会自动控制被删去的团如何连接。
证明透视
删团归纳如何紧到足以完成分类
两个归纳同时进行:对没有 团的分支,对部分参数 归纳;对有 团的分支,对阶数 归纳。第一个分支需要均衡化定理中的严格不等式 ,正是这种严格性后来把它排除在所有等号情形之外。在第二个分支中,图无 这一假设对每个外部顶点各用一次:它把连向 的边数限制为至多 。恒等式 于是使三部分计数恰好相加为 。
等号需要的不止数值归纳。在所选团处取等,使每个外部顶点恰好缺失 的一个顶点,而这种模式命名了各部分。禁止团的条件第二次被用到,是在每个拟定的部分内部,使它成为独立集。只有这样,均衡化定理才把“包含于完全 部图中”提升为“等于均衡的完全 部图”;无须用较小导出子图的分类去控制 如何连接。
将精确结论转移到独立集
证明
(补图转换)
一个集合在图中是独立的,当且仅当它在简单补图中是团。因此,独立数至多为 意味着补图是 -free 的。对补图的 条边应用上界并整理,即得 的下界。
对等号图取补,会去掉所有跨部分的边并把每个部分内部补满,得到不交的均衡团。反过来,该并集的独立数至多等于其非空团的个数,因而至多为 ,且它达到所述的边数。这就证明了互补等号命题的两个方向,包括 时极值图为无边图的情形。
该阈值能判定什么,不能判定什么
由整数除法计算 是直接的,而边数更多的图必定含有可证明存在的大团。该定理并没有说边数更少的图都是无团的。要检测实际的团,或解释密度检验的失败,还需要其他论证。
对固定的 ,枚举所有 个顶点的集合并检查其点对,是关于 的多项式时间的有限搜索,指数依赖于 。这一观察并不是对以二进制编码的可变阈值一致成立的多项式界。该极值定理是一个精确的结构性陈述,其存在性证明并不能消除一般团算法中输入模型的区别。
例题详解
例题 10.6.5
(八个顶点且禁止四团时,边数至多二十一)
取 。均衡大小为三、三、二。其跨部分边数为 。每个不含四团的图至多有二十一条边,而等号恰好要求这种完全三部图的形状。
因此二十二条边就迫使出现四团。在互补的独立集问题中,要迫使独立数至多为三,至少需要 条边;大小为三、三、二的均衡团并集的边数为 。
例题 10.6.6
(奇数阶的无三角形界保留了取整)
对于七个顶点且 ,均衡部分的大小为四和三,得到十二条边。未取整的密度项是 ,而修正量为四分之一,从而整数最优值为十二。
每个有十二条边的无三角形图,在重新标号意义下都是完全二部图 。十三条边就迫使出现三角形。精确的分类给出的信息,多于在忘记其等号条件之后对粗略估计简单地向下取整。
例题 10.6.7
(可用部分数多于顶点数时不会出现例外公式)
对于三个顶点且 ,取三个单点部分和两个空部分。均衡图是 ,有三条边,且不可能含有被禁止的六团。
公式中商为零、余数为三,同样给出三。其补图是三个孤立点,可表示为大小为一、一、一、零、零的五个均衡团部分。其独立数为三,确实至多为五。允许空部分使两个等号命题在这一边界处保持一致。
概念视角组合
最大化允许的边数同时也揭示了禁团的边界
均衡多部构造把边花在部分之间,同时阻止团在同一部分内取两个顶点。归纳证明了没有任何其他排布能花费更多的边。在取等时,每个外部顶点在所选 团中唯一缺失的邻点重构了这些部分,使得极值形状成为一个结论,而不是一幅凭空猜测的图。
常见错误
反例模式
低于阈值并不意味着图是无团的
一个三角形加上三个孤立点只有三条边,远低于 ,但它仍含有三角形。该定理说的是无三角形图的边数不能超过九,或等价地说,多于九条边就迫使出现三角形。它并没有把每个更小的边数都变成不存在三角形的证明。
常见错误
(恰好等于阈值并不迫使团出现)
在迫使性陈述中要保持严格不等号,在极值上界中要保持非严格不等号。 恰有 条边而没有三角形,所以“七个顶点上的十二条边迫使三角形出现”是错的;要十三条或以上才行。
常见错误
(单凭边数不能确定图)
等号分类只有在已知图无团之后才适用。一个三角形加一条悬挂边有四个顶点和 条边,却不是 ,因为它含有三角形。
常见错误
(多部图与团的不交并回答不同的问题)
均衡完全多部图与不交团并并不相同;补运算在这两种结构之间互相交换。在四个顶点、 时, 有四条边,是最大的无三角形图;两条不相交的边则是独立数至多为二的最小图,有 条边。把两个答案互换,得到的图对两个问题都不是极值图。
总结
均衡化各部分大小给出了精确的整数候选者及其修正项。删团归纳法证明了全局极值上界,而与所选团的紧密连接迫使每个等号图都是均衡多部图。取补得到精确的最少边独立集对应结论,而否定性的密度检验仍然是不确定的。
练习
快速检查
(求十个顶点的无四团图的精确边数上界。写出等号情形的形状,以及独立数至多为三时的互补最小值。)
把十均衡地分成三部分。
解答 · 答案
该界为 。等号要求具有这些大小的完全三部图。三十四条边就迫使出现四团。
互补最小值为 ,恰好由大小为四、三、三的不交团取到。它们的内部边数分别为六、三、三,总计十二,而任何独立集在每个团中至多使用一个顶点。
快速检查
(通过从每个均衡部分中各删去一个顶点,解释 的递推式,并对 、 验证之。)
计数被删去的团及其与留存顶点之间的所有边。
解答 · 答案
被删去的 个顶点构成一个团,有 条边。其余 个顶点中的每一个,都与除自己所在部分对应的那个以外的所有被删顶点相邻,贡献 条跨部分边。剩余部分仍是均衡的,于是得到递推式。
在 时,,,差为十三。按所计数的类别得 ,符合要求。
快速检查
(在等号证明中,为什么缺失同一个团顶点的两个外部顶点必然不相邻?为什么最终的边数迫使所有跨部分边都存在?)
在调用均衡化之前,先使用团中其余 个顶点。
解答 · 答案
若两个这样的外部顶点相邻,它们与团中其余 个顶点就会两两相邻,产生大小为 的被禁团。因此,它们被指派的部分(包括其缺失的那一个团顶点)是独立的。
该图包含于这些部分上的完全多部图中。它的边数已经等于任何此类部分大小下所能达到的最大边数。若缺少某条允许的跨部分边,则包含它的多部图的边数就会严格大于该最大值。因此一条也不缺,而均衡化结果中的等号迫使各部分大小至多相差一。