图的分数边覆盖 我们从最基础的覆盖概念入手，循序渐进地理解图的分数边覆盖。 第一步：经典边覆盖的定义 首先，回顾一个经典图论概念。在一个无向图 G = (V, E) 中，一个“边覆盖”是指一个边集 C ⊆ E，使得图中的每一个顶点都至少与 C 中的某条边相关联。换句话说，边集 C “覆盖”了图的所有顶点。而“边覆盖数” ρ(G) 是指所有边覆盖中，所含边数最少的那个覆盖的边数。寻找最小边覆盖是一个经典的优化问题，并且有高效算法（例如，可通过最大匹配来构造：最小边覆盖 = 所有顶点 - 最大匹配的边数）。 第二步：从整数到分数——线性规划松弛 “分数”版本的思路，是对经典组合优化问题进行线性规划松弛。在经典的边覆盖问题中，我们为每条边 e 赋予一个0或1的决策变量 x_ e，表示这条边是否被选入覆盖集。约束条件是：对于每个顶点 v，与其关联的所有边的变量之和至少为1（即至少有一条边覆盖它）。目标是最小化所有 x_ e 的和。 分数边覆盖放松了变量的整数限制，允许 x_ e 在 [ 0, 1 ] 区间内取任意实数值。这样一来，我们得到一个线性规划问题： 最小化：∑_ {e ∈ E} x_ e 约束条件：对于每个顶点 v， ∑_ {e 关联 v} x_ e ≥ 1 变量范围：x_ e ≥ 0 这个线性规划的最优值，就称为图的“分数边覆盖数”，记为 ρ_ f(G)。显然，由于可行域扩大了，有 ρ_ f(G) ≤ ρ(G)。 第三步：对偶性与分数匹配 理解分数边覆盖的一个关键视角是其线性规划的对偶问题。原问题的对偶问题是： 最大化：∑_ {v ∈ V} y_ v 约束条件：对于每条边 e = uv， y_ u + y_ v ≤ 1 变量范围：y_ v ≥ 0 这个对偶问题恰好是“分数匹配”的线性规划形式！其中 y_ v 可以理解为分配给顶点 v 的“权重”，而约束条件 y_ u + y_ v ≤ 1 意味着一条边两端的权重之和不能超过1，这正好模拟了匹配中一条边不能被“重复使用”的思想。分数匹配的最大值记为 μ_ f(G)。根据强对偶定理，原问题和对偶问题的最优值相等，即： ρ_ f(G) = μ_ f(G) 第四步：与分数匹配的互补松弛关系 这个对偶关系揭示了分数边覆盖和分数匹配之间深刻的联系。它们是一对互补的问题。更进一步，对于最优的分数边覆盖解 {x_ e* } 和最优的分数匹配解 {y_ v* }，互补松弛条件成立： 如果某条边 e 的 x_ e* > 0，那么在对偶中对应的约束是紧的，即 y_ u* + y_ v* = 1。 如果某个顶点 v 的 y_ v* > 0，那么在原问题中对应的约束是紧的，即所有关联边 e 的 x_ e* 之和恰好为 1。 这意味着，在最优解下，被“积极使用”的边（x_ e > 0）其两端顶点的匹配权重之和必须达到上界1；而拥有正权重的顶点，其被边覆盖的总“强度”恰好是1（不松不紧）。 第五步：计算与性质 由于分数边覆盖是一个线性规划问题，它可以在多项式时间内求解（例如，使用椭球法或内点法）。对于一个 n 个顶点的图，我们有 ρ_ f(G) ≥ n/2，因为每条边最多覆盖两个顶点，要覆盖 n 个顶点单位权重，至少需要 n/2 的边权重和。等号成立当且仅当图存在完美分数匹配（即 μ_ f(G) = n/2）。特别地，在二分图中，由于线性规划的系数矩阵是全单模的，其分数最优解自动为整数解，因此对于二分图有 ρ_ f(G) = ρ(G)。但在非二分图中，分数边覆盖数可能严格小于整数边覆盖数，例如在奇环 C_ 3（三角形）中，ρ = 2，而 ρ_ f = 3/2 = 1.5。 总结 ：图的分数边覆盖是经典边覆盖问题的连续松弛，其最优值等于分数匹配数，并通过线性规划对偶性与分数匹配构成一对互补问题。它提供了从连续优化的视角分析图覆盖问题的一个有力工具，并且在二分图等特殊图类上与经典问题等价。