1、1. 匹配的概念2. 二分圖的定義和判定3. 二分圖的最大匹配4. 二分圖的最小覆蓋問題5. 二分圖的最佳匹配問題1、匹配的概念(1) ,GV GE GME GMMGMM定義1 設圖，而是的一個子集，如果中的任兩條邊均不鄰接，則稱是 的一個匹配。中的一條邊的兩個端點叫做在下是配對的。MvMvvM 若匹配中的某條邊與定點 關聯，則稱飽和頂點 ，并稱 是飽和的。匹配的概念(2)MGGRMMRRM 設是圖 的一個匹配，若 中存在一條基本路徑，路徑的邊是由屬于的匹配邊和不屬于的非匹配邊交替出現組成，則稱 為交替路。若 的兩個端點都是的非飽和點，則稱這條交替路為可增廣路。 ,GV GE GV GXYGM

2、E GXXYMG 設圖，被分成兩個非空的互補頂點子集 和 ，若圖 的一個匹配能飽和 中的每個頂點，換言之， 中的全部頂點和 中的一個子集的頂點之間確定一個一一對應關系，則稱是圖 的一個完備匹配。二分圖的定義 12121212( ,)( ,;)GV EVVVEVVGV V EVVP VVV定義2 設圖，若能把 分成兩個集合 和，使得 中的每條邊的兩個端點，一個在 中，另一個在中，這樣的圖稱為偶圖，也叫二分圖，或是二部圖。偶圖也可表示為。 對于頂點集，用表示中所有和 相連的頂點的集合。1GVG2定義3 如果偶圖 的互補結點子集 中的每一結點都與V中的所有結點鄰接，則稱 為完全偶圖。二分圖的判定0,

3、0GG定理1 當且僅當無向圖 的每一個回路的次數均為偶數時， 才是一個偶圖。如果無回路，相當于任一回路的次數為視為偶數。二分圖的最大匹配 (1)(2) ,(3)(4) , (3),( )(2)GMXMMXMuSu TP STyP STyMyzMSSz TTyR u yMME R 從 中取一個初始匹配。若 中的頂皆為中邊的端點，止，即為完備匹配；否則，取 中不與中邊關聯的頂 ，記。若，止，無完備匹配，否則，取。若 是中邊的端點，設，令，轉；否則，取可增廣路徑，令，轉。Edmonds于1965年提出了解決二分圖的最大匹配的匈牙利算法：例題：小狗散步例題：小狗散步Grant喜歡帶著他的小狗Pando

4、g散步。Grant以一定的速度沿著固定路線走，該路線可能自交。Pandog喜歡游覽沿途的景點，不過會在給定的N個點和主人相遇。小狗和主人同時從點出發，并同時在點匯合。小狗的速度最快是Grant的兩倍。當主人從一個點以直線走向另一個點時，Pandog跑向一個他感興趣的景點。Pandog每次與主人相遇之前最多只去一個景點。已知n個定點的坐標和m個景點的坐標。你的任務是：為Pandog尋找一條路線（有可能與主人的路線部分相同），使它能夠游覽最多的景點，并能夠準時與主人在給定地點相遇或者匯合。 將頂點分成兩類由于“當主人從一個點以直線走向另一個點時，Pandog跑向一個他感興趣的景點”，并且主人的移動

5、路線是確定的，所以尋找一條路線可以看作確定在每一段路線上小狗的選擇：或是跑向哪一個景點，或是和主人的路線重合。因此圖中的點被自然的分成了兩類：1.每一段路線2.景點定義邊 由于在一個線段上，小狗只能跑向一個景點，所以景點是否可達，只和景點到線段兩端點的距離有關，而小狗的速度最快是主人的兩倍。由此得出線段的定義求求二分圖的最大匹配二分圖的最大匹配由于一條線段只能和一個景點發生關聯，而一個景點也只在第一次訪問的時候才有意義，因此任何兩項關聯都不會有任何交點，這顯然滿足了匹配的定義。兩類頂點組成了一個二分圖。使用匈牙利算法求最大匹配數及匹配方案 圖的最小覆蓋問題設D是圖G的一個頂點子集，對于G的任一

6、頂點u，要末u是D集合的一個頂點元素，要末與D中的一個頂點相鄰，那末D稱為圖G的一個覆蓋集。若在D集中去除任何元素D不再是覆蓋集，則覆蓋集D是極小覆蓋集。稱G的所有覆蓋集中頂點個數最少的覆蓋集為最小覆蓋集D0，一般圖的最小覆蓋問題是一個已被證明的NPC問題。換一句話說，一般圖的最小覆蓋問題，是沒有有效算法的圖論模型。所以，將一個實際問題抽象成最小覆蓋問題，是沒有任何意義和價值的。但是，如果問題可以抽象成二分圖的最小覆蓋問題，結局就不一樣了。由于二分圖的特殊性，二分圖的最小覆蓋問題存在多項式算法。二分圖二分圖最大匹配與最小覆蓋的關系最大匹配與最小覆蓋的關系在證明這個定理的過程中，要用到HallH

7、all婚姻定理婚姻定理： 1211GVVGVSVSP S 設 是一個偶圖，頂集劃分成 和， 中存在對于 的完備匹配的充要條件是，對于一切，都有。1931年Knig給出最大匹配與最小覆蓋的關系定理如下： *GMKMK 在偶圖 中，若是最大匹配，是最小覆蓋集，則。例題：國際象棋例題：國際象棋一張大小為n*n的國際象棋棋盤，上面有一些格子被拿走了，棋盤規模n不超過200。馬的攻擊方向如下圖，其中S處為馬位置，標有X的點為該馬的攻擊點。你的任務是確定在這個棋盤上放置盡可能多的馬，并使他們不互相攻擊。求最小覆蓋集的圖論問題求最小覆蓋集的圖論問題將棋盤的每一個格子作為一個頂點，兩點間直接可達（互可攻擊）的

8、關系作為邊。則題目所要求的就是在這樣一張圖中的尋找一個最大獨立子集（即頂點集合中的任意兩頂點都不相鄰、且含頂點數最多）。由于對于任意一張圖，其最大獨立子集和最小覆蓋集互為補集最大獨立子集=n-最小覆蓋集，所以本題也是一個求最小覆蓋集的圖論問題。 棋盤定義在攻擊關系上是一個二分圖 在一張國際象棋的棋盤上，白格和黑格相交錯，一匹馬只能從一個白格跳到一個黑格，或是從一個黑格跳到一個白格。必要條件：一個位置上的馬只能攻擊和其所在位置顏色不同的格子。即同一顏色的任意兩個格子間不存在邊。 棋盤格子按照顏色分成兩個部分。 如果按照自上而下、由左而右的順序給格子編號的話，在所有未被拿走的格子（i,j）中(1i

9、,jn，mapi,j=true)，同種顏色的格子必須滿足如下條件：n為奇數，且(i-1)*n+j為奇數；n為偶數，且i和j的奇偶性不同；我們將所有同種顏色的格子組成X頂點集。顯然X頂點集中每個頂點跳后位置的顏色是不同的，其中未被拿走的跳后位置組成Y頂點集。 通過二分圖最大匹配計算問題解二分圖的最大匹配數與最小覆蓋數之間存在著對應的數量關系，而最大獨立子集和最小覆蓋集互為補集，因此我們可以通過求二分圖的最大匹配數， 互不攻擊情況下馬的最多放置數目=未被拿走的格子數-最多匹配數 二分圖的最佳匹配問題121122124,;,.,.,0nnijGV V EVx xxVy yyw x yMMW MW M

10、MG定義是加權完全偶圖，權。如果有一完備匹配，對所有完備匹配，都有，則稱為偶圖的最佳匹配。由于引入了權，所以最佳匹配不能直接套用最大匹配算法進行求解。同時，由于對最佳匹配的定義是建立在完全加權二分圖的基礎上的，對于不完全圖，可以通過引入權為0（或是其他不影響最終結果的值），使得二分圖稱為完全二分圖，從而使用最佳匹配算法來解決。KM算法前的準備在介紹求最佳匹配的KM算法前，首先介紹一些相關的概念： 125:|,llll V GRxVyVl xl yw xyl vGExy xyE Gl xl yw xyEG 定義映射滿足，成立，則稱是偶圖 的可行頂標；令稱以 為邊集的生成子圖為“相等子圖”，記做。

11、可以證明，Gl的完備匹配即為G的最佳匹配。 以此為基礎，1955年Kuhn，1957年Munkres給出修改頂標的方法，使新的相等子圖的最大匹配逐漸擴大，最后出現相等子圖的完備匹配。 這就是KM算法。KM算法 1,(1)(2) ,(3),(4),min,(4)lllllx S y TlllGMVMMGMuSu TP STP STl va vSal xl yw xyl vl va vTl vll GGP STyyMy 選定初始可行頂標 ，在上選取一個初始匹配。若 中的頂皆為中邊的端點，止，即為最佳匹配；否則，取中不與中邊關聯的頂 ，記。若轉；若，取，其它。選中的一點 ，若 是中邊的端點，且 ,

12、(3),( )(2)lzMSSz TTyGMR u yMME R，則，轉；否則，取中可增廣路徑，令，轉。一個例題某公司有工作人員x1,x2,xn ，他們去做工作y1,y2,yn ，每個人都能做其中的幾項工作，并且對每一項工作都有一個固定的效率。問能否找到一種合適的工作分配方案，使得總的效率最高。要求一個人只能參與一項工作，同時一項工作也必須由一個人獨立完成。不要求所有的人都有工作。一個實例Y1Y2Y3Y4Y5X135541X222022X324410X401100X512133若工人x完全不能參與工作y，則w(x,y)=0流程(1)首先，選取可行頂標l(v)如下： 123410,1,2,3,4

13、,5;max 3,5,5,4,15,max 2,2,0,2,22,max 2,4,4,1,04,max 0,1,1,0,01,max 1,2,1,3,33l yil xl xl xl xl x構造Gl，并求其最大匹配：（其流程過長，此處略）流程(2)其最終得到的最大匹配如圖所示：1x5x4x3x2x1y2y3y4y5y圖中粗點劃線構成最大匹配。 流程(3)Gl中無完備匹配，故修改頂標。 443132,1234512345,min14,2,3,0,3;0,1,1,0,0lx S y Tux Sx x xTyyal xl yw xyxxxxxyyyyy由于，所以修改后的頂標為：流程(4)根據新的頂

14、標構造Gl ，并求其上的一個完全匹配如圖所示： 1x5x4x3x2x1y2y3y4y5y圖中粗點劃線給出了一個最佳匹配，其最大權為4241314。題目完成。 例題例題 Roadseee EfCD請求出修改的最小代價。請求出修改的最小代價。 給定一個無向圖給定一個無向圖G0=（V0，E0，C），），V0為頂點為頂點集合集合,E0為邊集合（無重邊），為邊集合（無重邊），C為邊權（非負整數）為邊權（非負整數）。設。設n= |V0|，m= |E0|，E0中前中前n-1條邊構成一棵生成樹條邊構成一棵生成樹T。請將邊權進行如下修改，即對于。請將邊權進行如下修改，即對于eE，把，把Ce修改修改成成De（De

15、也為非負整數），使得樹也為非負整數），使得樹T成為圖成為圖G的一棵最的一棵最小生成樹。修改的代價定義為：小生成樹。修改的代價定義為：415234622357415234424334f=|6-4|+|2-2|+|5-3|+|7-4|+|3-3|+|2-4|+|4-4|=9初步分析初步分析l根據與樹根據與樹T T的關系的關系, ,我們可以把圖我們可以把圖G0 0中的邊分成中的邊分成樹邊與非樹邊兩類。樹邊與非樹邊兩類。l設設Pe表示邊表示邊e的兩個端點之間的樹的路徑中邊的兩個端點之間的樹的路徑中邊的集合。的集合。初步分析初步分析 如右圖，如右圖，uT，t1，t2，t3T，且，且t1，t2，t3連接了

16、連接了u的兩個端點，所以的兩個端點，所以Pu=t1，t2，t3。/l 那么用非樹邊那么用非樹邊u代替樹邊代替樹邊t1，t2，t3中任意一條都可以得到一中任意一條都可以得到一棵新的生成樹。棵新的生成樹。l 而如果而如果u的邊權比所替換的的邊權比所替換的邊的邊權更小的話，則可以得邊的邊權更小的話，則可以得到一棵權值更小的生成樹。到一棵權值更小的生成樹。l 那么要使原生成樹那么要使原生成樹T是一棵是一棵最小生成樹，必須滿足條件：最小生成樹，必須滿足條件：Dt1 Du ； Dt2 Du ； Dt3 Duut1t2t3初步分析初步分析 如果邊如果邊v，u(u可替換可替換v)，則必須滿足則必須滿足 Dv

17、Du ，否則用否則用u替換替換v可得到一棵權值更可得到一棵權值更小的生成樹小的生成樹T-v+u 。/ 對邊對邊v，u如果滿足條件如果滿足條件uT ，vPu， 則稱則稱u可替換可替換v。初步分析初步分析 不等式不等式DvDu中中v總為樹邊總為樹邊，而而u總為總為非樹邊。非樹邊。 那么顯然樹邊的邊權應該減小那么顯然樹邊的邊權應該減小(或不變或不變)，而非樹邊的邊權則應該增大而非樹邊的邊權則應該增大(或不變或不變)。 設邊權的修改量為設邊權的修改量為，即，即 e=|DeCe|/當當eT， e=DeCe, , 即即De=Cee當當eT， e=CeDe，即，即De=Cee初步分析初步分析 那問題就是求出

18、所有的那問題就是求出所有的使其滿足以上不等式且：使其滿足以上不等式且：vuDDvvuuCC vuvuCC 1miif最小。最小。 那么當那么當u可替換可替換v時，由不等式時，由不等式觀察此不等式觀察此不等式其中不等號右側其中不等號右側CvCu是一個已知量！是一個已知量！vuvuCC 大家或許會發現這個不等式似曾相識大家或許會發現這個不等式似曾相識! 這就是在求二分圖最佳匹配的經典這就是在求二分圖最佳匹配的經典KM算法中算法中不可或缺的一個不等式。不可或缺的一個不等式。 KM算法中，首先給二分圖的每個頂點都設一個算法中，首先給二分圖的每個頂點都設一個可行頂標，可行頂標，X結點結點i為為li，Y結

19、點結點j為為rj。從始至終，邊權。從始至終，邊權為為Wv,u的邊的邊(v,u)都需要滿足都需要滿足lv + ru Wv,u 。1234567建立兩個互補的結點集合建立兩個互補的結點集合X，Y。/Y結點結點j表示圖表示圖G0中中非樹邊非樹邊aj(ajT)。X結點結點i表示圖表示圖G0中中樹邊樹邊ai(aiT)。XY設這些結點均為實點。設這些結點均為實點。1234567XY 如果圖如果圖G0中，中，aj 可替換可替換ai，且，且CiCj0,則在則在X結點結點i和和Y結點結點j之間添加邊之間添加邊(i,j), 邊權邊權Wi,j=CiCj。1234567XY1234567XY 設這些邊均為實邊。設這些

20、邊均為實邊。1234567 在結點數少的一側添加虛結點，使得在結點數少的一側添加虛結點，使得X結點和結點和Y結結點的數目相等。點的數目相等。XY8 如果如果X結點結點i和和Y結點結點j之間沒有邊，則添加一條權之間沒有邊，則添加一條權值為值為0的虛邊的虛邊(i,j)。12345678XY算法分析算法分析,( , )iji jlrWi jX,( , )iji jlrWi jM,( , )Mi jiji jMi Xj YSWlr設完備匹配設完備匹配X的所有匹配邊的權值和為的所有匹配邊的權值和為SX，則則 對于圖對于圖G的任意一個完備匹配的任意一個完備匹配X，都有，都有 設設M為圖為圖G的最大權匹配，顯然的最大權匹配，顯然M也是完備匹配，也是完備匹配，則滿足則滿足 顯然，此時的可行頂標之和取到最小值。顯然，此時的可行頂標之和取到最小值。 因為虛結點因為虛結點Xi的匹配邊肯定是權值為的匹配邊肯定是權值為0的虛邊，的虛邊，所以所以li=0