图的符号边控制与符号边控制数
字数 2473 2025-12-05 04:47:24

图的符号边控制与符号边控制数

1. 基本概念引入
图的符号边控制是图论中控制理论的一个变种，它关注的是对图中边的“赋值”或“标记”，并研究这种赋值如何满足特定的全局条件。为了理解这个概念，我们首先需要明确几个基础构件：

  • 图 (Graph)：由顶点集合和边集合构成，边连接两个顶点。
  • 边赋值 (Edge Assignment)：为图中的每一条边分配一个数值。在符号边控制中，这个数值通常来自集合 {-1, +1}。
  • 边邻域 (Edge Neighborhood)：对于任意一条边 e = uv，它的（开）边邻域是指所有与 e 至少有一个公共顶点的边的集合，但不包括 e 本身。例如，与边 e 共享顶点 u 的所有其他边，以及共享顶点 v 的所有其他边，共同构成了 e 的边邻域。

2. 符号边控制的定义
现在我们给出核心定义。设 G = (V, E) 是一个图（通常假设没有孤立边）。一个符号边控制函数是一个函数 f: E -> {-1, +1}，它为每条边分配一个 +1（代表“正”）或 -1（代表“负”）的权重。
这个函数 f 要成为符号边控制函数，必须满足以下条件：对于图中的每一条边 e ∈ E，其边邻域内所有边的权重之和至少为 1。
用数学公式表达就是：对于任意边 e ∈ E，有 ∑_{e' ∈ N(e)} f(e') >= 1，其中 N(e) 是边 e 的边邻域。

3. 直观理解与示例
这个定义意味着什么？我们可以把每条边看作一个“哨兵”，它需要被其周围的边（即它的边邻域）所“支持”或“保护”。每条边都要求其周围的支援力量（权重和）至少达到一个正的单位值（即 >=1）。
让我们考虑一个最简单的图——由三条边构成的路径图 P₃（顶点序列为 A-B-C-D，边为 e1=AB, e2=BC, e3=CD）。

  • 边 e1 的邻域是 {e2}（因为它只与边 e2 共享顶点B）。
  • 边 e2 的邻域是 {e1, e3}（与e1共享B，与e3共享C）。
  • 边 e3 的邻域是 {e2}。
    现在，我们尝试构造一个符号边控制函数 f。
  • 如果我们尝试 f(e1)=+1, f(e2)=+1, f(e3)=+1：
    • 对于 e1：f(e2) = +1 >= 1，满足。
    • 对于 e2：f(e1) + f(e3) = +1 + +1 = 2 >= 1，满足。
    • 对于 e3：f(e2) = +1 >= 1，满足。
      所以 f = {+1, +1, +1} 是一个符号边控制函数。
  • 如果我们尝试 f(e1)=+1, f(e2)=-1, f(e3)=+1：
    • 对于 e1：f(e2) = -1，-1 < 1，不满足条件。
      所以这个赋值不是符号边控制函数。

4. 符号边控制数的定义
对于一个给定的图 G，通常存在许多不同的符号边控制函数。我们关心的是，在所有可能的符号边控制函数中，能找到的那个使得整个图所有边的权重总和最小的函数。这个最小的总和就称为图 G 的符号边控制数，记作 γ'_s(G)。
公式化定义：γ'_s(G) = min { ∑_{e ∈ E} f(e) }，其中 f 取遍 G 的所有符号边控制函数。

5. 计算符号边控制数的思路与性质
继续以路径图 P₃ 为例。我们已经知道 f = {+1, +1, +1} 是一个符号边控制函数，其总和为 +3。是否存在一个总和更小的函数？

  • 尝试 f(e1)=+1, f(e2)=+1, f(e3)=-1：
    • e1: f(e2)=+1 >=1，满足。
    • e2: f(e1)+f(e3)=+1 + (-1) = 0，0 < 1，不满足。
  • 尝试 f(e1)=-1, f(e2)=+1, f(e3)=+1：类似地，e3 的邻域和 f(e2)=+1 满足，但 e2 的邻域和 f(e1)+f(e3) = -1 +1 = 0，不满足。
  • 尝试 f(e1)=+1, f(e2)=-1, f(e3)=-1：
    • e1: f(e2)=-1，不满足。
  • 尝试 f(e1)=-1, f(e2)=+1, f(e3)=-1：
    • e1: f(e2)=+1，满足。
    • e2: f(e1)+f(e3) = -1 + (-1) = -2，不满足。
  • 尝试 f(e1)=-1, f(e2)=-1, f(e3)=+1：e3 满足，e2 不满足。
  • 尝试 f(e1)=-1, f(e2)=-1, f(e3)=-1：任何一条边的邻域和都是 -1 或 -2，均不满足。
    由此可见，对于 P₃，f = {+1, +1, +1} 是总和最小的符号边控制函数，因此 γ'_s(P₃) = 3。
    符号边控制数有一些基本性质：
  • 对于任意无孤立边的图 G，有 γ'_s(G) >= |E| - 2|M|，其中 M 是图的一个匹配。
  • 符号边控制数可以是负数。例如，对于一个圈图 C₄（4个顶点构成的圈），可以找到一个符号边控制函数，其总和为 0（例如，两条相邻边为 +1，另外两条为 -1），甚至可以找到总和为 -2 的函数。这表明负权重的边在满足局部约束的条件下，可以拉低全局总和。

6. 研究意义与扩展
符号边控制问题是对经典边控制问题（要求每条边邻域内至少有一条边被“选中”）的一种推广和深化。它通过引入负权重，丰富了控制理论的内涵，并使得问题在组合结构和计算复杂性上更具挑战性。研究符号边控制数的上界、下界，以及其在特定图类（如树、平面图、正则图等）上的精确值，是图论研究的一个活跃方向。此外，还存在许多变体，如全符号边控制（考虑边及其邻域）、k-符号边控制（邻域和至少为k）等，进一步扩展了这一理论框架。

图的符号边控制与符号边控制数 1. 基本概念引入 图的符号边控制是图论中控制理论的一个变种，它关注的是对图中边的“赋值”或“标记”，并研究这种赋值如何满足特定的全局条件。为了理解这个概念，我们首先需要明确几个基础构件： 图 (Graph) ：由顶点集合和边集合构成，边连接两个顶点。 边赋值 (Edge Assignment) ：为图中的每一条边分配一个数值。在符号边控制中，这个数值通常来自集合 {-1, +1} 。 边邻域 (Edge Neighborhood) ：对于任意一条边 e = uv ，它的（开）边邻域是指所有与 e 至少有一个公共顶点的边的集合，但不包括 e 本身。例如，与边 e 共享顶点 u 的所有其他边，以及共享顶点 v 的所有其他边，共同构成了 e 的边邻域。 2. 符号边控制的定义 现在我们给出核心定义。设 G = (V, E) 是一个图（通常假设没有孤立边）。一个 符号边控制函数 是一个函数 f: E -> {-1, +1} ，它为每条边分配一个 +1 （代表“正”）或 -1 （代表“负”）的权重。 这个函数 f 要成为符号边控制函数，必须满足以下条件：对于图中的 每一条 边 e ∈ E ，其边邻域内所有边的权重之和 至少为 1 。 用数学公式表达就是：对于任意边 e ∈ E ，有 ∑_{e' ∈ N(e)} f(e') >= 1 ，其中 N(e) 是边 e 的边邻域。 3. 直观理解与示例 这个定义意味着什么？我们可以把每条边看作一个“哨兵”，它需要被其周围的边（即它的边邻域）所“支持”或“保护”。每条边都要求其周围的支援力量（权重和）至少达到一个正的单位值（即 >=1）。 让我们考虑一个最简单的图——由三条边构成的路径图 P₃ （顶点序列为 A-B-C-D，边为 e1=AB, e2=BC, e3=CD）。 边 e1 的邻域是 {e2} （因为它只与边 e2 共享顶点B）。 边 e2 的邻域是 {e1, e3} （与e1共享B，与e3共享C）。 边 e3 的邻域是 {e2} 。 现在，我们尝试构造一个符号边控制函数 f 。 如果我们尝试 f(e1)=+1, f(e2)=+1, f(e3)=+1 ： 对于 e1 ： f(e2) = +1 >= 1 ，满足。 对于 e2 ： f(e1) + f(e3) = +1 + +1 = 2 >= 1 ，满足。 对于 e3 ： f(e2) = +1 >= 1 ，满足。 所以 f = {+1, +1, +1} 是一个符号边控制函数。 如果我们尝试 f(e1)=+1, f(e2)=-1, f(e3)=+1 ： 对于 e1 ： f(e2) = -1 ， -1 < 1 ，不满足条件。 所以这个赋值不是符号边控制函数。 4. 符号边控制数的定义 对于一个给定的图 G ，通常存在许多不同的符号边控制函数。我们关心的是，在所有可能的符号边控制函数中，能找到的那个使得 整个图所有边的权重总和最小 的函数。这个最小的总和就称为图 G 的 符号边控制数 ，记作 γ'_s(G) 。 公式化定义： γ'_s(G) = min { ∑_{e ∈ E} f(e) } ，其中 f 取遍 G 的所有符号边控制函数。 5. 计算符号边控制数的思路与性质 继续以路径图 P₃ 为例。我们已经知道 f = {+1, +1, +1} 是一个符号边控制函数，其总和为 +3 。是否存在一个总和更小的函数？ 尝试 f(e1)=+1, f(e2)=+1, f(e3)=-1 ： e1 : f(e2)=+1 >=1 ，满足。 e2 : f(e1)+f(e3)=+1 + (-1) = 0 ， 0 < 1 ，不满足。 尝试 f(e1)=-1, f(e2)=+1, f(e3)=+1 ：类似地， e3 的邻域和 f(e2)=+1 满足，但 e2 的邻域和 f(e1)+f(e3) = -1 +1 = 0 ，不满足。 尝试 f(e1)=+1, f(e2)=-1, f(e3)=-1 ： e1 : f(e2)=-1 ，不满足。 尝试 f(e1)=-1, f(e2)=+1, f(e3)=-1 ： e1 : f(e2)=+1 ，满足。 e2 : f(e1)+f(e3) = -1 + (-1) = -2 ，不满足。 尝试 f(e1)=-1, f(e2)=-1, f(e3)=+1 ： e3 满足， e2 不满足。 尝试 f(e1)=-1, f(e2)=-1, f(e3)=-1 ：任何一条边的邻域和都是 -1 或 -2 ，均不满足。 由此可见，对于 P₃ ， f = {+1, +1, +1} 是总和最小的符号边控制函数，因此 γ'_s(P₃) = 3 。 符号边控制数有一些基本性质： 对于任意无孤立边的图 G ，有 γ'_s(G) >= |E| - 2|M| ，其中 M 是图的一个匹配。 符号边控制数可以是负数。例如，对于一个圈图 C₄ （4个顶点构成的圈），可以找到一个符号边控制函数，其总和为 0 （例如，两条相邻边为 +1 ，另外两条为 -1 ），甚至可以找到总和为 -2 的函数。这表明负权重的边在满足局部约束的条件下，可以拉低全局总和。 6. 研究意义与扩展 符号边控制问题是对经典边控制问题（要求每条边邻域内至少有一条边被“选中”）的一种推广和深化。它通过引入负权重，丰富了控制理论的内涵，并使得问题在组合结构和计算复杂性上更具挑战性。研究符号边控制数的上界、下界，以及其在特定图类（如树、平面图、正则图等）上的精确值，是图论研究的一个活跃方向。此外，还存在许多变体，如 全符号边控制 （考虑边及其邻域）、 k-符号边控制 （邻域和至少为k）等，进一步扩展了这一理论框架。