形式上,支配集可描述如下:给定无向图G =〈V , E〉,其中V 是大小为n 的点集, E 是边集, 那么V 的一个子集S称为支配集当且仅当对于V - S 中任何一个点v ,都有S 中的某个定点u , 使得( u , v) ∈E。

支配集问题的两个变形。

定义1 在图G=〈V , E〉中,V 的一个子集S 称为C 强支配集( C 是某个固定的常正整数) 当且仅当对任何一个大小不

小于| S| - C 的S 的一个子集S′,对于V - S 中任何一个顶点v ,都有S′中的某个定点u ,使得( u , v) ∈E。

定义2 在图G=〈V , E〉中,V 的一个子集S 称为完全支配集当且仅当对于V 中任何一个点v ,都有S - { v} 的某个点

u ,使得( u , v) ∈E。

1 支配集

D是图G=<V,E>的一个顶点子集，对于G的任一顶点v，要么v属于D，要么与D中的一个顶点相邻，则D称为图G的一个支配集。若在D集中去掉任何元素后D不再是支配集，则称D是极小支配集。称图G的所有支配集中顶点个数最少的支配集为最小支配集，最小支配集中的顶点个数称为图G的支配数。

如何求G的所有极小支配集合？

对符号X,Y,Z，定义两种运算X+Y（加法运算，或运算）和XY（乘法运算，与运算），满足以下运算定律：

交换律：X+Y = Y+X; XY = YX

结合律：(X+Y)+Z = X+(Y+Z); (XY)Z = X(YZ)

分配律：X(Y+Z) = XY+XZ

吸收律：X+X = X; XX = X; X+XY = X

求所有极小支配集的公式：

一个顶点与它相邻的所有顶点进行加法运算组成一个因子项，n个因子项再相乘。连乘过程中根据上述运算规律展开成积之和的形式。每一积项给出一个最小支配集。

(1 + 2 + 3 + 4)(2 + 1 + 4)(3 + 1 + 4)(4 + 1 + 2 + 3 + 5 + 6)(5 + 4 + 6)(6 + 4 + 5)

=15 + 16 + 4 + 235 + 236

故极小支配集为

{V1, V5}, {V1, V6}, {V4}, {V2, V3, V5}, {V2, V3, V6}