9.1 支配集、点独立集与覆盖集

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【本章范围与符号】第9章依次讨论支配集、覆盖集、独立集、匹配与着色。前3节对有限无向简单图讨论;着色一节另行说明无自环的条件。本书用 表示支配数, 表示点独立数, 表示点覆盖数。不同书的记号可能不同,本章始终按这里的约定使用。

【定义9.1.1:支配集】设 ,。若每个 都至少与 中一点相邻,称 为支配集。集合内部的点不要求另有邻点,可以理解为在所选站点自身已有服务。用闭邻域表示,就是 。

若 的任何真子集都不再支配全图,称极小支配集;全图所有支配集中顶点数最少者称最小支配集,其大小为 。极小只表示“不能再删除”,最小表示“全局数量最少”。最小必极小,极小未必最小。

例如工作站网络中,边表示两站可直接通信。把数据库副本放在 中的工作站上,要求每站自己有副本或直接邻接一个有副本的站,正是支配集条件;使副本数最少,则要求最小支配集。这里不把经过多条边才能到达的站当成直接获得服务,否则就改成了别的问题。

v1v2v3v4v5v6v7
图9.1.1(a):七个带标号顶点;中央圆点把经过它的线段分为不同边

图(a)中 都是极小支配集。前三个都是最小支配集,:它们能支配全图,而图中没有与其他六点全部相邻的单个顶点,故不能只选一点。最后一集有3点,仍不能任删一点,所以它极小但不最小。

v0v1v2v3v4v5v6
图9.1.1(b):七阶星,v0为中心

图(b)的 与 都极小:删掉中心就没有服务点;若只选所有叶点,删掉任何一个叶点后,它自己既未被选中,也不邻接其他叶点。最小者为 ,。

v0v1v2v3v4v5
图9.1.1(c):六阶轮图W6,v0为中心,外围五点依次成圈

图(c)中 等都极小,但只有大小1的中心点集最小,所以 。本书 的下标是总顶点数,外围是五边形。

【定义9.1.2:点独立集】 中任意两不同顶点均不相邻,称点独立集,简称独立集。再加入任一外部顶点都会破坏独立性者称极大独立集;所有独立集中大小最大者称最大独立集,其大小为 。极大不等于最大,判断极大要逐一检查是否还能加入外部顶点,不能仅凭当前集合中没有边。

图(a)中 、、 都是极大独立集,最后一集大小3,为最大独立集,。前两个只有2点,不能再加点但不是全局最多。图(b)中中心单点和全部六叶点都极大,全部叶点最大,。图(c)中 、 都是最大独立集,:独立集若含中心只能含它自身;若不含中心,则是五边形的独立集,至多2点。

【定理9.1.1:极大独立集给出极小支配集】教材在无孤立点的条件下叙述:图的每个极大点独立集都是极小支配集。设 极大独立,若某个外部点不邻接 中任一点,就可把它加入 ,矛盾,故 支配全图。再从 删除任一点 , 既不再被选中,也不邻接剩余独立集中的点,故失去支配性,所以 极小。

这个证明实际上允许孤立点:极大独立集必包含全部孤立点,因此不需无孤立点假设也成立。逆命题不成立,图(a)的 是极小支配集,但 本身就是边,故不是独立集。

【定义9.1.3:点覆盖】 若与每条边的至少一个端点相交,称点覆盖。极小点覆盖不能再删除顶点;最小点覆盖在全图所有点覆盖中顶点数最少,其大小记为 。点覆盖要覆盖的是所有边,不是直接覆盖所有顶点,孤立点不必选入。

图(a)中 与 都是极小点覆盖,后者为最小者,。图(b)中中心单点与六叶点均极小,中心最小,。图(c)中 、 都是最小点覆盖,。

【定理9.1.2:点覆盖与独立集互补】对任意无向简单图及 ,

若补集中存在一条边,其两端均不在 ,则这条边未被覆盖;反过来,若补集独立,每条边至少有一端在 ,所以 覆盖全部边。教材同样带了“无孤立点”的假设,但此处的等价和下面的推论对含孤立点的简单图仍成立。

【推论9.1.1】集合 是极小点覆盖,当且仅当其补集是极大独立集; 是最小点覆盖,当且仅当其补集是最大独立集。因为删除覆盖集中的一点,正对应向独立集加入这一点;两种集合大小之和恒为 ,所以

图(a)、(b)、(c)分别验证为 、、。这是一对“最少覆盖顶点”和“最多独立顶点”的互补关系,不应与支配数相混。