图的容错控制 我们先从最基础的“控制”概念开始。在图中，一个顶点控制着它自身以及所有与其直接相邻的顶点（即它的邻居）。一个顶点集 S 是图 G 的一个 控制集 ，如果图中的每一个顶点要么在 S 中，要么与 S 中的某个顶点相邻。控制集的核心思想是“覆盖”或“监控”——S 中的顶点能“监控”到整个图的所有顶点。控制数是满足条件的最小控制集的大小，是图的重要参数。 然而，实际系统中，顶点（代表处理器、传感器、设施等）可能发生故障。经典的控制集定义是脆弱的：一旦 S 中某个顶点失效，它自身及其能监控的邻居就可能失去监控。为了增强系统的鲁棒性，人们提出了各种 容错控制 的概念。其核心思想是：在图中寻找一个顶点子集 S，使得即使 S 中的某些顶点（或它们所关联的边）失效，剩余部分依然能够控制整个图。 最典型的一种是 多重控制 ，更具体地，我们重点讲解 k-控制 或称 k-支配 。对于一个正整数 k，一个顶点集 S 称为图 G 的一个 k-控制集 ，如果对于图中 每一个 不在 S 中的顶点 v，v 在 S 中 至少拥有 k 个邻居 。也就是说，任意一个“平民”顶点都被 S 中的“警卫”严密保护，即使有 (k-1) 个警卫失效，至少还有一个警卫能看住它。k-控制数 γ_ k(G) 就是最小的 k-控制集的大小。显然，当 k=1 时，这就是经典的控制。 但 k-控制只保证了“平民”的容错，没有保护“警卫”自身。如果 S 中的一个顶点 u 失效，它自己就失去了被监控的能力。为了应对这种情况，定义了 全控制 。一个顶点集 S 是 全控制集 ，如果图中 每一个 顶点（包括 S 内部的顶点）都与 S 中另一个顶点相邻。这意味着每个顶点身边至少有一个“警卫”，包括警卫之间也互相照看。全控制数 γ_ t(G) 是最小的全控制集的大小。 很自然地，我们将这两者结合，得到 容错控制中最重要、研究最广泛的概念之一：k-全控制 。对于一个正整数 k，一个顶点集 S 称为图 G 的一个 k-全控制集 ，如果对于图中 每一个 顶点 v（无论 v 是否在 S 中），v 在 S 中 至少拥有 k 个邻居 。换言之，每个顶点都被 S 中的顶点“多重覆盖”。这使得系统具有强大的容错能力：即使任意 (k-1) 个控制顶点（或它们发出的监控信号）失效，每个顶点仍然至少被一个有效的控制顶点监控着。图 G 的 k-全控制数 ，记为 γ_ {kt}(G)，是满足条件的最小 k-全控制集的大小。 我们来看一个简单例子。考虑一个由四个顶点构成的“正方形”（4-环）C4，顶点按顺序为 v1, v2, v3, v4。 经典控制：{v1, v3} 是一个控制集，控制数为2。 2-控制：需要每个不在S中的顶点在S中有2个邻居。取 S={v1, v2, v3}，检查v4，它在S中有邻居v1和v3，满足。控制数为3。（注意{v1, v3}不满足，因为v2和v4在S中都只有一个邻居）。 全控制：{v1, v3} 是全控制集吗？v1的邻居是v2和v4，都不在S中，所以v1自己没有被S中其他顶点控制，因此不是。{v1, v2, v3} 是全控制集，因为v1（邻居v2）、v2（邻居v1或v3）、v3（邻居v2）、v4（邻居v1和v3）都满足条件。全控制数为3。 2-全控制：每个顶点需要在S中有2个邻居。在C4中，必须取S为全部四个顶点，因为任何大小为3的集合，都会导致剩下的那个顶点在S中只有1个邻居。所以2-全控制数为4。 k-全控制数的计算通常是 NP-难的，因此研究其上下界、与图的其他参数（如阶数n、最小度δ、最大度Δ等）的关系，以及特殊图类（如树、网格、超立方体、平面图等）上的精确值和多项式时间算法，是该领域的核心内容。一个基本的下界是：对于最小度 δ ≥ k 的图，有 γ_ {kt}(G) ≥ kn/(δ+1)。上界则与图的连通性和度分布密切相关。 除了多重和全控制，还有其他容错控制模型，例如： 冗余控制 ：控制集S是冗余的，如果移除S中任意一个顶点后，剩下的集合仍然是控制集。这比2-控制弱，因为它只要求对S内顶点失效有容错，不要求“多重覆盖”。 故障可恢复控制 ：要求控制集S在至多f个顶点（或边）发生任意故障后，能够通过调整（例如，添加少量顶点）快速恢复成一个控制集。 罗马控制、符号控制 等：这些模型通过给顶点赋权值（如{-1, 0, 1}或{0,1,2}）来定义控制条件，其容错性体现在权值分配方案的内在冗余上。 容错控制 广泛应用于网络设计、无线传感器网络、监控系统、软件工程（模块放置）和电力网络等领域，其目标是设计出成本（控制集大小）和鲁棒性（容错能力）之间达到最佳平衡的资源部署方案。理解其从经典控制到多重、全控制，再到k-全控制的概念演化，是掌握这一图论应用分支的关键。