多部圖的最大匹配算法

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

(河北大學 數(shù)學與計算機學院 河北 保定 071002)

多部圖的最大匹配算法

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

(河北大學 數(shù)學與計算機學院 河北 保定 071002)

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

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

0 引言

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

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

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

1 預備知識

文中關(guān)于圖論的基本知識均來自文獻[8-10]，下面僅復習其中幾個概念.

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

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

為表述方便，給一個新的概念.

定義2設(shè)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的一個匹配.若M滿足vj∈Xj(j=1,2,…,k)，則稱M為G的一個通匹配.

2 模型建立

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

設(shè)用u1,u2,…,us表示s個工作人員，t項工作用v1,v2,…,vt表示，用w1,w2,…,wm表示m種報酬，令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可以獲得報酬wl，則vjwl之間有一條邊相連，j∈{1,2,…,t}，l∈{1,2,…,m}，用E表示上面給出的所有邊的集合，則得到一個3部圖(X1,X2,X3;E)，如何安排工作可以使更多的工作人員得到報酬，這樣問題可以轉(zhuǎn)化為求3部圖(X1,X2,X3;E)的最大通匹配問題.

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

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

3 算法

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

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

3.3算法復雜度分析

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

4 實例

下面通過一個實例說明，如何利用第3節(jié)給出的算法，得到相應的最大匹配問題.

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

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

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

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=?.

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

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

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

5 結(jié)束語

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

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

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

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

[4] 王偉，王錦彪. 中國民航飛機排班問題的多部圖模型[J].交通與計算機學報，2008,26(4):112-115.

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

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

[7] 林翠琴. 圖的匹配設(shè)計的矩陣構(gòu)造法[J].系統(tǒng)科學與數(shù)學學報，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

保定市科學技術(shù)研究項目,編號11ZG005.

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

O 23

A

1671-6841(2013)01-0027-03

10.3969/j.issn/1671-6841.2013.01.007