支配集

支配集（dominating set）是一个顶点集合，使每个未被选中的顶点都至少有一个已选邻居。已选顶点由自身覆盖，因此它表达“每个顶点要么被选中，要么与已选点相邻”。最小支配集大小称为支配数，记为 $\gamma (G)$。

在边为 $ab,ac,bc,cd,de$ 的五顶点图中，选择 $D=\{c,e\}$。未选点 $a,b$ 都邻接 $c$，未选点 $d$ 邻接 $c,e$；所选两点由自身满足条件，因此它是一个支配集。

每个未选点只需有一个已选邻居；c、e之间没有边也不影响支配性。

闭邻域表达定义

对无向简单图，记 $N(v)$ 为邻居集合，$N[v]=N(v)\cup \{v\}$ 为闭邻域。那么 $$D\text{支配}G⟺\bigcup _{v\in D}N[v]=V.$$ 主例中 $N[c]=\{a,b,c,d\}$，$N[e]=\{d,e\}$，二者并集正好是五点全集。定义使用闭邻域，是为了让已选顶点无须另找邻居。若要求已选点也必须有已选邻居，得到的是全支配集，属于另一个概念；孤立点使全支配集不存在，却只是要求普通支配集必须选入该孤立点。

非空图的支配数至少一，全部顶点总能支配，所以 $1\le \gamma (G)\le n$。若存在与其他所有点相邻的全邻接顶点，一个点便可支配全图；反过来，一个点能支配全图也说明它与其余所有点相邻。主例最大度只有三，少于 $n-1=4$，所以不存在单点支配集。加上 $\{c,e\}$ 的上界，得到 $\gamma (G)=2$。

极小性与私有见证

一个支配集若删去任一已选点便不再支配，称为极小支配集；大小最少者才是最小支配集。为精确判断极小性，对每个 $d\in D$ 寻找一个顶点 $x$，使 $$N[x]\cap D=\{d\}.$$ 这个 $x$ 称为 $d$ 相对于 $D$ 的私有邻居或私有见证，允许 $x=d$。它表示：当前只有 $d$ 能支配 $x$。

命题。 支配集 $D$ 极小，当且仅当它的每个点都有这样的私有见证。

证明。 若每个 $d$ 都有见证 $x$，删去 $d$ 后 $N[x]$ 与剩余集合无交，故 $x$ 不再被支配，任何一点都不能删。反过来，若 $D$ 极小，删去 $d$ 后必有某个 $x$ 失去支配。删前 $D$ 支配 $x$，删后只有 $d$ 消失，因此删前与 $N[x]$ 相交的点恰为 $d$，得到所需见证。

主例的 $\{c,e\}$ 中，$a$ 可为 $c$ 作见证，因为 $N[a]\cap D=\{c\}$；$e$ 为自身作见证，因为 $N[e]\cap D=\{e\}$。这证明它极小；其最小性仍依赖前面排除单点方案的下界，不能只靠私有见证断言。

在四叶星图中，全部四片叶子构成极小支配集，每片叶子为自身作见证；中心单点却已是最小支配集，大小一。极小与最小的差距可以随图规模增长。

度数下界与独立集

若最大度为 $\Delta$，每个已选顶点的闭邻域最多含 $\Delta +1$ 个点。支配集的这些闭邻域覆盖 $n$ 点，故 $$n\le \sum _{d\in D}\mathrm{\#}N[d]\le \mathrm{\#}D(\Delta +1),\gamma (G)\ge \lceil \frac{n}{\Delta +1}\rceil .$$ 邻域可能重叠，求和只会高估总覆盖数，因而仍给出有效下界。主例下界为 $\lceil 5/4\rceil =2$，与实际值相等。

每个极大独立集都是支配集：若某个外部点没有已选邻居，就能加入独立集，违反极大性。因此 $\gamma (G)\le \alpha (G)$。逆向并不成立，支配集内部可以相邻；主例的 $\{c,d\}$ 也支配全图，却含有边 $cd$。

变式。 给主例增加孤立顶点 $f$。任何支配集都必须包含 $f$；其他五点之间的支配关系不变，所以支配数恰从二增加到三。最小集合可取 $\{c,e,f\}$。这个变化不能通过给 $f$ 指派一个远处的已选点解决，因为定义只允许距离至多一。

普通支配集也不要求每条边有已选端点。例如三角形内选一点可支配全部三点，但未选两点之间的边仍未被端点覆盖。覆盖边的条件见顶点覆盖，不应与覆盖邻域的条件混用。