图的符号控制数与分数控制数 首先明确背景：在图论中，控制集（dominating set）是一个顶点子集，使得图中每个顶点要么属于该子集，要么与该子集中的某个顶点相邻。基于此概念，研究者引入了多种推广，其中包括 符号控制 （signed dominating）和 分数控制 （fractional dominating）。这两个概念分别从赋权和连续赋值的角度扩展了经典控制集问题。 第一步：符号控制函数的定义 设图 \( G = (V, E) \)，一个 符号控制函数 （signed dominating function）是一个函数 \( f: V \to \{-1, 1\} \)，满足对任意顶点 \( v \in V \)，有 \[ f(N[ v]) = \sum_ {u \in N[ v ]} f(u) \ge 1 \] 其中 \( N[ v ] = \{v\} \cup \{u \mid uv \in E\} \) 是 \( v \) 的闭邻域。 直观上，每个顶点可以分配 \(+1\) 或 \(-1\) 的权重，要求每个顶点及其所有邻居的权重之和不小于 1。 符号控制数 （signed domination number）定义为： \[ \gamma_ s(G) = \min \left\{ \sum_ {v \in V} f(v) \;\middle|\; f \text{ 是符号控制函数} \right\} \] 它反映了用 \(+1/-1\) 赋值满足上述条件时全图权重和的最小值。 第二步：分数控制函数的定义 在分数控制中，放宽赋值范围，允许顶点权重为区间 \([ 0,1]\) 中的实数。一个 分数控制函数 （fractional dominating function）是函数 \( g: V \to [ 0,1 ] \)，满足对任意顶点 \( v \in V \)，有 \[ \sum_ {u \in N[ v ]} g(u) \ge 1 \] 即每个闭邻域的权重和至少为 1。 分数控制数 （fractional domination number）定义为： \[ \gamma_ f(G) = \min \left\{ \sum_ {v \in V} g(v) \;\middle|\; g \text{ 是分数控制函数} \right\} \] 它等价于经典控制问题的线性规划松弛，因此 \(\gamma_ f(G) \le \gamma(G)\)（经典控制数）。 第三步：两者与经典控制数的关系 对任意图 \( G \)，有 \(\gamma_ f(G) \le \gamma(G)\)，且 \(\gamma_ f(G)\) 可以达到小于 1 的顶点权重和。 符号控制与经典控制无直接大小比较，但符号控制数可以小于经典控制数，因为允许负权重可更灵活地满足邻域和约束。 第四步：计算与复杂度 计算 \(\gamma_ s(G)\) 是 NP-难的，即使对二分图或平面图也如此。而 \(\gamma_ f(G)\) 可通过线性规划多项式时间求解，因为它是线性规划松弛问题。 第五步：示例说明 考虑路径图 \( P_ 3 \) 的顶点依次为 \( v_ 1, v_ 2, v_ 3 \)。 分数控制：可设 \( g(v_ 1)=g(v_ 3)=0.5, g(v_ 2)=0 \)，则每个闭邻域和均为 1，故 \(\gamma_ f(P_ 3)=1\)。 符号控制：可取 \( f(v_ 1)=1, f(v_ 2)=-1, f(v_ 3)=1 \)，验证每个闭邻域和 ≥1，总权重和为 1，即 \(\gamma_ s(P_ 3)=1\)。 第六步：研究意义与推广 符号控制和分数控制为经典控制问题提供了新的优化视角。分数控制在算法设计中有应用（如圆控制、网络监控的资源分配），符号控制则与图上的符号编码、社会网络的正负影响分析相关。进一步推广还包括 负控制 （仅允许非正权重）和 多重符号控制 等。