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

1、文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.第四章匹配問題及其應(yīng)用一、匹配理論概念及基本性質(zhì)（ 1）定義：1、設(shè) M 是圖 G 的邊子集，稱 M 是 G 中的一個 匹配，若 M 中任二邊在 G 中不相鄰； M 中的每條邊的兩個端點稱為 在 M 中相配；M 中每邊的端點稱為 被 M 許配；稱 M 為 G 的一個完全匹配 ，若 G 中每個頂點皆被 M 許配；稱 G 的最大匹配 ，若對任意的 G 的匹配 M ，均有 MM 。2、權(quán)數(shù)：對于匹配M ，它的權(quán)數(shù)為Me 。e M3、稱 M 為最優(yōu)匹配 ，若 M 為所有匹配中權(quán)數(shù)最大的匹配。4、稱 P 為關(guān)于匹配 M 的可擴路：設(shè) M

2、 是圖 G 的一個匹配， 若路 P 的邊在 M 中交替出現(xiàn)，且 P 的兩個端點是 M 不飽和的。5、稱 B 是 G 的一個覆蓋集：設(shè) BV G ，若 G 的每條邊皆與 B 中的頂相關(guān)聯(lián)。6、稱 B 是 G 的極小覆蓋 ：設(shè) BV G ，若 B 是 G 的一個覆蓋集，但vB ，Bv 不再是 G 的覆蓋集。7、稱 B 為 G 的最小覆蓋 ：設(shè) BV G ，若 B 是 G 的頂數(shù)最小的覆蓋集。8、G 的覆蓋數(shù)：最小覆蓋中頂?shù)臄?shù)目，記作G 。9、AB 為 A 與 B 的對稱差：AB= ABAB ，其中 A、B 為集合，有時也寫成AB 。（ 2）基本性質(zhì)：1、M是圖G 中的一個最大匹配當且僅當G 中無M

3、 的可擴路。2、設(shè)G 是二分圖，頂集的二分圖劃分為X 與Y ，滿足 V GXY ；XY；X中的任兩點不相鄰，Y 中亦然；XY ，記Xn ；文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.則存在把 X 中點皆許配的匹配的充要條件是SX ， N (S)S ，其中 N ( S) 是S 中每個點的鄰點組成的所謂S 的鄰集。求 G 的最大匹配 M 的算法：Step1：任取 G 的匹配 M ；Step2：若 Mn ，則 M 為 G 的最大匹配，算法終止；若不存在 M 的可擴路，則 M 為 G 的最大匹配，算法終止。否則轉(zhuǎn)到 Step3；Step3：取 M 的可擴路 P，作 MME P

4、。Eg：求圖 G 的最大匹配。路 P：123456作M M EP=M EPE P M=M EPE P M= 1,2 , 3,4 , 5,6Step1：取 Mx1, y2取 P1y2 x1 P1 上一邊在 M 中交叉出現(xiàn) x2 、 y1 都是 M 不飽和的P1 是關(guān)于 M 的可擴路。作 M 1M E P1 = x1 , y2 , x2 , y1Step2：對于 M ， P2y3 x2 也是可擴路。作M =MEP2=122, y123x , y, x, x ,yStep3：對于 M , P3y5 x4 也是可擴路。作 M= ME P3 = x1 , y2 , x2 , y1 , x2 ,y 3 ,

5、 x4 , y53、k 次正則 2 分圖有完備匹配， k>0。4、若 G 為二分圖，則其最大匹配的邊數(shù)為G 。5、圖 G 有完備匹配當且僅當SV G ，G S S，其中GS是GS中奇數(shù)個頂?shù)倪B通片的個數(shù)。文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.6、無橋三次正則圖有完備匹配（所謂橋是一條邊eE G，使得 Ge的連通片增加）。7、設(shè) K n,nG 是具有正常頂標l 的加權(quán)圖，取 G 的邊子集令 Gl 是以 El 為邊集的G 的生成子圖，如果 G l 有完備匹配 M ，則 M 即為 G的最佳匹配。8、 K 2n 是可以1 因子分解的，n1。9、 K 2n 1 存在每個因子

6、皆生成圈的2 因子分解，共計n 個生成圈。二、匹配問題的應(yīng)用圖論中涉及的匹配問題無論是在實際生活中還是在學(xué)習工作中都有著極其廣泛的應(yīng)用。應(yīng)用一：回顧這一章開頭提出的畢業(yè)生應(yīng)聘問題，設(shè)n 名畢業(yè)生為v1, v2 ,.,vn ，m 家招聘公司為u1, u2 ,., um 。我們造一個二分圖G，V EX UY ，X、Y是G 的二分圖頂劃分，其中Xv1 ,v2 ,., vn ， Yu1, u2 ,., um ，僅當 vi 可以接受的公司為u j 之間連一條邊， 如此構(gòu)成一個應(yīng)聘圖 G。我們欲給出一個有效算法，求得上述二分圖G中的最大匹配。與此問題相似的問題很多， 例如某城市有 n 名姑娘，m 名小伙子

7、都到了結(jié)婚的年齡，其中一些異性年輕人互相已有友情， 但姑娘們不愿輕率處理自己的終身大事，她們排除了一些小伙子作為自己的終身伴侶， 這樣她們實際上手頭 （心頭）有一份可嫁的名單，問最多有多少位姑娘可以嫁給她如意的人選？為解決諸如此類的問題， 1965 年匈牙利數(shù)學(xué)家埃德蒙茲 （ Edmonds）為之設(shè)計了一種命名為“匈牙利算法”的有效算法。1、匈牙利算法：（ 1） 設(shè) G 是連通的二分圖，在 G 中任取初始匹配 M ；（ 2） 若 M 把 X 中頂皆許配，止；否則取 X 中未被 M 許配的頂 u ,令 Su ,T（ 3） 若 N ST ，止， G 中無完備匹配；文檔來源為 :從網(wǎng)絡(luò)收集整理.wo

8、rd 版本可編輯 .歡迎下載支持.否則取 y N S T ；（ 4） 若 y 被 M 許配，設(shè) yz M , SSy ，轉(zhuǎn)（ 3）；否則取可增廣軌 p u, y ，令 MME P ，轉(zhuǎn)（ 2）。匈牙利算法實例應(yīng)用（摘自 2011 高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 B 題）：問題重述：（問題中地圖取自重慶市部分地圖）現(xiàn)就某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的5個問題： .根據(jù)該市中心城區(qū) A 的交通網(wǎng)絡(luò)和現(xiàn)有的20 個交巡警服務(wù)平臺的設(shè)置情況示意圖，為各交巡警服務(wù)平臺分配管轄范圍， 使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在 3 分鐘內(nèi)有交巡警（警車的時速為 60km/h）

9、到達事發(fā)地。 .對于重大突發(fā)事件，需要調(diào)度全區(qū) 20 個交巡警服務(wù)平臺的警力資源，對進出該區(qū)的 13 條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。 .根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內(nèi)再增加 2 至 5 個平臺，請確定需要增加平臺的具體個數(shù)和位置。 .針對全市（主城六區(qū) A ，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)， 分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案 （參見附件）的合理性。如果有明顯不合理，請給出解決方案。 .如果該市地點 P（第 32 個節(jié)點）處發(fā)生

10、了重大刑事案件， 在案發(fā) 3 分鐘后接到報警，犯罪嫌疑人已駕車逃跑。 為了快速搜捕嫌疑犯， 請給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。第二問的求解就是對“匈牙利算法”的應(yīng)用對于，本文從 20 個交巡警服務(wù)平臺中選出 13 個平臺封堵交通要道的思想出發(fā)，首先求出封堵的最短時間， 然后依據(jù)匈牙利算法， 并針對該問題進行適當改進，最后得出了最優(yōu)調(diào)度方案，具體方法如下：先在圖中找出 13 條交通要道的路點集合 G=12，14，16，21，22，23，24，28，29， 30，38，48，62根據(jù) Floyed 算法，求得每個交通平臺到各點的最短距離。根據(jù)匈牙利算法可文檔來源為 :從網(wǎng)絡(luò)收集整

11、理.word 版本可編輯 .歡迎下載支持.以在該問題中虛擬 7 個交通要道，并且每個平臺到這 7 個虛擬交通要道點的距離均為 ，這樣就可以把問題轉(zhuǎn)化為 20 個交通平臺分配到 20 個交通要道點的問題，由此得到改進后的匈牙利算法。并得到分配方案如下表所示：警力移動到相應(yīng)的 13 條交通要道點2384625 486 3072991610 1211 2212 241323142115281614并求得最小距離是8.01546 千米，也就是最少經(jīng)過8.01546 分鐘實現(xiàn)封鎖。把以上的匈牙利算法稍加修改就能夠用來求二分圖的最大完備匹配。最優(yōu)分派問題： 在人員分派問題中， 工作人員適合做的各項工作當中

12、，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。這個問題的數(shù)學(xué)模型是：在人員分派問題的模型中，圖G的每邊加了權(quán)( xi ,y j )0 ，表示 xi 做 y j 工作的效益，求加權(quán)圖G上的權(quán)最大的完備匹配。解決這個問題可以用庫恩曼克萊斯（Kuhn-Munkres）算法。2、KM 算法：（1）選定初始可行頂點標號l ，確定 Gl ，在 Gl 中取定初始匹配M ；（2）若 X 中頂點皆被 M 許配，停止， M 即G的權(quán)最大的完備匹配；否則，取Gl 中未被 M 許配的頂點u ，令Su， T；（3）若NGl(S)T，轉(zhuǎn)（ 4），若NGl(S)T，?。?） 選NGl(S)T中一頂點y ，若y

13、 已被 M 許配，且yzM ，SS z，T T y ，轉(zhuǎn)（ 3）；否則，取 Gl 中一個 M 的可擴路 p(u, y) ，令MME(p) ，轉(zhuǎn)（ 2）。其中 NGl (S) 是 G l 中 S的相鄰頂點集。KM 算法實例應(yīng)用例如 K ，的全矩陣為W，W的元素ij(x , y)， 1 i5， 1 j 5。5 5ij取正常初始頂點：l (yi )0,i1,2,3,4,5，l (x1)max1j max3,5,5,4,15，1 j 5l (x2 )max2 j max2,2,0,2,22，1 j 5文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.l (x3)max3 j max2

14、,4,4,1,04 ，1j5l (x4 )max4 j max0,1,1,0,01，1j5l (x5)max5 j max1,2,1,3,33.1j5構(gòu)造 Gl 如下圖所示，圖中粗實線是 Gl 上的最大匹配 M ， G l 無完備匹配，其頂標需要修改。取未被 M 許配的頂點x4 ， S x4 , x3 , x1 ， T y3 , y2 ，這時 NGl(S) T ，取_修改后的頂標為 l ( x1 )4 ，l ( x2 ) 2 ，l ( x3 )3 ，l ( x4 )0 ，l (x5 )3 ，l ( y1 )0 ，_l ( y2 ) 1， l ( y3 ) 1， l ( y4 )0 ， l ( y5 ) 0 。_對于 l ，得 Gl 如下圖所示，其上的粗實線是 Gl 上的完備匹配，從而由基本性質(zhì)7，我們以找到加權(quán)圖 K 5，5 上的一個最佳匹配 M x1 y4 , x2 y1, x3 y3 , x4 y2 , x5 y5 。應(yīng)用二：初中數(shù)學(xué)競賽1. 動物運動會進行龜兔 100m×2 跑，每只烏龜認識 10 只兔子，每只兔子認識 10 只