李伟娟，陈光亭，陈 永，张 安

(杭州电子科技大学理学院，浙江 杭州 310018)

二部图中的完美匹配子集权的极小化问题

李伟娟，陈光亭，陈 永，张 安

(杭州电子科技大学理学院，浙江 杭州 310018)

主要研究了二部图中的完美匹配子集权的极小化问题，针对完美匹配两个子集权的极小化问题，证明了最小权重优先算法SWF的最坏情况界为3/2，并应用一一互换思想，设计了最坏情况界至多为4/3的改进算法.

二部图；完美匹配；近似算法；最坏情况界

0 引 言

1 问题陈述及符号说明

图1 问题示意图

2 近似算法及最坏情况分析

最小权重优先(Smallest Weight First, SWF)算法的基本步骤如下：

1)将权重按照从小到大的顺序排序w(e1)≤w(e2)≤…≤w(e2n)；

2)从权重最小的边开始，依次放入当前边权和最小的子集U1或者U2里.

引理按照SWF算法，最终得到2个集合U1和U2里边的条数一定相等.

证明反证法.若集合U1和U2里边的个数不相等，一定存在一条边em,不妨设em在U2，在em放入U2之前，记w(U2)=sm，w(U1)=r分别表示子集U2，U1的权重，则有

sm+w(em)

(1)

定理1SWF算法的最坏情况界不超过3/2且是紧的.

证明记M1为SWF算法得到的完美匹配，设边权w(e2n)放入子集U2时，U2中的边权和记为s2n，则有

实例说明3/2的界是紧的.Ui=2(i=1,2),U1有2个点u1，u2.U2有2个点u3,u4.V=4，V中有4个点v1，v2，v3，v4.各边的权重分别为：

w(e1)=w(v1,u1)=w(v1,u3)=ε,w(e2)=w(v2,u2)=w(v2,u4)=1,w(e3)=w(v3,u3)=w(v3,u1)=1,w(e4)=w(v4,u4)=w(v4,u2)=2.

图2 最优解

图3 算法解

下面给出改进的一一互换算法.令U1，U2是e1，e2，…，e2n的一个划分且Ui=n(i=1,2)，不妨假设w(Uq)er，Uq=Uq∪eres，称为一次一一互换.易知，互换后的匹配最大权只可能减少.

互换算法的步骤如下：

1)将U任意划分成边数相等的两个子集Ui(i=1,2)；

2)不断进行上述的一一互换过程，直至不能进行互换为止.

定理2互换……