1、第四章匹配問題及其應用一、匹配理論概念及基本性質(1) 定義：1、設M是圖G的邊子集，稱M是G中的一個匹配，若M中任二邊在G中不相鄰；M中的每條邊的兩個端點稱為在M中相配；M中每邊的端點稱為被M許配；稱M為G的一個完全匹配，若G中每個頂點皆被M許配；稱G的最大匹配，若對任意的G的匹配M :均有M，蘭M。2、權數：對于匹配M，它的權數為 M = a e。e矽3、稱M為最優匹配，若M為所有匹配中權數最大的匹配。4、稱P為關于匹配M的可擴路：設M是圖G的一個匹配，若路P的邊在M中 交替出現，且P的兩個端點是M不飽和的。5、稱B是G的一個覆蓋集：設B V G，若G的每條邊皆與B中的頂相關聯。6稱B是G

2、的極小覆蓋：設B V G，若B是G的一個覆蓋集，但-v B， B - b不再是G的覆蓋集。7、稱B為G的最小覆蓋：設B V G，若B是G的頂數最小的覆蓋集。8、G的覆蓋數：最小覆蓋中頂的數目，記作1 G。9、AB為A與B的對稱差：A < B= A B - A B，其中A、B為集合，有 時也寫成A二B。(2) 基本性質：1、M是圖G中的一個最大匹配當且僅當 G中無M的可擴路。2、設G是二分圖，頂集的二分圖劃分為 X與丫，滿足 V G 二 X Y ； X Y； X中的任兩點不相鄰，丫中亦然； X <Y，記 x| = n ;則存在把X中點皆許配的匹配的充要條件是X , N(S)引S ,其

3、中N (S)是S中每個點的鄰點組成的所謂 S的鄰集。求G的最大匹配M的算法：Stepl:任取G的匹配M ;Step2:若M |啟n，則M為G的最大匹配，算法終止；若不存在M的可擴路，則M為G的最大匹配，算法終止 否則轉到Step3;Step3:取M的可擴路P，作M =M二E P。Eg：求圖G的最大匹配。1*6M ,2,3 , 4,5 /路 P： 123456作 M " =M 二 E P = M E P 川.E P M=M E P u i：E P M =1,2 , 3,4 , 5,6 /Stepl：取 M 二：Xt , y2 1取 Pi = y2XtPi上一邊在M中交叉出現 X2、yi

4、都是M不飽和的.Pi是關于M的可擴路。作 Mi = M 二 EPi= " Xi, y2 , X2, yi /Step2：對于m，P2 =3X2也是可擴路。 作 M = M 二 E P2 = 1 Xi, y? , X2, yi , X2詡 3 /Step3:對于M , p3 =y5x4也是可擴路。作 M ”=M 二 E P3 =：Xi,y2 , X2, yi , X2 ,y 3 , X4, y5 /.M = X3、k次正則2分圖有完備匹配，k>0。4、若G為二分圖，則其最大匹配的邊數為一：G。5、 圖G有完備匹配當且僅當/SuV(G )，0 (GS)|S，其中O (GS )是GS

5、 中奇數個頂的連通片的個數。6無橋三次正則圖有完備匹配(所謂橋是一條邊 eEG，使得G -e的連通片 增加)。7、設=G是具有正常頂標I的加權圖，取G的邊子集E = ：xy xy 三 E G , I x j 亠 I y = w xy #令Gi是以Ei為邊集的G的生成子圖，如果Gi有完備匹配M，則M即為G 的最佳匹配。8、K 2n是可以1因子分解的，n _1。9、k 2n 1存在每個因子皆生成圈的2因子分解，共計n個生成圈。二、匹配問題的應用圖論中涉及的匹配問題無論是在實際生活中還是在學習工作中都有著極其 廣泛的應用。應用一：回顧這一章開頭提出的畢業生應聘問題，設 n名畢業生為V1,v2,.,

6、vn，m家 招聘公司為U1,U2,，Um。我們造一個二分圖G，VE二XUY, X、丫是G的二 分圖頂劃分，其中X =匕，V2 ,，Vn /， Y = Ui , U2 ,., um /，僅當Vi可以接受的公司為Uj之間連一條邊，如此構成一個應聘圖G。我們欲給出 一個有效算法，求得上述二分圖G中的最大匹配。與此問題相似的問題很多，例如某城市有n名姑娘，m名小伙子都到了結婚 的年齡，其中一些異性年輕人互相已有友情， 但姑娘們不愿輕率處理自己的終身 大事，她們排除了一些小伙子作為自己的終身伴侶，這樣她們實際上手頭（心頭）有一份可嫁的名單，問最多有多少位姑娘可以嫁給她如意的人選？為解決諸如此類的問題，1

7、965年匈牙利數學家埃德蒙茲（EdmondS）為之設 計了一種命名為“匈牙利算法”的有效算法。1、匈牙利算法：（1） 設G是連通的二分圖，在 G中任取初始匹配M ;（2）若M把X中頂皆許配，止；否則取X中未被M許配的頂u ,令S = （u?,T;（3） 若N S =T，止，G中無完備匹配；否則取y N S T ；（4） 若y被M許配，設yzM,S=：S ，轉（3）；否則取可增廣軌p u,y，令M=M二EP，轉（2）。匈牙利算法實例應用（摘自2011高教社杯全國大學生數學建模競賽 B題）: 問題重述：（問題中地圖取自重慶市部分地圖）現就某市設置交巡警服務平臺的相關情況，建立數學模型分析研究下面的

8、5個問題：I 根據該市中心城區A的交通網絡和現有的20個交巡警服務平臺的設置情 況示意圖，為各交巡警服務平臺分配管轄范圍， 使其在所管轄的范圍內出現突發 事件時，盡量能在3分鐘內有交巡警（警車的時速為 60km/h）到達事發地。n .對于重大突發事件，需要調度全區 20個交巡警服務平臺的警力資源，對 進出該區的13條交通要道實現快速全封鎖。實際中一個平臺的警力最多封鎖一 個路口，請給出該區交巡警服務平臺警力合理的調度方案。川.根據現有交巡警服務平臺的工作量不均衡和有些地方出警時間過長的實 際情況，擬在該區內再增加2至5個平臺，請確定需要增加平臺的具體個數和位V.針對全市（主城六區A，B，C，D

9、，E，F）的具體情況，按照設置交巡警 服務平臺的原則和任務，分析研究該市現有交巡警服務平臺設置方案 （參見附件） 的合理性。如果有明顯不合理，請給出解決方案W 如果該市地點P (第32個節點)處發生了重大刑事案件，在案發3分鐘后 接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調度全市交巡 警服務平臺警力資源的最佳圍堵方案。第二問的求解就是對“匈牙利算法”的應用對于U，本文從20個交巡警服務平臺中選出13個平臺封堵交通要道的思想 出發，首先求出封堵的最短時間，然后依據匈牙利算法，并針對該問題進行適當 改進，最后得出了最優調度方案，具體方法如下：先在圖中找出13條交通要道的路點集合 G

10、= 12, 14, 16, 21, 22, 23, 24,28，29, 30, 38, 48, 62根據Floyed算法，求得每個交通平臺到各點的最短距離。根據匈牙利算法可 以在該問題中虛擬7個交通要道，并且每個平臺到這7個虛擬交通要道點的距離 均為：，這樣就可以把問題轉化為 20個交通平臺分配到20個交通要道點的問 題，由此得到改進后的匈牙利算法。并得到分配方案如下表所示：警力移動到相應的13條交通要道點2384625 486 30729916101211 2212 2413 2314 2115281614并求得最小距離是8.01546千米，也就是最少經過8.01546分鐘實現封鎖。把以上的

11、匈牙利算法稍加修改就能夠用來求二分圖的最大完備匹配。最優分派問題：在人員分派問題中，工作人員適合做的各項工作當中，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。這個問題的數學模型是：在人員分派問題的模型中，圖G的每邊加了權(Xi,yj)_0，表示Xi做yj工作的效益，求加權圖G上的權最大的完備匹配。解決這個問題可以用庫恩一曼克萊斯(Kuhn-Munkres)算法。2、KM算法：(1) 選定初始可行頂點標號l，確定Gi，在Gi中取定初始匹配M ；(2) 若X中頂點皆被M許配，停止，M即G的權最大的完備匹配；否則，取G|中未被M許配的頂點U，令S =u , T二一；(3) 若 Ngi(

12、S)二 T，轉(4),若 Ng|(S)=T，取二 min l(x) l(y) 一 (xy)x尋,y更l (v) _G1 , V E SI = « I (v) +ai , v w TI (v),其他(5) 選Ngi(S)-T中一頂點y，若y已被M許配，且yzM ,S = S z,T =TUy，轉(3)；否則，取G|中一個M的可擴路p(u,y),令M = M 二 E(p)，轉(2)。其中Ngi(S)是G|中S的相鄰頂點集。KM算法實例應用例如K5；5的全矩陣為W，W的元素F：(Xi , yj)，仁啟5，j < 5。-3554122022W =244100110012133取正常初始

13、頂點：l(yj=0, i =123,4,5,l(xj =maX 餌j =max3,5,5,4,1 =51上1(X2)=maX '2j =max2,2,0,2,2 =2，1 g <1(X3) = max 3 =max2,4,4,1,0H 4，1歿3l(x4) = max 4j二 max0,1,1,0,0 =1， 5j =max1,2,1,3,3 =3.構造G |如下圖所示，圖中粗實線是G| 上的最大匹配M，G|無完備匹配，其頂標需要修改。Xi,取未被M許配的頂點x4 ,S x4 , x3T 二y32，這時 Ng(S) =T，取二 min l(x) l(y) - .(xy) =1 x爭,y田修改后的頂標為 l(xi) =4 , I(X2)= 2 ,丨(X3) = 3 , 1(X4) = 0 , l (X5)=3 , 1 (yi) = 0 ,I (y2) -i , I(y3)=1 , I ( y 4) - 0 , I(y5)。對于I，得Gi如下圖所示，其上的粗實線是Gi 上的完備匹配，從而由基本性質7, 我們以找到加權圖K 5,5上的一個最佳匹配M = X1 y 4, X2y1, X3 y3, X4 y 2, X5 y5。應用二：初中數學競賽1.動物運動會進行龜兔100mx 2跑，每只烏龜認識10只兔子，每只兔子認識 10只烏龜。龜兔