图的符号控制函数与分数符号控制数 图论中的符号控制函数是控制理论的延伸，旨在为图中的每个顶点分配一个实数值，使得每个顶点及其邻域的总赋值满足特定条件。分数符号控制数则是在分数赋值下的优化参数，其研究结合了连续优化和图结构性质。 1. 基本定义与背景 符号控制函数 （signed dominating function）：给定图 \(G = (V, E)\)，一个函数 \(f: V \to \{-1, 1\}\) 称为符号控制函数，如果对每个顶点 \(v \in V\)，其闭邻域 \(N[ v ] = \{v\} \cup N(v)\) 的赋值之和至少为 1，即 \[ f(N[ v]) = \sum_ {u \in N[ v ]} f(u) \ge 1. \] 符号控制数 （signed domination number）\(\gamma_ s(G)\) 定义为所有符号控制函数的最小权重 \(\sum_ {v \in V} f(v)\)。 2. 分数推广动机 整数赋值 \(\{-1, 1\}\) 限制较强，分数赋值允许更灵活的优化。 分数符号控制函数 ：将值域扩展为区间 \([ -1, 1]\) 中的实数，条件仍为 \(f(N[ v ]) \ge 1\)。 分数符号控制数 \(\gamma_ {s}^* (G)\) 定义为所有分数符号控制函数的最小权重 \(\sum_ {v \in V} f(v)\)。 3. 线性规划模型 分数符号控制数可通过线性规划求解： 变量：\(f(v) \in [ -1, 1 ]\)。 目标：最小化 \(\sum_ {v \in V} f(v)\)。 约束：对每个 \(v \in V\)，\(\sum_ {u \in N[ v ]} f(u) \ge 1\)。 由线性规划对偶性，可导出分数符号控制数的对偶问题，关联于图的覆盖或包装结构。 4. 与经典控制数的关系 符号控制数满足 \(\gamma_ s(G) \ge \gamma_ {s}^* (G)\)，且分数版本可能严格更小。 对正则图或对称结构，分数符号控制数常可通过均匀赋值逼近。 5. 关键性质与界 一般图 \(G\) 有下界 \(\gamma_ {s}^* (G) \ge \frac{n}{\Delta+1}\)（\(\Delta\) 为最大度），上界与最小度 \(\delta\) 相关。 对树、网格等特殊图类，分数符号控制数有闭式表达式或递归计算法。 6. 算法与复杂性 分数符号控制数是线性规划问题，可在多项式时间求解。 整数版本的符号控制数计算是 NP-困难问题，分数化提供了近似界。 7. 应用与扩展 可用于网络监控：正负赋值可区分“激活”与“抑制”节点。 推广到 k-符号控制 （要求 \(f(N[ v]) \ge k\)）或 负控制 （允许赋值为负）。 与图的符号边控制、符号全控制等形成控制函数族。 通过分数松弛，符号控制问题更易分析，并为整数版本提供近似算法设计基础。该方向融合了图论、线性规划和组合优化，是符号控制理论的重要发展。