图的连通支配集

我们来探讨图论中一个结合了连通性与支配性的重要概念——图的连通支配集。

1. 基本定义

   • 在图G=(V,E)中，顶点子集S⊆V称为支配集，如果V\S中的每个顶点都与S中至少一个顶点相邻
   • 如果S不仅是支配集，而且S的诱导子图G[S]是连通图，则称S为连通支配集
   • 图的连通支配数γ_c(G)定义为最小连通支配集的大小

2. 与相关概念的区别

   • 与普通支配集不同：连通支配集要求支配顶点之间连通
   • 与连通控制集的关系：在某些文献中这两个术语等价，但控制集通常强调对边或路径的掌控
   • 与斯坦纳树的联系：寻找最小连通支配集可转化为斯坦纳树问题的特例

3. 计算复杂性

   • 最小连通支配集问题是NP困难的
   • 在一般图中不存在常数近似比的近似算法（除非P=NP）
   • 在单位圆图等特殊图类中存在多项式时间算法
   • 对于树结构，可通过动态规划在O(n)时间内求解

4. 构造算法

   • 贪心构造：从任意顶点开始，逐步添加距离最近的未支配顶点
   • 基于最大叶生成树：先构造生成树，取其非叶顶点集合
   • 两阶段法：先找支配集，再添加最少的连接顶点使其连通
   • 局部搜索：通过顶点交换的局部优化改进解质量

5. 近似算法

   • 最小生成树近似：性能比不超过2(Δ+1)，其中Δ为最大度
   • 基于支配集的近似：先求支配集D，再用斯坦纳树连接，性能比2H(Δ)+1
   • 分布式算法：适用于无线传感器网络等场景
   • 参数化算法：对于小参数k，可在f(k)n^O(1)时间内求解

6. 应用场景

   • 无线网络虚拟骨干网构造
   • 网络路由协议设计
   • 社交网络影响力最大化
   • 设施选址问题
   • 图像处理中的连通区域分析

7. 理论性质

   • 对于n顶点图，γ_c(G) ≤ n-1（星图达到上界）
   • 下界：γ_c(G) ≥ (n-1)/Δ
   • 与直径的关系：γ_c(G) ≥ diam(G)/3
   • 在闭包运算下的行为：对图进行某些运算后连通支配数的变化规律

这个概念的独特之处在于同时要求集合的"覆盖性"（支配）和"内聚性"（连通），在理论和应用层面都具有重要意义。