二部圖中的完美匹配子集權(quán)的極小化問(wèn)題

李偉娟，陳光亭，陳 永，張 安

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

二部圖中的完美匹配子集權(quán)的極小化問(wèn)題

李偉娟，陳光亭，陳 永，張 安

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

主要研究了二部圖中的完美匹配子集權(quán)的極小化問(wèn)題，針對(duì)完美匹配兩個(gè)子集權(quán)的極小化問(wèn)題，證明了最小權(quán)重優(yōu)先算法SWF的最壞情況界為3/2，并應(yīng)用一一互換思想，設(shè)計(jì)了最壞情況界至多為4/3的改進(jìn)算法.

二部圖；完美匹配；近似算法；最壞情況界

0 引 言

1 問(wèn)題陳述及符號(hào)說(shuō)明

圖1 問(wèn)題示意圖

2 近似算法及最壞情況分析

最小權(quán)重優(yōu)先(Smallest Weight First, SWF)算法的基本步驟如下：

1)將權(quán)重按照從小到大的順序排序w(e1)≤w(e2)≤…≤w(e2n)；

2)從權(quán)重最小的邊開(kāi)始，依次放入當(dāng)前邊權(quán)和最小的子集U1或者U2里.

引理按照SWF算法，最終得到2個(gè)集合U1和U2里邊的條數(shù)一定相等.

證明反證法.若集合U1和U2里邊的個(gè)數(shù)不相等，一定存在一條邊em,不妨設(shè)em在U2，在em放入U(xiǎn)2之前，記w(U2)=sm，w(U1)=r分別表示子集U2，U1的權(quán)重，則有

sm+w(em)

(1)

定理1SWF算法的最壞情況界不超過(guò)3/2且是緊的.

證明記M1為SWF算法得到的完美匹配，設(shè)邊權(quán)w(e2n)放入子集U2時(shí)，U2中的邊權(quán)和記為s2n，則有

實(shí)例說(shuō)明3/2的界是緊的.Ui=2(i=1,2),U1有2個(gè)點(diǎn)u1，u2.U2有2個(gè)點(diǎn)u3,u4.V=4，V中有4個(gè)點(diǎn)v1，v2，v3，v4.各邊的權(quán)重分別為：

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 最優(yōu)解

圖3 算法解

下面給出改進(jìn)的一一互換算法.令U1，U2是e1，e2，…，e2n的一個(gè)劃分且Ui=n(i=1,2)，不妨假設(shè)w(Uq)er，Uq=Uq∪eres，稱為一次一一互換.易知，互換后的匹配最大權(quán)只可能減少.

互換算法的步驟如下：

1)將U任意劃分成邊數(shù)相等的兩個(gè)子集Ui(i=1,2)；

2)不斷進(jìn)行上述的一一互換過(guò)程，直至不能進(jìn)行互換為止.

定理2互換算法的最壞情況界至多是4/3.

證明記M2為互換算法得到的完美匹配，假定w(M*)=1(w(ei)除以w(M*)).因此對(duì)于劃分U1，U2有

(2)

假設(shè)w(U1)=1+α且w(U1)是子集中權(quán)和最大者，w(U2)是子集中權(quán)和較小者.記Δ12=w(U1)-w(U2)，δ12=minw(er)-w(es)|w(er)-w(es)>0，er∈U1，es∈U2若U1，U2已不能進(jìn)行一一互換了，那么Δ12≤δ12，根據(jù)式(2)可得

Δ12=w(U1)-w(U2)=2w(U1)-(w(U1)+w(U2))≥2(1+α)-2=2α.

3 結(jié)束語(yǔ)

本文主要研究了二部圖中的完美匹配子集權(quán)的極小化問(wèn)題，首先設(shè)計(jì)了最小權(quán)重優(yōu)先算法并證明了算法的最壞情況界為3/2且是緊的.其次，根據(jù)一一互換思想，設(shè)計(jì)的改進(jìn)算法的最壞情況界至多為4/3.下一步將對(duì)集合U的個(gè)數(shù)m>2的情況做進(jìn)一步研究.

[1] BARKETAU M, PESCH E, SHAFRANSKY Y. Minimizing maximum weight of subsets of a maximum matching in a bipartite graph[J]. Discrete Applied Mathematics, 2015,196:4-19.

[2] BOYSEN N, FLIEDNER M. Determining crane areas in intermodal transshipment yards: The yard partition problem[J]. European Journal of Operational Research, 2010,204(2):336-342.

[3] BOYSEN N, FLIEDNER M, JAEHN F, et al. A survey on container processing in railway yards[J]. Transportation Science, 2013,47(3):312-329.

[4] BURKARD R E, DELL’AMICO M, MARTELLO S. Assignment Problems, Revised Reprint[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2009:383-386.

[5] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity[M]. Englewood:Prentice-Hall, 1982:495-496.

[6] CARPANETO G, TOTH P. Algorithm for the solution of the bottleneck assignment problem[J]. Computing, 1981,27(2):179-187.

[7] FUJITO T, NAGAMOCHI H. A 2-approximation algorithm for the minimum weight edge dominating set problem[J]. Discrete Applied Mathematics, 2002,118(3):199-207.

MinimizingMaximumWeightofSubsetsofaPerfectMatchinginaBipartiteGraph

LI Weijuan, CHEN Guangting, CHEN Yong, ZHANG An

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

This paper studies the minimization problem of perfect matching subset weights in bipartite graphs. It first proves that the worst case ratio of the SWF algorithm is 3/2, and then an improved algorithm using the one to one exchange idea is presented, which is shown to be 4/3-approximation.

bipartite graph; perfect matching; approximation algorithm; worst-case ratio

O221.7

A

1001-9146(2017)05-0097-03

2016-12-05

國(guó)家自然科學(xué)基金資助項(xiàng)目(11571252，11401149)；浙江省自然科學(xué)基金資助項(xiàng)目(LY16A010015)

李偉娟(1989-)，女，河南滎陽(yáng)市人，碩士研究生，組合優(yōu)化.通信作者：陳光亭教授，E-mail：gtchen@hdu.edu.cn.

10.13954/j.cnki.hdu.2017.05.018