控制集(dominating set),理学-数学-图论-图的同构,设是图的一个顶点子集,如果对图中任意的顶点都有或者与中的某个顶点相邻,则称为图的一个控制集。如果是图的一个控制集,但的任何真子集不再是的控制集,则称为的极小控制集(minimal dominating set)。顶点数最少的控制集称为最小控制集(minimum dominating set),其顶点数称为图的控制数(dominating number),记成。由极大独立集和极小控制集的定义,容易看出:任何图的极大独立集必为的极小控制集,以及图的控制数不会超过顶点覆盖数,即。对于图中的任意一个点,它最多能控制个顶点,其中表示图的最大度,因此。阿诺托(Arnauto)(1974)和帕扬(Payan)(1975)分别证明了如下结果:给定个顶点的图,如果的最小度为,则包含一个大小不超过的控制集。给定图和正整数,,判定图是否有一个顶点数不超过的控制集问题称为控制集问题(dominating set problem)。1979年,加里(Garey)和约翰逊(Johnson)证明了控制集问题是NP完全的。