图的符号边控制与符号边控制数
图论中，控制集问题研究的是如何选择顶点子集，使得图中每个顶点要么在子集中，要么与子集中的某个顶点相邻。符号边控制是这一经典概念的推广，它将“控制”的思想从顶点集延伸到了对边集进行赋值，并研究如何通过这种赋值来反映图的结构特性。
我们先从基本定义开始。设 \(G = (V, E)\) 是一个无向简单图。一个符号边控制函数是一个映射 \(f: E \to \{-1, +1\}\)，它为图中的每条边分配一个值，要么是 +1，要么是 -1。
这个函数的核心在于它对每个顶点产生的“负载”。对于任意一个顶点 \(v \in V\)，它的负载 \(f[v]\) 定义为所有与它相关联的边的函数值之和。用数学公式表达就是：
\[f[v] = \sum_{e \in E, \, e \text{ 与 } v \text{ 关联}} f(e) \]
简单来说，就是把连接顶点 \(v\) 的所有边的赋值（+1 或 -1）加起来。
如果这个符号边控制函数 \(f\) 满足一个条件：对于图中的每一条边 \(e = uv \in E\)，都有 \(f[u] + f[v] \ge 1\)，那么我们就称 \(f\) 为图 \(G\) 的一个符号边控制函数。
这个条件 \(f[u] + f[v] \ge 1\) 是什么意思呢？它要求对于任意一条边，其两个端点的负载之和至少为 1。这意味着一条边的两个端点不能同时具有过小的负载（比如都是负数），从而保证了图在某种“符号”意义下的稳定性或可控性。
现在，对于一个给定的符号边控制函数 \(f\)，我们可以计算它的权重 \(w(f)\)，即所有边的函数值之和：
\[w(f) = \sum_{e \in E} f(e) \]
图 \(G\) 的符号边控制数，记作 \(\gamma'_{s}(G)\)，定义为所有可能的符号边控制函数中，权重的最小值。即：
\[\gamma'_{s}(G) = \min \{ w(f) \mid f \text{ 是 } G \text{ 的符号边控制函数} \} \]
为了让你更好地理解，我们来看一个最简单的例子：路径图 \(P_3\)，它有三个顶点 \(v_1, v_2, v_3\) 和两条边 \(e_1 = v_1v_2, e_2 = v_2v_3\)。
我们尝试几种赋值方案：
-
方案一：\(f(e_1) = +1, f(e_2) = +1\)。
计算负载：\(f[v_1] = +1, f[v_2] = +1 + (+1) = +2, f[v_3] = +1\)。
检查条件：对于边 \(e_1\)，\(f[v_1] + f[v_2] = 1+2=3 \ge 1\)；对于边 \(e_2\)，\(f[v_2] + f[v_3] = 2+1=3 \ge 1\)。条件满足。
权重 \(w(f) = 1 + 1 = 2\)。 -
方案二：\(f(e_1) = -1, f(e_2) = +1\)。
计算负载：\(f[v_1] = -1, f[v_2] = (-1) + (+1) = 0, f[v_3] = +1\)。
检查条件：对于边 \(e_1\)，\(f[v_1] + f[v_2] = (-1) + 0 = -1 < 1\)。条件不满足！所以这个 \(f\) 不是符号边控制函数。 -
方案三：\(f(e_1) = +1, f(e_2) = -1\)。
计算负载：\(f[v_1] = +1, f[v_2] = (+1) + (-1) = 0, f[v_3] = -1\)。
检查条件：对于边 \(e_2\)，\(f[v_2] + f[v_3] = 0 + (-1) = -1 < 1\)。条件不满足。 -
方案四：\(f(e_1) = -1, f(e_2) = -1\)。
计算负载：\(f[v_1] = -1, f[v_2] = (-1) + (-1) = -2, f[v_3] = -1\)。
检查条件：对于边 \(e_1\)，\(f[v_1] + f[v_2] = -1 + (-2) = -3 < 1\)；对于边 \(e_2\)，\(f[v_2] + f[v_3] = -2 + (-1) = -3 < 1\)。条件不满足。
由此可见，对于 \(P_3\)，只有方案一是可行的符号边控制函数，其权重为 2。那么，是否存在权重更小的函数呢？我们只找到这一个可行的，所以 \(\gamma'_{s}(P_3) = 2\)。
符号边控制数有一些基本的性质。例如，对于任何 \(n\) 个顶点的图 \(G\)，其符号边控制数满足一个下界：\(\gamma'_{s}(G) \ge \lceil -|E|/2 \rceil\)。同时，对于正则图（每个顶点度数相同的图），有更精确的界。
研究符号边控制数的意义在于，它提供了一个衡量图“可控性”的新维度。与经典的边控制（要求每条边至少与一个被选中的边相邻）不同，符号边控制通过赋值为负的边来“抵消”一部分正的控制作用，使得问题的约束更加灵活，但也更具挑战性。确定一个一般图的符号边控制数通常是 NP-难问题，因此研究者们主要关注特殊图类（如树、圈、完全图、正则图）的符号边控制数的精确值或上下界。
总结一下，符号边控制是图控制理论中一个有趣的分支，它通过给边赋予正负号，并考察顶点负载的约束条件，来探索图在符号赋值下的结构性质。其核心参数——符号边控制数，则量化了实现这种控制所需的最小“净正控制力”。\(\boxed{\text{概念引入完毕}}\)