基于线性规划的图最小环基问题的线性规划建模与求解示例 我们考虑 图最小环基问题 。给定一个无向连通图 \( G = (V, E) \) ，每条边 \( e \in E \) 有一个非负权重 \( w(e) \) 。图的一个环基是指一组环（圈的并）的集合，使得图中每个环都可以表示为这组环的对称差（即模2加法）。最小环基问题是寻找一个总权重最小的环基。该问题在网络设计、电路分析等领域有应用。 步骤1：问题建模（整数规划） 首先，注意到在一个连通图中，最小环基与图的一棵生成树密切相关：每个非树边与树路径构成一个基本环，所有基本环构成一个环基，但不一定是最小权重的。更一般地，我们需要选取一组环，使它们线性无关（在环空间的 \( \mathbb{F}_ 2 \) 向量空间中）且总权重最小。 设 \( \mathcal{C} \) 为图 \( G \) 中所有简单环（圈）的集合（可能指数级多）。对于每个环 \( C \in \mathcal{C} \) ，引入二元变量 \( x_ C \)： \[ x_ C = \begin{cases} 1, & \text{如果环 } C \text{ 被选入环基}\\ 0, & \text{否则} \end{cases} \] 环基必须满足： 数量条件 ：环基中环的数量等于图的环维数 \( m - n + 1 \) （其中 \( m = |E|, n = |V| \) ，即图的第一贝蒂数）。 线性无关性 ：选出的环集合在 \( \mathbb{F}_ 2 \) 下线性无关。 线性无关的约束很难直接表达，但我们可以利用对偶观点：在 \( \mathbb{F}_ 2 \) 中，一组向量线性无关当且仅当存在一组“边”上的函数（对偶变量）使得这些环与其内积构成一个可逆矩阵。另一种方法是直接要求选出的环能生成整个环空间，且数量正好是环维数，这等价于：对每条非树边 \( e \) ，选出的环集合中必须至少有一个环包含 \( e \) ，并且这些环在某种意义下是“基本环”的线性组合。 更实用的建模思路：固定一棵生成树 \( T \) 。对于每条非树边 \( e \in E \setminus T \) ，定义基本环 \( C_ e \) 为 \( e \) 加上 \( T \) 中连接 \( e \) 两端点的唯一路径。那么任意环都可以表示为若干基本环的对称差。因此，我们可以将选取环基的问题转化为：选取一组非树边 \( F \subseteq E \setminus T \) ，使得对应的基本环集合 \( \{ C_ e : e \in F \} \) 线性无关，并且我们希望最小化这些基本环的总权重。但注意，基本环的权重可能不是最小的，因为可能存在其他环权重更小。 另一种常见方法是利用 拟阵理论 ：图的环拟阵的对偶是余环拟阵，最小环基问题等价于在余环拟阵中寻找最大权基（符号反转）。但我们这里直接采用整数线性规划建模： 对每条边 \( e \in E \) ，引入辅助变量 \( y_ e \in \{0,1\} \) 表示边 \( e \) 是否被至少一个选中的环覆盖。同时，我们要求选中的环集合能够“生成”整个环空间。这可以通过约束：对任意非空边集 \( S \subseteq E \) ，如果 \( S \) 是一个割集（即删除 \( S \) 后图不连通），则 \( S \) 必须与选中的环集合有偶数条边相交（在 \( \mathbb{F}_ 2 \) 中为0）。这是因为环与割集的内积为0（在 \( \mathbb{F}_ 2 \) 中）。这个约束保证了选中的环集合是环空间中的子空间，且如果环数量等于环维数，则构成一组基。 然而，割集数量是指数级的。我们可以利用 生成树的对偶性 来化简：固定一棵生成树 \( T \) 。对于每条树边 \( t \in T \) ，定义对应的基本割集 \( D_ t \) 为：删除 \( t \) 后，将树分成两个连通分量，连接这两个分量的所有边（包括 \( t \) ）构成的集合。那么，任何环与每个基本割集 \( D_ t \) 的交的边数必须为偶数。因此，我们只需要对每条树边 \( t \in T \) 施加这样的约束，即可保证与所有割集正交。 令 \( x_ C \in \{0,1\} \) 表示环 \( C \) 是否被选中。总权重最小化目标为： \[ \min \sum_ {C \in \mathcal{C}} w(C) x_ C \] 其中 \( w(C) = \sum_ {e \in C} w(e) \) 。 约束： 环数量等于环维数： \[ \sum_ {C \in \mathcal{C}} x_ C = m - n + 1 \] 对于每条树边 \( t \in T \) ，要求选中的环集合与基本割集 \( D_ t \) 的交的边数（模2）为0： \[ \sum_ {C \in \mathcal{C}} |C \cap D_ t| \cdot x_ C \equiv 0 \pmod{2}, \quad \forall t \in T \] 但模2约束不是线性的。我们可以将其线性化：引入变量 \( z_ {C,t} \in \{0,1\} \) 表示环 \( C \) 与割集 \( D_ t \) 的交的边数的奇偶性（即 \( |C \cap D_ t| \mod 2 \) ）。由于 \( |C \cap D_ t| \) 的奇偶性等于环 \( C \) 是否包含树边 \( t \) （因为基本割集 \( D_ t \) 包含 \( t \) 以及其他跨两个分量的边，但环与割集相交的边数必为偶数当且仅当环不包含 \( t \) ？需要仔细分析：实际上，环如果包含树边 \( t \) ，则它必须也包含另一条跨分量的边（因为环是封闭的），所以环与割集 \( D_ t \) 的交的边数至少为2，是偶数。但环可能包含多条跨分量的边，所以交的边数总是偶数。等等——这里有一个关键点：在无向图中，环与割集的交的边数总是偶数（这是图论的基本定理）。因此，模2约束总是自动满足！所以这个约束不能用来保证线性无关性。 因此，我们需要另一种方式保证线性无关性。一种方法是直接要求选中的环构成环空间的一组基，这等价于：存在一个 \( (m-n+1) \times (m-n+1) \) 的满秩矩阵，其行对应选中的环，列对应一组线性无关的边（例如非树边）。这又回到拟阵基的条件。 更常见的方法是将问题转化为 整数线性规划 ：我们不是直接选环，而是先固定一组基环（例如基于生成树的基本环），然后允许环的线性组合。但这会使问题变得复杂。 实际上，最小环基问题有多项式时间算法（如 Horton 算法），但这里我们展示如何用线性规划松弛来建模，并可能用于分支定界求解。 步骤2：线性规划松弛 我们放松整数约束，允许 \( x_ C \geq 0 \) ，并且不要求线性无关性，而是要求环集合能够“覆盖”所有边？这不对，因为环基并不需要覆盖所有边。 一种启发式松弛：我们要求对每条边 \( e \) ，包含 \( e \) 的环的“总权重”至少为某个值？这缺乏明确意义。 由于原整数规划涉及指数级变量（环的数量），并且约束难以线性化，通常不会直接求解这个线性规划松弛。但我们可以考虑其 对偶问题 ，可能对应到某种“覆盖”或“打包”问题。 步骤3：简化建模（基于生成树） 在实际计算中，通常采用以下方法： 枚举所有“相关环”（例如 Horton 算法中只考虑最短路径环）。 定义环-边关联矩阵 \( A \) ，其中 \( A_ {C,e} = 1 \) 如果环 \( C \) 包含边 \( e \) ，否则为0。 环基的线性无关性等价于矩阵 \( A \) 的对应行满秩。 但线性无关性约束是组合的，难以线性化。因此，最小环基问题通常通过组合算法（如贪心算法）求解，而不是通过线性规划。 步骤4：示例图与求解 我们构造一个小图示例：设图有4个顶点 \( V = \{1,2,3,4\} \) ，边 \( E = \{a,b,c,d,e\} \) ，权重 \( w(a)=1, w(b)=2, w(c)=3, w(d)=4, w(e)=5 \) 。连接关系：a=(1,2), b=(2,3), c=(3,4), d=(1,4), e=(2,4) 。该图环维数 = 5 - 4 + 1 = 2 。 简单环列表 \( \mathcal{C} \) ： \( C_ 1: a-b-e-d \) （权重1+2+5+4=12） \( C_ 2: b-c-e \) （2+3+5=10） \( C_ 3: a-d-c-b \) （1+4+3+2=10） \( C_ 4: a-b-c-d \) （1+2+3+4=10） \( C_ 5: d-c-e \) （4+3+5=12） \( C_ 6: a-d-e-b \) （1+4+5+2=12） 我们需要选择2个环，使得它们线性无关（即不能完全相同，且不能一个环是另一个的对称差？实际上，两个环线性相关当且仅当它们相同或对称差为0，所以只要两个环不同，在 \( \mathbb{F}_ 2 \) 中它们总是线性无关的，除非其中一个为0环。因此，在这个小例子中，任意两个不同的环都构成环基。 所以问题简化为：从所有环中选取两个环，使总权重最小。显然，选取两个权重最小的环：\( C_ 2 \) (10) 和 \( C_ 3 \) (10) 或 \( C_ 4 \) (10) ，总权重20。 如果使用线性规划建模，变量 \( x_ {C_ 1}, \dots, x_ {C_ 6} \geq 0 \) ，约束 \( x_ {C_ 1} + \dots + x_ {C_ 6} = 2 \) ，且整数约束。目标最小化 \( 12x_ {C_ 1} + 10x_ {C_ 2} + 10x_ {C_ 3} + 10x_ {C_ 4} + 12x_ {C_ 5} + 12x_ {C_ 6} \) 。线性规划松弛的最优解可能是分数解，例如 \( x_ {C_ 2}=x_ {C_ 3}=x_ {C_ 4}=2/3 \) ，其他为0，目标值 \( 10* (2/3)* 3 = 20 \) ，与整数最优解相同。 步骤5：总结 最小环基问题的线性规划建模较为复杂，主要难点在于环的线性无关性约束难以线性化。在实际应用中，通常采用组合算法（如基于所有点对最短路径的 Horton 算法）在多项式时间内求解。线性规划方法可能用于分支定界框架中，但需处理指数级变量（列生成）和复杂约束。本例展示了如何将问题形式化为整数线性规划，并说明在小例子中求解的基本思路。