图的分数边控制 我们先从熟悉的“边控制”概念入手。在图中，一个边集被称为 边控制集 ，如果图中每条边至少与该边集中的某条边相邻（有公共顶点）。 边控制数 γ‘(G) 是最小边控制集的大小。 现在，我们将这个概念推广到分数版本。在 分数边控制 中，我们允许为每条边e分配一个 权重 w(e)，其取值范围通常是[ 0, 1]。其目标是在满足“对图中每条边e，其自身及所有与其相邻的边的权重之和不小于1”的条件下，使得所有边的总权重 w(E) = Σ w(e) 最小。这个最小值称为图的 分数边控制数 ，记为 γ’_ f(G)。 用数学语言精确描述：一个函数 w: E(G) → [ 0, 1] 称为一个 分数边控制函数 ，如果对于每条边 e ∈ E(G)，都有 w(N[ e]) ≥ 1，其中 N[ e] = {e} ∪ {f ∈ E(G) | f 与 e 相邻} 是边e的闭邻域（包含e自身及其所有邻边）。那么，分数边控制数 γ’ f(G) = min { Σ {e∈E(G)} w(e) | w 是分数边控制函数 }。 接下来，我们看一个关键特性：分数边控制可以自然地表述为一个 线性规划（LP） 问题。其原始线性规划（Primal LP）就是上面的定义。更有趣的是，其 对偶线性规划（Dual LP） 对应着“分数边覆盖”的概念。一个分数边覆盖函数 g: E(G) → [ 0, 1] 要求对每个顶点v，关联于v的所有边的权重之和至少为1。分数边覆盖数 ρ_ f(G) 是此类函数的最小总权重。根据线性规划强对偶定理，有 γ’_ f(G) = ρ_ f(G)。这个等式建立了分数边控制与分数边覆盖的完美对偶关系，是其理论基石。 为了计算或估计 γ’_ f(G)，我们常利用其与匹配的关系。注意，任意一个 匹配 M（一组互不相邻的边）的指示函数（即M中边权重为1，其余为0）自然是一个边控制函数，因为匹配中的边互不相邻，一条边e若不在M中，则其必与M中至少一条边相邻（否则M可扩充），从而被控制。因此，γ’(G) ≤ |M|。分数版本下则有 γ’_ f(G) ≤ ν_ f(G)，其中 ν_ f(G) 是 分数匹配数 （权重和在[ 0,1]内，且每个顶点关联边权重和不超过1的最大总权重）。结合对偶性，我们得到 γ’_ f(G) = ρ_ f(G) ≤ ρ(G) （边覆盖数）且 γ’_ f(G) ≥ γ’(G)/Δ，其中Δ是最大度，这个下界来自将最优分数解“缩放”。 分数边控制数的计算复杂性是多项式时间的，因为它对应求解一个线性规划。然而，寻找“最优的整数边控制集”（即经典边控制数γ‘(G)）通常是NP难的，这体现了分数松弛的价值，它可以为经典问题提供紧的下界，并在近似算法中发挥核心作用。 最后，分数边控制与图的某些特定结构有关。例如，在 线图L(G) 中，原图G的边对应L(G)的顶点，原图边的相邻关系对应L(G)中顶点的相邻关系。那么，G的分数边控制问题等价于其线图L(G)的 分数顶点控制 问题。这一视角允许我们利用顶点控制理论来研究边控制，是图论中一种强有力的转化方法。