图的支配集问题 1. 支配集的基本定义 在图 \( G = (V, E) \) 中，若顶点子集 \( D \subseteq V \) 满足图中任意顶点要么属于 \( D \)，要么与 \( D \) 中的至少一个顶点相邻（即被 \( D \) "支配"），则称 \( D \) 为 支配集 。形式化定义为： \[ \forall v \in V, \, v \in D \ \lor\ \exists u \in D \text{ 使得 } (u, v) \in E. \] 极小支配集 ：若 \( D \) 的任意真子集都不是支配集，则称 \( D \) 是极小的。 最小支配集 ：所有支配集中顶点数最少的集合，其大小称为 支配数 ，记作 \( \gamma(G) \)。 示例 ：在一条路径图 \( P_ 4 \)（顶点依次为 \( v_ 1, v_ 2, v_ 3, v_ 4 \)）中，集合 \( \{v_ 2, v_ 3\} \) 是一个支配集，但最小支配集是 \( \{v_ 2, v_ 4\} \)（或 \( \{v_ 1, v_ 3\} \)），因此 \( \gamma(P_ 4) = 2 \)。 2. 支配集与图性质的关联 平凡情况 ：完全图的支配数为 1（任一顶点可支配全图），空图的支配数为 \( |V| \)（每个顶点需单独选取）。 与连通性的关系 ：若图不连通，支配集必须覆盖每个连通分量。 与顶点度的关系 ：若存在孤立顶点，则该顶点必须属于支配集；高密度图的支配数通常较小。 3. 特殊图的支配数 路径图 \( P_ n \) ：\( \gamma(P_ n) = \lceil n/3 \rceil \)。 （例如 \( P_ 5 \) 的支配数为 2，通过间隔两个顶点选取一个顶点实现） 圈图 \( C_ n \) ：\( \gamma(C_ n) = \lceil n/3 \rceil \)。 完全二分图 \( K_ {m,n} \) ：\( \gamma(K_ {m,n}) = \min(m, n) \)（需选取较小分部的全部顶点）。 4. 相关变种问题 连通支配集 ：要求支配集 \( D \) 的诱导子图是连通的。适用于网络设计需保证支配节点间能直接通信的场景。 独立支配集 ：要求 \( D \) 是独立集（集合内顶点互不相邻）。此时支配集兼具独立性与覆盖性。 权支配集 ：每个顶点有权重，目标是求总权重最小的支配集。 5. 计算复杂性与算法 NP-完全性 ：判断是否存在大小不超过 \( k \) 的支配集是经典NP-完全问题（即使限制到平面图或二分图）。 近似算法 ：贪心算法是常用近似方案：每次选择能支配最多未支配顶点的点，近似比约为 \( \ln \Delta \)（\( \Delta \) 为最大度）。 精确算法 ：对于小规模图，可采用分支定界或动态规划（如对树结构可在多项式时间求解）。 6. 应用场景 无线传感器网络 ：选择部分节点作为中继站，覆盖所有节点并节省能耗。 社交网络影响最大化 ：找到最小群体，使其能直接影响整个网络。 设施选址 ：部署最少设施（如监控摄像头）以覆盖所有区域。 通过以上步骤，可以逐步掌握支配集问题的核心概念、性质及实际意义。