图的分数支配集
字数 2489 2025-12-14 20:01:38

图的分数支配集

我先从支配集概念本身说起。
一个图 \(G = (V, E)\) 的支配集是指一个顶点子集 \(D \subseteq V\)，使得图中每个不在 \(D\) 中的顶点至少有一个邻居在 \(D\) 中。换句话说，每个顶点要么属于 \(D\)，要么与 \(D\) 中某个顶点相邻。
支配数是所有支配集的最小大小，记作 \(\gamma(G)\)。

分数支配集 是对这一概念的分数化推广。
我们为每个顶点 \(v \in V\) 分配一个权值 \(x_v \in [0, 1]\)。
要求对于每个顶点 \(v \in V\)，其自身及其所有邻居的权值之和至少为 1，即

\[\sum_{u \in N[v]} x_u \ge 1 \]

其中 \(N[v] = \{v\} \cup \{u \mid uv \in E\}\) 表示 \(v\) 的闭邻域。

目标是使所有顶点权值之和最小：

\[\min \sum_{v \in V} x_v \]

这个最小值称为图的 分数支配数，记作 \(\gamma_f(G)\)。

为什么引入分数支配集？
因为分数松弛常用于为整数组合优化问题提供下界。
显然，任何整数支配集（取 \(x_v \in \{0,1\}\)）都满足上述约束，所以：

\[\gamma_f(G) \le \gamma(G) \]

分数支配数往往比整数支配数更容易计算（它是一个线性规划问题），并且它的值可以帮助估计整数情况下的难度。

分数支配的线性规划对偶
考虑线性规划原问题：

\[\text{最小化 } \mathbf{1}^T x \quad \text{s.t. } A_{\text{闭}} x \ge \mathbf{1}, \; x \ge 0 \]

其中 \(A_{\text{闭}}\) 是闭邻关联矩阵（行对应顶点，列也对应顶点，若顶点在闭邻域内则对应位置为 1）。

其对偶问题为：

\[\text{最大化 } \mathbf{1}^T y \quad \text{s.t. } A_{\text{闭}}^T y \le \mathbf{1}, \; y \ge 0 \]

注意 \(A_{\text{闭}}^T = A_{\text{闭}}\)，因为矩阵是对称的。
所以对偶是：
最大化 \(\sum_{v} y_v\)，满足对每个顶点 \(v\)，其闭邻域中所有 \(y_u\) 之和不超过 1。

这个对偶可以解释为：
我们给每个顶点分配权值 \(y_v\)，要求每个顶点闭邻域的权值和不超过 1，目标是使总权值和最大。
由强对偶定理，最大对偶值等于 \(\gamma_f(G)\)。

对偶问题实际上就是分数 包支配函数（fractional packing of closed neighborhoods）问题。

计算分数支配数的简单例子
考虑一个路径图 \(P_3\)：顶点 \(v_1 - v_2 - v_3\)。
设权值 \(x_1, x_2, x_3\)。
约束：

  • 对 \(v_1\)：\(x_1 + x_2 \ge 1\)
  • 对 \(v_2\)：\(x_1 + x_2 + x_3 \ge 1\)
  • 对 \(v_3\)：\(x_2 + x_3 \ge 1\)

最小化 \(x_1 + x_2 + x_3\)。
可通过对称性设 \(x_1 = x_3 = a, x_2 = b\)，则约束变为：

  1. \(a + b \ge 1\)
  2. \(2a + b \ge 1\)（其实比第一个弱，因为 \(a \ge 0\)）
  3. 同第一个
    因此只需 \(a + b \ge 1\) 且 \(a \ge 0, b \ge 0\)。
    目标 \(2a + b\) 在 \(a + b = 1\) 且 \(a\) 尽量小时最小，取 \(a = 0, b = 1\) 得到值 \(1\)。
    所以 \(\gamma_f(P_3) = 1\)。

实际上对于任何图，孤立顶点会迫使分数支配数至少为 \(n\) 个顶点中的某些值，但对连通图可能小于 1。
例如 \(K_n\)：每个顶点权值 \(1/n\) 就满足条件（闭邻域权值和 = 1），总和为 1，所以完全图的分数支配数是 1。

分数支配数与支配数的关系
已知：

\[\gamma_f(G) \le \gamma(G) \]

并且存在一些图类（如树）有 \(\gamma(G) \le 2 \gamma_f(G)\) 的关系，甚至更紧的界。
分数支配数可以用线性规划快速求解（多项式时间），而整数支配集在一般图中是 NP-hard 问题，因此分数松弛是一种近似手段。

分数全支配集
类似可以定义 分数全支配集：要求每个顶点（包括支配集内顶点）必须至少有一个邻居在支配集中（即闭邻域改为开邻域 \(N(v)\)）。
此时约束变为对每个顶点 \(v\)：\(\sum_{u \in N(v)} x_u \ge 1\)。
对应的分数全支配数记作 \(\gamma_{ft}(G)\)。

类似地，对偶问题是分数打包开邻域问题。

分数支配集与分数覆盖的关系
注意，分数支配集的约束本质上是一个 分数覆盖型 约束：用权值覆盖每个闭邻域。
这和点覆盖（覆盖边）不同，这里是覆盖“顶点被支配”的条件，可以看作超图覆盖问题，其中超边是各顶点的闭邻域。

研究意义
分数支配在无线网络传感器布置、资源分配等问题中有应用，因为允许部分权值可以模型化概率性覆盖或资源共享的情况。
此外，分数参数常用来获得整数参数的界，研究整数与分数之间的“间隙”，理解问题的线性规划松弛效果。

图的分数支配集 我先从支配集概念本身说起。 一个图 \( G = (V, E) \) 的支配集是指一个顶点子集 \( D \subseteq V \)，使得图中每个不在 \( D \) 中的顶点至少有一个邻居在 \( D \) 中。换句话说，每个顶点要么属于 \( D \)，要么与 \( D \) 中某个顶点相邻。 支配数是所有支配集的最小大小，记作 \( \gamma(G) \)。 分数支配集 是对这一概念的分数化推广。 我们为每个顶点 \( v \in V \) 分配一个权值 \( x_ v \in [ 0, 1 ] \)。 要求对于每个顶点 \( v \in V \)，其自身及其所有邻居的权值之和至少为 1，即 \[ \sum_ {u \in N[ v]} x_ u \ge 1 \] 其中 \( N[ v ] = \{v\} \cup \{u \mid uv \in E\} \) 表示 \( v \) 的闭邻域。 目标是使所有顶点权值之和最小： \[ \min \sum_ {v \in V} x_ v \] 这个最小值称为图的 分数支配数 ，记作 \( \gamma_ f(G) \)。 为什么引入分数支配集？ 因为分数松弛常用于为整数组合优化问题提供下界。 显然，任何整数支配集（取 \( x_ v \in \{0,1\} \)）都满足上述约束，所以： \[ \gamma_ f(G) \le \gamma(G) \] 分数支配数往往比整数支配数更容易计算（它是一个线性规划问题），并且它的值可以帮助估计整数情况下的难度。 分数支配的线性规划对偶 考虑线性规划原问题： \[ \text{最小化 } \mathbf{1}^T x \quad \text{s.t. } A_ {\text{闭}} x \ge \mathbf{1}, \; x \ge 0 \] 其中 \( A_ {\text{闭}} \) 是闭邻关联矩阵（行对应顶点，列也对应顶点，若顶点在闭邻域内则对应位置为 1）。 其对偶问题为： \[ \text{最大化 } \mathbf{1}^T y \quad \text{s.t. } A_ {\text{闭}}^T y \le \mathbf{1}, \; y \ge 0 \] 注意 \( A_ {\text{闭}}^T = A_ {\text{闭}} \)，因为矩阵是对称的。 所以对偶是： 最大化 \( \sum_ {v} y_ v \)，满足对每个顶点 \( v \)，其闭邻域中所有 \( y_ u \) 之和不超过 1。 这个对偶可以解释为： 我们给每个顶点分配权值 \( y_ v \)，要求每个顶点闭邻域的权值和不超过 1，目标是使总权值和最大。 由强对偶定理，最大对偶值等于 \( \gamma_ f(G) \)。 对偶问题实际上就是分数 包支配函数 （fractional packing of closed neighborhoods）问题。 计算分数支配数的简单例子 考虑一个路径图 \( P_ 3 \)：顶点 \( v_ 1 - v_ 2 - v_ 3 \)。 设权值 \( x_ 1, x_ 2, x_ 3 \)。 约束： 对 \( v_ 1 \)：\( x_ 1 + x_ 2 \ge 1 \) 对 \( v_ 2 \)：\( x_ 1 + x_ 2 + x_ 3 \ge 1 \) 对 \( v_ 3 \)：\( x_ 2 + x_ 3 \ge 1 \) 最小化 \( x_ 1 + x_ 2 + x_ 3 \)。 可通过对称性设 \( x_ 1 = x_ 3 = a, x_ 2 = b \)，则约束变为： \( a + b \ge 1 \) \( 2a + b \ge 1 \)（其实比第一个弱，因为 \( a \ge 0 \)） 同第一个 因此只需 \( a + b \ge 1 \) 且 \( a \ge 0, b \ge 0 \)。 目标 \( 2a + b \) 在 \( a + b = 1 \) 且 \( a \) 尽量小时最小，取 \( a = 0, b = 1 \) 得到值 \( 1 \)。 所以 \( \gamma_ f(P_ 3) = 1 \)。 实际上对于任何图，孤立顶点会迫使分数支配数至少为 \( n \) 个顶点中的某些值，但对连通图可能小于 1。 例如 \( K_ n \)：每个顶点权值 \( 1/n \) 就满足条件（闭邻域权值和 = 1），总和为 1，所以完全图的分数支配数是 1。 分数支配数与支配数的关系 已知： \[ \gamma_ f(G) \le \gamma(G) \] 并且存在一些图类（如树）有 \( \gamma(G) \le 2 \gamma_ f(G) \) 的关系，甚至更紧的界。 分数支配数可以用线性规划快速求解（多项式时间），而整数支配集在一般图中是 NP-hard 问题，因此分数松弛是一种近似手段。 分数全支配集 类似可以定义 分数全支配集 ：要求每个顶点（包括支配集内顶点）必须至少有一个邻居在支配集中（即闭邻域改为开邻域 \( N(v) \)）。 此时约束变为对每个顶点 \( v \)：\( \sum_ {u \in N(v)} x_ u \ge 1 \)。 对应的分数全支配数记作 \( \gamma_ {ft}(G) \)。 类似地，对偶问题是分数打包开邻域问题。 分数支配集与分数覆盖的关系 注意，分数支配集的约束本质上是一个 分数覆盖型 约束：用权值覆盖每个闭邻域。 这和点覆盖（覆盖边）不同，这里是覆盖“顶点被支配”的条件，可以看作超图覆盖问题，其中超边是各顶点的闭邻域。 研究意义 分数支配在无线网络传感器布置、资源分配等问题中有应用，因为允许部分权值可以模型化概率性覆盖或资源共享的情况。 此外，分数参数常用来获得整数参数的界，研究整数与分数之间的“间隙”，理解问题的线性规划松弛效果。