图的零强迫数与电力系统监控 基本概念引入 零强迫数（Zero Forcing Number）是图论中描述图“可控性”的参数，起源于电力网络监控问题。假设图中每个顶点代表一个电力节点（如变电站），初始时部分节点被安装传感器（称为“已染色”节点）。若某个已染色节点的所有邻居中仅有一个未染色节点，则该邻居会被“强迫”染色（即通过逻辑推断确定其状态）。重复此过程，若最终所有节点被染色，则初始染色集合称为 零强迫集 ，其最小大小即为图的零强迫数。 零强迫规则的形式化定义 给定图 \( G=(V,E) \) 和初始染色集合 \( S \subseteq V \)，零强迫过程按以下规则迭代： 若某个已染色顶点 \( u \) 的未染色邻居恰好只有一个（即 \( |N(u) \setminus S| = 1 \)），则该唯一邻居被染色。 若过程终止时 \( S \) 覆盖所有顶点，则 \( S \) 是零强迫集。零强迫数 \( Z(G) \) 是所有零强迫集的最小基数。 与电力系统监控的关联 在电力系统中，零强迫集对应最少数量的电压监测点。通过基尔霍夫定律和潮流方程，已知部分节点的电压可唯一确定全网状态。零强迫规则模拟了这种推导过程：若某节点的所有邻居除一个外均已知，则剩余邻居的状态可通过电路方程解出。 零强迫数的性质与计算 边界关系 ：对任意图 \( G \)，有 \( Z(G) \geq \delta(G) \)（最小度）且 \( Z(G) \leq n-1 \)（星图达到上界）。 与连通度的关系 ：若 \( G \) 的顶点连通度为 \( \kappa(G) \)，则 \( Z(G) \geq \kappa(G) \)。 NP难解性 ：寻找最小零强迫集是NP难问题，但对树、网格图等特殊图类存在多项式算法。 扩展模型与应用 功率支配集 ：推广零强迫规则，允许单个节点推断多个邻居的状态，更贴合电力系统的实际约束。 有向图零强迫 ：用于描述非对称信息流（如直流电网）。 故障容错 ：研究部分传感器失效时仍能监控全网的“强零强迫集”。 实例分析 以路径图 \( P_ 4 \)（顶点按顺序 \( v_ 1-v_ 2-v_ 3-v_ 4 \)）为例： 初始染色集 \( S=\{v_ 2\} \)：\( v_ 2 \) 强迫 \( v_ 1 \)（因 \( v_ 1 \) 是唯一未染色邻居），但 \( v_ 3,v_ 4 \) 无法被染色，故 \( S \) 不是零强迫集。 最小零强迫集为 \( S=\{v_ 1,v_ 3\} \)：\( v_ 1 \) 强迫 \( v_ 2 \)，随后 \( v_ 2 \) 强迫 \( v_ 3 \)，最终 \( v_ 3 \) 强迫 \( v_ 4 \)。因此 \( Z(P_ 4)=2 \)。 研究前沿 当前工作包括： 零强迫数与图的谱参数（如特征值）的关联； 动态零强迫（允许随时间增加监测点）； 在分布式传感器网络中的分布式算法设计。