图的分数控制与分数控制数
字数 2347 2025-12-09 09:17:06

图的分数控制与分数控制数

我们从基本定义开始。在图 \(G=(V,E)\) 中，一个控制集 \(D \subseteq V\) 满足：图中每个顶点要么在 \(D\) 中，要么至少与 \(D\) 中的一个顶点相邻。控制的概念是“全有或全无”的，即一个顶点要么完全被控制（计入控制集），要么完全不被控制（不计入）。分数控制推广了这一概念，允许顶点以“分数”的形式归属于控制集。

我们可以从线性规划松弛的角度来理解分数控制：

  1. 定义：对于图 \(G=(V,E)\)，一个分数控制函数 \(f: V \rightarrow [0, 1]\) 满足：对于每个顶点 \(v \in V\)，都有 \(f(N[v]) \geq 1\)，其中 \(N[v] = \{v\} \cup \{u: uv \in E\}\) 是顶点 \(v\) 的闭邻域。函数值 \(f(v)\) 可以看作顶点 \(v\) 在控制集中所占的“份量”。条件 \(f(N[v]) \geq 1\) 保证了每个顶点（包括其自身）的闭邻域内的总控制份量至少为1，从而确保它被“充分”控制。
  2. 分数控制数：图 \(G\) 的分数控制数，记为 \(\gamma_f(G)\)，定义为所有分数控制函数 \(f\) 的目标值 \(\sum_{v \in V} f(v)\) 中的最小值。由于控制集对应函数值只能在 \(\{0, 1\}\) 中取值的特殊情况，显然有 \(\gamma_f(G) \leq \gamma(G)\)，其中 \(\gamma(G)\) 是通常的（整数）控制数。

接下来，我们探讨分数控制数的重要性质和计算方法。

  1. 线性规划对偶：分数控制问题可以写成一个线性规划（LP）：最小化 \(\sum_{v} f(v)\)，满足 \(f(N[v]) \geq 1\) 且 \(f(v) \geq 0\)。其对偶问题为：最大化 \(\sum_{v} g(v)\)，满足对于每个顶点 \(v\)，有 \(\sum_{u \in N[v]} g(u) \leq 1\) 且 \(g(v) \geq 0\)。这个对偶问题称为分数包问题。由线性规划强对偶定理，原问题的最优值等于对偶问题的最优值。这为我们提供了计算和界定分数控制数的强大工具。
  2. 上下界：分数控制数有一些易于计算的界。例如，对于任意 \(n\) 阶图 \(G\)，有 \(\gamma_f(G) \geq n / (\Delta + 1)\)，其中 \(\Delta\) 是最大度。另外，\(\gamma_f(G)\) 不小于图的最小特征值相关量。一个重要的上界是 \(\gamma_f(G) \leq n / (\delta + 1)\)，其中 \(\delta\) 是最小度。这些界通常比整数控制数的相应界更紧。

然后，我们考虑分数控制与图的结构性概念的联系。

  1. 分数控制与分数包：如前所述，分数包数是分数控制数的线性规划对偶。一个图 \(G\) 的分数包数，记为 \(\alpha_f^*(G)\) 或有时记为 \(\rho_f(G)\)，是满足对偶约束的函数 \(g\) 的最大权和。对于所有图，有 \(\gamma_f(G) = \alpha_f^*(G)\)。注意，这与整数情况下的控制数 \(\gamma(G)\) 和独立数（或包数）\(\alpha(G)\) 之间没有简单的等式关系不同，分数版本的对偶性带来了完美的对称性。
  2. 分数控制与2-包：一个2-包是顶点集的一个子集 \(P\)，其中任意两个不同顶点在 \(G\) 中的距离至少为3（即它们没有公共邻居）。2-包的大小上界是分数控制数的一个有用的下界：对于任何图，其最大2-包的大小不超过 \(\gamma_f(G)\)。这是因为在分数包的对偶约束下，任何2-包中的顶点在其闭邻域上的权重和至多为1，且这些闭邻域互不相交，因此总权重和有一个自然上界。

最后，我们探讨一些特殊图类中的分数控制数和相关算法。

  1. 特殊图的值：
  • 完全图 \(K_n\)：每个顶点控制其自身和所有其他顶点。最小的分数控制函数是为每个顶点赋权 \(1/n\)，则每个闭邻域的总权为 \(1\)，总权为 \(1\)。因此，\(\gamma_f(K_n) = 1\)。
  • 完全二部图 \(K_{a,b}\)：可以证明 \(\gamma_f(K_{a,b}) = 2 - \frac{1}{\max(a,b)+1}\) 当 \(a \neq b\) 时有特定表达式，当 \(a=b\) 时为 \(2 - 1/(a+1)\)。
  • 路径 \(P_n\) 和圈 \(C_n\)：有精确公式，例如 \(\gamma_f(P_n) = \lceil n/3 \rceil\) 的分数推广形式，与整数控制数在循环模式上类似但值更小。
    • 树：分数控制数可以通过线性规划或动态规划有效计算，并且存在多项式时间算法。
  1. 计算复杂性：计算一般图的分数控制数是一个线性规划问题，因此可以在多项式时间内求解（例如使用内点法）。然而，寻找具有特定结构（如半整数值）的最优分数控制函数可能与整数规划问题相关。值得注意的是，分数版本的计算通常比对应的整数NP难问题（如计算控制数）容易得多。
  2. 整数舍入与近似：由于 \(\gamma_f(G) \leq \gamma(G)\)，分数控制数为整数控制数提供了一个下界。通过舍入分数解（例如，对分数控制函数设定阈值，将权重大于某值的顶点放入控制集），可以构造整数控制集，从而得到整数控制数的近似算法，近似比通常与图的最大度有关。
图的分数控制与分数控制数 我们从基本定义开始。在图 \(G=(V,E)\) 中，一个 控制集 \(D \subseteq V\) 满足：图中每个顶点要么在 \(D\) 中，要么至少与 \(D\) 中的一个顶点相邻。控制的概念是“全有或全无”的，即一个顶点要么完全被控制（计入控制集），要么完全不被控制（不计入）。 分数控制 推广了这一概念，允许顶点以“分数”的形式归属于控制集。 我们可以从线性规划松弛的角度来理解分数控制： 定义 ：对于图 \(G=(V,E)\)，一个 分数控制函数 \(f: V \rightarrow [ 0, 1]\) 满足：对于每个顶点 \(v \in V\)，都有 \(f(N[ v]) \geq 1\)，其中 \(N[ v] = \{v\} \cup \{u: uv \in E\}\) 是顶点 \(v\) 的闭邻域。函数值 \(f(v)\) 可以看作顶点 \(v\) 在控制集中所占的“份量”。条件 \(f(N[ v ]) \geq 1\) 保证了每个顶点（包括其自身）的闭邻域内的总控制份量至少为1，从而确保它被“充分”控制。 分数控制数 ：图 \(G\) 的 分数控制数 ，记为 \(\gamma_ f(G)\)，定义为所有分数控制函数 \(f\) 的目标值 \(\sum_ {v \in V} f(v)\) 中的最小值。由于控制集对应函数值只能在 \(\{0, 1\}\) 中取值的特殊情况，显然有 \(\gamma_ f(G) \leq \gamma(G)\)，其中 \(\gamma(G)\) 是通常的（整数）控制数。 接下来，我们探讨分数控制数的重要性质和计算方法。 线性规划对偶 ：分数控制问题可以写成一个线性规划（LP）：最小化 \(\sum_ {v} f(v)\)，满足 \(f(N[ v]) \geq 1\) 且 \(f(v) \geq 0\)。其对偶问题为：最大化 \(\sum_ {v} g(v)\)，满足对于每个顶点 \(v\)，有 \(\sum_ {u \in N[ v]} g(u) \leq 1\) 且 \(g(v) \geq 0\)。这个对偶问题称为 分数包 问题。由线性规划强对偶定理，原问题的最优值等于对偶问题的最优值。这为我们提供了计算和界定分数控制数的强大工具。 上下界 ：分数控制数有一些易于计算的界。例如，对于任意 \(n\) 阶图 \(G\)，有 \(\gamma_ f(G) \geq n / (\Delta + 1)\)，其中 \(\Delta\) 是最大度。另外，\(\gamma_ f(G)\) 不小于图的最小特征值相关量。一个重要的上界是 \(\gamma_ f(G) \leq n / (\delta + 1)\)，其中 \(\delta\) 是最小度。这些界通常比整数控制数的相应界更紧。 然后，我们考虑分数控制与图的结构性概念的联系。 分数控制与分数包 ：如前所述，分数包数是分数控制数的线性规划对偶。一个图 \(G\) 的 分数包数 ，记为 \(\alpha_ f^ (G)\) 或有时记为 \(\rho_ f(G)\)，是满足对偶约束的函数 \(g\) 的最大权和。对于所有图，有 \(\gamma_ f(G) = \alpha_ f^ (G)\)。注意，这与整数情况下的控制数 \(\gamma(G)\) 和独立数（或包数）\(\alpha(G)\) 之间没有简单的等式关系不同，分数版本的对偶性带来了完美的对称性。 分数控制与2-包 ：一个2-包是顶点集的一个子集 \(P\)，其中任意两个不同顶点在 \(G\) 中的距离至少为3（即它们没有公共邻居）。2-包的大小上界是分数控制数的一个有用的下界：对于任何图，其最大2-包的大小不超过 \(\gamma_ f(G)\)。这是因为在分数包的对偶约束下，任何2-包中的顶点在其闭邻域上的权重和至多为1，且这些闭邻域互不相交，因此总权重和有一个自然上界。 最后，我们探讨一些特殊图类中的分数控制数和相关算法。 特殊图的值 ： 完全图 \(K_ n\) ：每个顶点控制其自身和所有其他顶点。最小的分数控制函数是为每个顶点赋权 \(1/n\)，则每个闭邻域的总权为 \(1\)，总权为 \(1\)。因此，\(\gamma_ f(K_ n) = 1\)。 完全二部图 \(K_ {a,b}\) ：可以证明 \(\gamma_ f(K_ {a,b}) = 2 - \frac{1}{\max(a,b)+1}\) 当 \(a \neq b\) 时有特定表达式，当 \(a=b\) 时为 \(2 - 1/(a+1)\)。 路径 \(P_ n\) 和圈 \(C_ n\) ：有精确公式，例如 \(\gamma_ f(P_ n) = \lceil n/3 \rceil\) 的分数推广形式，与整数控制数在循环模式上类似但值更小。 树 ：分数控制数可以通过线性规划或动态规划有效计算，并且存在多项式时间算法。 计算复杂性 ：计算一般图的分数控制数是一个线性规划问题，因此可以在多项式时间内求解（例如使用内点法）。然而，寻找具有特定结构（如半整数值）的最优分数控制函数可能与整数规划问题相关。值得注意的是，分数版本的计算通常比对应的整数NP难问题（如计算控制数）容易得多。 整数舍入与近似 ：由于 \(\gamma_ f(G) \leq \gamma(G)\)，分数控制数为整数控制数提供了一个下界。通过舍入分数解（例如，对分数控制函数设定阈值，将权重大于某值的顶点放入控制集），可以构造整数控制集，从而得到整数控制数的近似算法，近似比通常与图的最大度有关。