基于线性规划的图最大权匹配问题的线性规划松弛与舍入算法求解示例 题目描述 考虑一个无向图G=(V,E)，每条边e∈E有一个权重w_ e。图匹配是指边的集合M⊆E，使得任意两条边不共享顶点。最大权匹配问题要求找到一个匹配M，使得所有边的权重之和最大。当图是二分图时，该问题存在多项式时间算法（如匈牙利算法），但对于一般图，最大权匹配是NP难问题。本题目将展示如何利用线性规划松弛与随机舍入技术，设计一个近似算法来求解一般图上的最大权匹配问题。 解题过程 步骤1：建立整数线性规划模型 首先，为每条边e引入一个二进制变量x_ e：若边e在匹配M中，则x_ e=1；否则为0。目标是最大化总权重，同时满足匹配约束：每个顶点最多与一条边相连。 目标函数：maximize ∑_ {e∈E} w_ e x_ e 约束条件：对于每个顶点v∈V，∑_ {e∈δ(v)} x_ e ≤ 1（δ(v)表示与v相连的边集），且x_ e ∈ {0,1}。 这是一个整数规划，直接求解计算困难。 步骤2：线性规划松弛 将整数约束x_ e ∈ {0,1}松弛为0 ≤ x_ e ≤ 1，得到线性规划（LP）松弛问题： maximize ∑_ {e∈E} w_ e x_ e subject to: 对于每个v∈V，∑_ {e∈δ(v)} x_ e ≤ 1，且0 ≤ x_ e ≤ 1。 该LP可以在多项式时间内求解（如使用内点法），最优解记为x* 。 步骤3：随机舍入算法设计 LP解x* 是分数值，需转化为整数解（即匹配）。采用随机舍入： 独立处理每条边e：以概率x*_ e将边e加入初始集合S（否则不加入）。 由于随机舍入可能导致冲突（共享顶点的边同时被选中），需清理S：遍历S中的边，按随机顺序检查每条边，若其与已加入匹配M的边无冲突，则加入M；否则跳过。 步骤4：近似比分析 期望权值：由于每条边e以概率x* e独立入选S，E[ ∑ {e∈S} w_ e] = ∑_ {e∈E} w_ e x*_ e = LP最优值OPT_ LP。 冲突处理：由于每个顶点v的约束∑_ {e∈δ(v)} x*_ e ≤ 1，边e入选S后因冲突被移除的概率最多为1/2（通过条件概率分析可得）。因此，边e最终留在M的概率至少为x*_ e/2。 整体近似比：E[ ∑ {e∈M} w_ e] ≥ (1/2) ∑ {e∈E} w_ e x*_ e = OPT_ LP/2。由于OPT_ LP ≥ OPT（整数最优值），算法期望权值至少为OPT/2，即这是一个1/2-近似算法。 步骤5：实例演示 设图有顶点集{a,b,c,d}，边集及权重：e1=(a,b,w=3)，e2=(b,c,w=2)，e3=(c,d,w=4)，e4=(a,d,w=1)。 LP松弛求解：最优解x* {e1}=0.5, x* {e2}=0.5, x* {e3}=0.5, x* {e4}=0.5（满足每个顶点关联边变量和≤1）。OPT_ LP = 3×0.5 + 2×0.5 + 4×0.5 + 1×0.5 = 5。 随机舍入：假设随机选择S={e1,e3}（概率各0.5），无冲突直接作为匹配M，权值和为7；若S={e1,e2,e4}，则清理后可能得M={e1}（权值3）或M={e2,e4}（权值3）。多次运行取平均，期望权值接近2.5 ≥ OPT_ LP/2。 整数最优解：M={e1,e3}，权值7，算法在期望意义下达到至少50%最优解。 总结 通过LP松弛与随机舍入，将NP难问题转化为可高效求解的近似算法，平衡了计算复杂度与解的质量。此方法适用于一般图，且1/2近似比是紧的。