支配集

支配集的定义如下：给定无向图G =（V ， E），其中V是点集， E是边集， 称V的一个子集S称为支配集当且仅当对于V-S中任何一个点v， 都有S中的某个点u， 使得(u， v) ∈E。特别地，最小的支配集S（即任意一个比S小的集合都不可能是支配集）叫做最小支配集。支配集问题的两个变形。