毛 華， 趙小娜, 史田敏， 毛曉亮， 劉 輝

(河北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院 河北 保定 071002)

多部圖的最大匹配算法

毛 華， 趙小娜, 史田敏， 毛曉亮， 劉 輝

(河北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院 河北 保定 071002)

匹配理論是圖論中一個(gè)重要的分支，已被廣泛地應(yīng)用于許多領(lǐng)域，如組合優(yōu)化、線性規(guī)劃、人工智能和矩陣論等.給出一個(gè)求解多部圖的最大匹配算法，并用仿真例子說(shuō)明其實(shí)用性和有效性，此算法為解決復(fù)雜的指派問(wèn)題開辟了新途徑.

匹配理論； 最大匹配； 多部圖

0 引言

圖論思想和方法越來(lái)越被許多科學(xué)領(lǐng)域所接受，并日益發(fā)揮它的重要作用.進(jìn)入21世紀(jì)以來(lái)，圖論又成為研究人員討論的熱點(diǎn),特別是圖論中的匹配知識(shí)在生產(chǎn)實(shí)踐中有著重要的應(yīng)用，多部圖的匹配作用更是如此，在實(shí)際生活中的“工作安排”、“體育比賽”等都用到多部圖匹配知識(shí).另外，在“交巡警安排”、“鐵路調(diào)度”、“公交調(diào)度”、“運(yùn)營(yíng)線路選擇”和“飛機(jī)排班問(wèn)題”等都有多部圖的成功運(yùn)用.此外，在知識(shí)發(fā)現(xiàn)、知識(shí)獲取以及人工智能等方面也有多部圖的有效應(yīng)用[1-7].

假設(shè)有n種不同的勞動(dòng)工具用集合{l1,l2,…,ln}表示，而每名工作人員會(huì)使用一種或幾種勞動(dòng)工具去從事不同的工作，如何達(dá)到盡可能多的工作人員使用不同的勞動(dòng)工具去從事不同的勞動(dòng)，對(duì)于這類問(wèn)題的解決，需要考慮的因素有人員、工具和工作.事實(shí)上，這是一類匹配的問(wèn)題，但是如果采用2部圖的模型已經(jīng)不能解決該問(wèn)題，因此必須建立新的數(shù)學(xué)模型，如3部圖等.解決這類問(wèn)題，一般地，若要考慮的因素有k個(gè)，那么可用k部圖建立其相應(yīng)的數(shù)學(xué)模型.

基于這類實(shí)際問(wèn)題以及多部圖的研究現(xiàn)狀，本文提出關(guān)于多部圖的最大匹配算法，不僅為研究多部圖的匹配問(wèn)題奠定了理論基礎(chǔ)，而且對(duì)于圖論本身也是一個(gè)貢獻(xiàn).

1 預(yù)備知識(shí)

文中關(guān)于圖論的基本知識(shí)均來(lái)自文獻(xiàn)[8-10]，下面僅復(fù)習(xí)其中幾個(gè)概念.

(2) 設(shè)v∈V(G)，G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目稱為v在G中的度，記作deg(v).為方便起見(jiàn)，稱度為零的頂點(diǎn)為孤立點(diǎn).

(3) 圖G稱為k部圖，若圖G的頂點(diǎn)集V(G)被分成k個(gè)不相交的子集X1,X2,…,Xk，并且圖G中沒(méi)有任何一條邊的2個(gè)端點(diǎn)在同一個(gè)Xj(j=1,2,…,k)中.

為表述方便，給一個(gè)新的概念.

定義2設(shè)G為一個(gè)k部圖，V(G)=X1∪X2∪…∪Xk，其中Xi∩Xj=?,(i≠j;i,j=1,2,…，k)，設(shè)M={v1v2,v2v3,…,vk-2vk-1,vk-1vk}為G的一個(gè)匹配.若M滿足vj∈Xj(j=1,2,…,k)，則稱M為G的一個(gè)通匹配.

2 模型建立

下面用一個(gè)3部圖描述所研究的模型.在實(shí)際生活中，人們通過(guò)勞動(dòng)得到應(yīng)有的報(bào)酬，這樣就有了人、勞動(dòng)和報(bào)酬之間的關(guān)系，而不是人和報(bào)酬之間的直接關(guān)系.

設(shè)用u1,u2,…,us表示s個(gè)工作人員，t項(xiàng)工作用v1,v2,…,vt表示，用w1,w2,…,wm表示m種報(bào)酬，令X1={u1,u2,…,us}，X2={v1,v2,…,vt}，X3={w1,w2,…,wm}，V=X1∪X2∪X3,易知X1∪X2∪X3=?.下面建立X1,X2,X3之間的關(guān)聯(lián)邊，若ui能勝任工作vj，則uivj之間有一條邊相連接，i∈(1,2,…,s)，j∈{1,2,…,t}，若工作vj可以獲得報(bào)酬wl，則vjwl之間有一條邊相連，j∈{1,2,…,t}，l∈{1,2,…,m}，用E表示上面給出的所有邊的集合，則得到一個(gè)3部圖(X1,X2,X3;E)，如何安排工作可以使更多的工作人員得到報(bào)酬，這樣問(wèn)題可以轉(zhuǎn)化為求3部圖(X1,X2,X3;E)的最大通匹配問(wèn)題.

故依據(jù)這類事實(shí)和圖論基本知識(shí)，本文將解決多部圖的有關(guān)內(nèi)容，所研究的多部圖的模型也是如上面的描述.

若圖中存在孤立點(diǎn)，則占用空間大，增大了算法的復(fù)雜度，但孤立點(diǎn)的存在并不影響通匹配的結(jié)果，故本文對(duì)存在孤立點(diǎn)的圖轉(zhuǎn)化為無(wú)孤立點(diǎn)的圖來(lái)研究.

3 算法

本節(jié)將給出多部圖的數(shù)學(xué)模型的解決算法，并對(duì)該算法的復(fù)雜度給予分析.

3.1算法的偽碼

Begin

M=?；G=(X1,X2,…,Xk;E)；

|X1|=m；

for (i=1;i≤m;i++)

{

for (j=1;jlt;k;j++)

}

}

OutputM.

3.2算法的依據(jù)法則

算法是優(yōu)先選取頂點(diǎn)度較小的元素，原因是若與該頂點(diǎn)匹配的元素較少，則應(yīng)優(yōu)先滿足，不然很可能得不到最大匹配結(jié)果；為了排除已匹配過(guò)的頂點(diǎn)，下一步只對(duì)刪去已匹配過(guò)頂點(diǎn)的剩余k部圖進(jìn)行匹配，這種匹配頂點(diǎn)排除法可以保證在進(jìn)行下一步分析匹配狀態(tài)時(shí)，不與已匹配過(guò)的頂點(diǎn)相重復(fù).在上述算法中，由于max{|X1|,|X2|,…，|Xk|}lt;，必有算法過(guò)程存在某一頂點(diǎn)集為空集?，這樣算法在有限步內(nèi)必停止，這時(shí)得到的匹配為最大通匹配.

3.3算法復(fù)雜度分析

令n=max{|X1|,|X2|,…,|Xk|}，由3.1給出的算法過(guò)程可以得到，求一個(gè)通匹配的算法復(fù)雜度為O(n(k-1))，而由于整個(gè)模型的最大匹配的個(gè)數(shù)至多為n，故整個(gè)算法的復(fù)雜度為O(n2(k-1)).

4 實(shí)例

下面通過(guò)一個(gè)實(shí)例說(shuō)明，如何利用第3節(jié)給出的算法，得到相應(yīng)的最大匹配問(wèn)題.

某公司小組現(xiàn)有4名工人a11,a12,a13,a14，不同的時(shí)間段b21,b22,b23，有不同的操作車間c31,c32,c33,c34,c35，有不同的生產(chǎn)設(shè)備d41,d42,d43,d44，生產(chǎn)的產(chǎn)品為e51,e52,e53,e54，若工人a11可以工作的時(shí)間段為b21,b22，在時(shí)間段b21里可以在車間c31,c32里工作，使用的生產(chǎn)設(shè)備都為d41，設(shè)備d41可以生產(chǎn)的產(chǎn)品為e51,e52,e53，有關(guān)系的頂點(diǎn)之間有一條邊相連.整個(gè)工作分配狀態(tài)見(jiàn)圖1，在這種狀態(tài)下，尋求一個(gè)最佳方案，使盡可能多的工人參加生產(chǎn)產(chǎn)品的工作.

圖1 5部圖Fig.1 5-partite graph

由圖1可以看出，這個(gè)問(wèn)題可歸結(jié)為一個(gè)討論5部圖的情況，此問(wèn)題可以歸結(jié)為第2節(jié)所建立的模型，故可由第3節(jié)給出的算法進(jìn)行討論.

Step15部圖G=(X1,X2,X3,X4,X5;E)，X1={a11,a12,a13,a14}，X2={b21,b22,b23}，X3={c31,c32,c33,c34,c35}，X4={d41,d42,d43,d44}，X5={e51,e52,e53,e54}，匹配M=?.

重復(fù)Step 2，得到的匹配M=M+a13b22c33d43e53+a12b21c31d41e51，此時(shí)K2=?，算法停止.

這樣，最大匹配結(jié)果為M={a14b23c35d44e54,a13b22c33d43e53,a12b21c31d41e51}.

求匹配a14b23c35d44e54的復(fù)雜度為O(9)，匹配a13b22c33d43e53的復(fù)雜度為O(10)，求匹配a12b21c31d41e51的復(fù)雜度為O(8)，求M的整個(gè)算法復(fù)雜度為O(27)與3.1節(jié)的算法復(fù)雜度一致，故3.1節(jié)的算法有效.

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

多部圖的匹配在實(shí)際生活中有重要的應(yīng)用，也是圖論的重要組成部分.本文利用多部圖的有關(guān)知識(shí)，為多部圖的匹配問(wèn)題提出新的算法，豐富了匹配的理論內(nèi)容，此算法可以在做最大匹配時(shí)達(dá)到簡(jiǎn)單、快速之目的.在以后的工作中，我們繼續(xù)研究有向圖的匹配、加權(quán)圖的匹配、有向加權(quán)圖的匹配和最大流相關(guān)的各類問(wèn)題，這些內(nèi)容預(yù)計(jì)都可以借用這里的思想完成.

[1] 毛華，史田敏，李斌.補(bǔ)圖方法在二部圖最大匹配中的應(yīng)用[J].黑龍江大學(xué)學(xué)報(bào):自然科學(xué)版，2012,29(3):289-293.

[2] 胡先富，李娜. 格上傳遞矩陣的性質(zhì)[J]. 四川師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009,32(6)：751-756.

[3] 于晶賢,宋岱才,趙曉穎,等.交巡警服務(wù)平臺(tái)的合理調(diào)度研究[J].科學(xué)技術(shù)與工程學(xué)報(bào)，2012,12(1):126-128.

[4] 王偉，王錦彪. 中國(guó)民航飛機(jī)排班問(wèn)題的多部圖模型[J].交通與計(jì)算機(jī)學(xué)報(bào)，2008,26(4):112-115.

[5] Song Xiaoxin，Liang Hongwei.Cover the vertices of a tree by machings[J]. 鄭州大學(xué)學(xué)報(bào):理學(xué)版，2006,38(1):24-27.

[6] 孫波，鐘聲. 帶匹配限制的交錯(cuò)路調(diào)課模型[J].廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2007,25(4):100-103.

[7] 林翠琴. 圖的匹配設(shè)計(jì)的矩陣構(gòu)造法[J].系統(tǒng)科學(xué)與數(shù)學(xué)學(xué)報(bào)，2000,20(2):140-148.

[8] Bondy J A, Murty U S R. Graph Theory with Applications[M]. New York: Elsevier, 1976:70-90.

[9] Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008:67-120.

[10] Tutte W T. Graph Theory[M].Cambridge: Cambridge University Press, 2001:16-40.

AnAlgorithmonMaximumMatchingofMultipartiteGraph

MAO Hua, ZHAO Xiao-na, SHI Tian-min, MAO Xiao-liang, LIU Hui

(CollegeofMathematicsandComputerScience,HebeiUniversity,Baoding071002,China)

As an important branch in graph theory, matching theory was applied in many fields such as combinatorial optimization, linear programming, artificial intelligence theoretical and matrix theory. An algorithm was provided relative to solving with the maximum matching of multipartite graph. The practicability and effectiveness of this algorithm was illustrated by a simulation example. This algorithm explored a new way dealing with complex allocation problems.

matching theory; maximum matching; multipartite graph

2012-10-30

保定市科學(xué)技術(shù)研究項(xiàng)目,編號(hào)11ZG005.

毛華(1963- )，女，教授，博士，主要從事概念格、數(shù)據(jù)挖掘、組合數(shù)學(xué)及網(wǎng)絡(luò)物流方向研究，E-mail:mh@hbu.edu.cn；通訊作者：趙小娜(1985-)，女，碩士，主要從事圖論和網(wǎng)絡(luò)物流研究，E-mail:shitianminzi@126.com.

O 23

A

1671-6841(2013)01-0027-03

10.3969/j.issn/1671-6841.2013.01.007