形式上,支配集可描述如下:给定无向图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。