支配集問題的兩個變形。
定義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}
