图的控制集问题 基本定义 图 \( G = (V, E) \) 的 控制集 （Dominating Set）是一个顶点子集 \( D \subseteq V \)，使得图中任意顶点要么属于 \( D \)，要么与 \( D \) 中的至少一个顶点相邻。形式化表述为： \[ \forall v \in V, \, v \in D \ \lor\ \exists u \in D \text{ 使得 } (u, v) \in E. \] 例如，在一条路径图 \( P_ 4 \)（顶点依次为 \( v_ 1, v_ 2, v_ 3, v_ 4 \)）中，集合 \( \{v_ 2, v_ 3\} \) 是一个控制集，因为 \( v_ 1 \) 与 \( v_ 2 \) 相邻，\( v_ 4 \) 与 \( v_ 3 \) 相邻，且 \( v_ 2, v_ 3 \) 自身属于 \( D \)。 最小控制集与控制数 最小控制集 是顶点数最少的控制集，其大小记为 \( \gamma(G) \)，称为图 \( G \) 的 控制数 （Domination Number）。 例如，完全图 \( K_ n \) 的控制数为 1（任一顶点均可控制全图），而圈图 \( C_ n \) 的控制数为 \( \lceil n/3 \rceil \)（每三个顶点需一个控制点）。 控制集的性质与分类 独立控制集 ：若控制集 \( D \) 还是独立集（即 \( D \) 中任意两点不相邻），则称为独立控制集。其最小大小记为 \( i(G) \)。 连通控制集 ：若 \( D \) 的诱导子图是连通的，则称为连通控制集，最小大小记为 \( \gamma_ c(G) \)。此类问题在无线网络设计中尤为重要。 全控制集 ：要求 \( D \) 不仅控制其他顶点，还需控制自身内部（即 \( D \) 中每个顶点至少与 \( D \) 中另一顶点相邻）。其最小大小记为 \( \gamma_ t(G) \)。 计算复杂性与近似算法 判定“图 \( G \) 是否存在大小不超过 \( k \) 的控制集”是 NP-完全问题 ，即使限制在平面图或二分图中亦然。 近似算法：贪心算法可达到近似比 \( O(\log n) \)（即解的大小不超过最优解的 \( O(\log n) \) 倍），但除非 \( P=NP \)，不存在常数倍近似算法。 特殊图类的控制数 树 ：可通过动态规划在多项式时间计算 \( \gamma(G) \)。 网格图 ：\( m \times n \) 网格图的控制数有精确公式（如 \( \lceil mn/3 \rceil \) 适用于部分情况）。 正则图 ：利用图的正则性可推导控制数的上下界，如 \( \gamma(G) \geq n/(\Delta+1) \)（其中 \( \Delta \) 为最大度）。 扩展研究方向 权值控制集 ：顶点带权时，求最小权值的控制集。 多目标控制 ：同时满足多种控制条件（如同时要求连通和独立）。 分布式计算模型 ：研究分布式算法如何高效构造近优控制集。