匹配問題及其應(yīng)用

1、第四章匹配問題及其應(yīng)用一、匹配理論概念及基本性質(zhì)（1）定義：1、設(shè)M是圖G的邊子集，稱M是G中的一個匹配，若M中任二邊在G中不相鄰；M中的每條邊的兩個端點稱為在M中相配；M中每邊的端點稱為被M許配；稱M為G的一個完全匹配，若G中每個頂點皆被M許配；稱G的最大匹配，若對任意的G的匹配M，均有M|m|o2、權(quán)數(shù)：對于匹配M,它的權(quán)數(shù)為Cm）=C）oeM3、稱M為最優(yōu)匹配，若M為所有匹配中權(quán)數(shù)最大的匹配。4、稱P為關(guān)于匹配M的可擴(kuò)路：設(shè)M是圖G的一個匹配，若路P的邊在M中交替出現(xiàn)，且P的兩個端點是M不飽和的。5、稱B是G的一個覆蓋集：設(shè)buV（G），若G的每條邊皆與B中的頂相關(guān)聯(lián)。6、稱B是G的極小

2、覆蓋：設(shè)buV（G），若B是G的一個覆蓋集，但vvB，Bv不再是G的覆蓋集。7、稱B為G的最小覆蓋：設(shè)buV（G），若B是G的頂數(shù)最小的覆蓋集。8、G的覆蓋數(shù)：最小覆蓋中頂?shù)臄?shù)目，記作B（g）。9、A0B為A與B的對稱差：AQB=（a|JB）-（AB），其中A、B為集合，有時也寫成AB。（）基本性質(zhì)：1、M是圖G中的一個最大匹配當(dāng)且僅當(dāng)G中無M的可擴(kuò)路。2、設(shè)G是二分圖，頂集的二分圖劃分為X與Y，滿足V（G）=XUY；XY=0；X中的任兩點不相鄰，Y中亦然；x|Y，記Ix|=n；則存在把X中點皆許配的匹配的充要條件是VS,X，N(S)|s|，其中N(S)是S中每個點的鄰點組成的所謂S的鄰集。求

3、G的最大匹配M的算法：Stepl：任取G的匹配M；Step2:若n，則M為G的最大匹配，算法終止；若不存在M的可擴(kuò)路，則M為G的最大匹配，算法終止。否則轉(zhuǎn)到Step3；Step3:取M的可擴(kuò)路P，作m=MEP)。Eg：求圖G的最大匹配。M=(2,3),(4,5)路P：l23456作M二MEP)=(ME(P)(EP)M)=(ME(P)(E(P)M)=紅2),(3,4),(5,6)Stepl：取M=(x,y)l2取P=yx2lP上一邊在M中交叉出現(xiàn)lx、y都是M不飽和的2l0。4、若G為二分圖，則其最大匹配的邊數(shù)為b（g）。5、圖G有完備匹配當(dāng)且僅當(dāng)VSuV（G），O（G-S）1。2n9、k存在每

4、個因子皆生成圈的2因子分解，共計n個生成圈。2n+1二、匹配問題的應(yīng)用圖論中涉及的匹配問題無論是在實際生活中還是在學(xué)習(xí)工作中都有著極其廣泛的應(yīng)用。應(yīng)用一：回顧這一章開頭提出的畢業(yè)生應(yīng)聘問題，設(shè)n名畢業(yè)生為v,vv，m家12n招聘公司為u,uu。我們造一個二分圖G,V,E）=XY，X、Y是G的二12m分圖頂劃分，其中X=v,v,.,v，Y=u,u,.,u，12n12m僅當(dāng)v可以接受的公司為u之間連一條邊，如此構(gòu)成一個應(yīng)聘圖G。我們欲給出ij一個有效算法，求得上述二分圖G中的最大匹配。與此問題相似的問題很多，例如某城市有n名姑娘，m名小伙子都到了結(jié)婚的年齡，其中一些異性年輕人互相已有友情，但姑娘們

5、不愿輕率處理自己的終身大事，她們排除了一些小伙子作為自己的終身伴侶，這樣她們實際上手頭（心頭）有一份可嫁的名單，問最多有多少位姑娘可以嫁給她如意的人選？為解決諸如此類的問題，1965年匈牙利數(shù)學(xué)家埃德蒙茲（Edmonds）為之設(shè)計了一種命名為“匈牙利算法”的有效算法。1、匈牙利算法：（1）設(shè)G是連通的二分圖，在G中任取初始匹配M；（2）若M把X中頂皆許配，止；否則取X中未被M許配的頂u，令S=u,T=,；（3）若N（S）二T，止，G中無完備匹配；否則取yGNS）-T；（4）若y被M許配，設(shè)yzGM,S=Sy，轉(zhuǎn)（3）；否則取可增廣軌pu,y，令M=MEP，轉(zhuǎn)（2）。匈牙利算法實例應(yīng)用（摘自20

6、11高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題）：問題重述：（問題中地圖取自重慶市部分地圖）現(xiàn)就某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的5個問題：I.根據(jù)該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況示意圖，為各交巡警服務(wù)平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有交巡警（警車的時速為60km/h）到達(dá)事發(fā)地。II對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。III根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡

7、和有些地方出警時間過長的實際情況，擬在該區(qū)內(nèi)再增加2至5個平臺，請確定需要增加平臺的具體個數(shù)和位置。V.針對全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案（參見附件）的合理性。如果有明顯不合理，請給出解決方案。如果該市地點P(第32個節(jié)點)處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。第二問的求解就是對“匈牙利算法”的應(yīng)用對于II,本文從20個交巡警服務(wù)平臺中選出13個平臺封堵交通要道的思想出發(fā)，首先求出封堵的最短時間，然后

8、依據(jù)匈牙利算法，并針對該問題進(jìn)行適當(dāng)改進(jìn)，最后得出了最優(yōu)調(diào)度方案，具體方法如下：先在圖中找出13條交通要道的路點集合G=12,14,16,21,22,23,24,28,29,30,38,48,62根據(jù)Floyed算法，求得每個交通平臺到各點的最短距離。根據(jù)匈牙利算法可以在該問題中虛擬7個交通要道，并且每個平臺到這7個虛擬交通要道點的距離均為，這樣就可以把問題轉(zhuǎn)化為20個交通平臺分配到20個交通要道點的問題，由此得到改進(jìn)后的匈牙利算法。并得到分配方案如下表所示：警力移動到相應(yīng)的13條交通要道點01356并求得最小距離是千米，也就是最少經(jīng)過分鐘實現(xiàn)封鎖。把以上的匈牙利算法稍加修改就能夠用來求二分圖

9、的最大完備匹配。最優(yōu)分派問題：在人員分派問題中,工作人員適合做的各項工作當(dāng)中,效益未必一致,我們需要制定一個分派方案,使公司總效益最大。這個問題的數(shù)學(xué)模型是：在人員分派問題的模型中，圖G的每邊加了權(quán),(x,y)0，表示x做y工作的效益，求加權(quán)圖G上的權(quán)最大的完備匹配。ijij解決這個問題可以用庫恩一曼克萊斯(Kuhn-Munkres)算法。2、KM算法：選定初始可行頂點標(biāo)號l,確定G，在G中取定初始匹配M；ll若X中頂點皆被M許配，停止，M即G的權(quán)最大的完備匹配；否則，取G中未被M許配的頂點u,令S=u,T=;l若N(S)T,轉(zhuǎn)(4),若N(S)=T,取GlGlaminl(x)+l(y)，(x

10、y)lxuS,yTl(v)-a,veS/ll(v)+a,veTl(v),其他選N(S)-T中一頂點y，若y已被M許配，且yzeM,SSz，GlTTy，轉(zhuǎn)(3)；否則，取g中一個M的可擴(kuò)路p(u,y),令MME(p)，轉(zhuǎn)(2)。其中N(S)是g中S的相鄰頂點集。GllKM算法實例應(yīng)用例如K的全矩陣為W，5，5W的元素(x,y)，1i5，1j5。ijij_355422022W244100110012133取正常初始頂點：l(y)0,i1,2,3,4,5，il(x)max1j51jmax3,5,5,4,15，l(x)max1j52jmax2,2,0,2,22，l(x)max1j53jmax2,4,4

11、,1,04l(x)max1j54jmax0,1,1,0,01，l(x)max1j55jmax1,2,1,3,33.構(gòu)造G如下圖所示，圖中粗實線是G上的最大匹配M,llG無完備匹配，其頂標(biāo)l需要修改。Sx,x，1,x43Ty,y，這時N(S)T，取32Gl取未被M許配的頂點x4aminl(x),l(y)一(xy)=1lxS,yT修改后的頂標(biāo)為/(x)4，/(x)2，/(x)3，/(x)0,/(x)3，/(y)=0,123451l(y)1，l(y)1，l(y)0，l(y)0。2345對于_，得G如下圖所示，其上的粗實線是G上的完備匹配，從而由基本性質(zhì)7,ll我們以找到加權(quán)圖K上的一個最佳匹配Mxy,xy,xy,xy,xy。5，51421334255應(yīng)用二：初中數(shù)學(xué)競賽1.動物運動會進(jìn)行龜兔100mX2跑，每只烏龜認(rèn)識10只兔子，每只兔子認(rèn)識10只烏龜。龜兔們都要求和自己的朋友組隊（每隊一龜一兔）