偶圖的算法及應(yīng)用

《偶圖的算法及應(yīng)用》由會(huì)員分享，可在線閱讀，更多相關(guān)《偶圖的算法及應(yīng)用（20頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、南京師范大學(xué)附屬中學(xué) 孫方成目錄匹配的概念偶圖的定義和判定偶圖的最大匹配偶圖的最小覆蓋問題偶圖的最佳匹配問題小結(jié)匹配的概念(1) ,GV GE GME GMMGMM定義1 設(shè)圖，而是的一個(gè)子集，如果中的任兩條邊均不鄰接，則稱是 的一個(gè)匹配。中的一條邊的兩個(gè)端點(diǎn)叫做在下是配對(duì)的。MvMvvM 若匹配中的某條邊與定點(diǎn) 關(guān)聯(lián)，則稱飽和頂點(diǎn) ，并稱 是飽和的。匹配的概念(2)MGGRMMRRM 設(shè)是圖 的一個(gè)匹配，若 中存在一條基本路徑，路徑的邊是由屬于的匹配邊和不屬于的非匹配邊交替出現(xiàn)組成，則稱 為交替路。若 的兩個(gè)端點(diǎn)都是的非飽和點(diǎn)，則稱這條交替路為可增廣路。 ,GV GE GV GXYGME G

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

3、1 當(dāng)且僅當(dāng)無向圖 的每一個(gè)回路的次數(shù)均為偶數(shù)時(shí)， 才是一個(gè)偶圖。如果無回路，相當(dāng)于任一回路的次數(shù)為視為偶數(shù)。偶圖的最大匹配 (1)(2) ,(3)(4) , (3),( )(2)GMXMMXMuSu TP STyP STyMyzMSSz TTyR u yMME R 從 中取一個(gè)初始匹配。若 中的頂皆為中邊的端點(diǎn)，止，即為完備匹配；否則，取 中不與中邊關(guān)聯(lián)的頂 ，記。若，止，無完備匹配，否則，取。若 是中邊的端點(diǎn)，設(shè)，令，轉(zhuǎn)；否則，取可增廣路徑，令，轉(zhuǎn)。Edmonds于1965年提出了解決偶圖的最大匹配的匈牙利算法：偶圖的最小覆蓋問題一般圖的最小覆蓋問題是一個(gè)已被證明的NPC問題。換一句話說，

4、一般圖的最小覆蓋問題，是沒有有效算法的圖論模型。所以，將一個(gè)實(shí)際問題抽象成最小覆蓋問題，是沒有任何意義和價(jià)值的。但是，如果問題可以抽象成偶圖的最小覆蓋問題，結(jié)局就不一樣了。由于偶圖的特殊性，偶圖的最小覆蓋問題存在多項(xiàng)式算法。最大匹配與最小覆蓋的關(guān)系在證明這個(gè)定理的過程中，要用到Hall婚姻定理婚姻定理： 1211GVVGVSVSP S 設(shè) 是一個(gè)偶圖，頂集劃分成 和， 中存在對(duì)于 的完備匹配的充要條件是，對(duì)于一切，都有。1931年Knig給出最大匹配與最小覆蓋的關(guān)系定理如下： *GMKMK 在偶圖 中，若是最大匹配，是最小覆蓋集，則。偶圖的最佳匹配問題121122124,;,.,.,0nnij

5、GV V EVx xxVy yyw x yMMW MW MMG定義是加權(quán)完全偶圖，權(quán)。如果有一完備匹配，對(duì)所有完備匹配，都有，則稱為偶圖的最佳匹配。由于引入了權(quán)，所以最佳匹配不能直接套用最大匹配算法進(jìn)行求解。同時(shí)，由于對(duì)最佳匹配的定義是建立在完全加權(quán)偶圖的基礎(chǔ)上的，對(duì)于不完全圖，可以通過引入權(quán)為0（或是其他不影響最終結(jié)果的值），使得偶圖稱為完全偶圖，從而使用最佳匹配算法來解決。KM算法前的準(zhǔn)備在介紹求最佳匹配的KM算法前，首先介紹一些相關(guān)的概念： 125:|,llll V GRxVyVl xl yw xyl vGExy xyE Gl xl yw xyEG 定義映射滿足，成立，則稱是偶圖 的可行

6、頂標(biāo)；令稱以 為邊集的生成子圖為“相等子圖”，記做?？梢宰C明，Gl的完備匹配即為G的最佳匹配。 以此為基礎(chǔ)，1955年Kuhn，1957年Munkres給出修改頂標(biāo)的方法，使新的相等子圖的最大匹配逐漸擴(kuò)大，最后出現(xiàn)相等子圖的完備匹配。 這就是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 選定初始可行頂標(biāo) ，在上選取一個(gè)初始匹配。若 中的頂皆為中邊的端點(diǎn)，止，即為最佳匹配；否則，取中不與中邊關(guān)聯(lián)的頂 ，記。若轉(zhuǎn)；若

7、，取，其它。選中的一點(diǎn) ，若 是中邊的端點(diǎn)，且 , (3),( )(2)lzMSSz TTyGMR u yMME R，則，轉(zhuǎn)；否則，取中可增廣路徑，令，轉(zhuǎn)。一個(gè)例題某公司有工作人員x1,x2,xn ，他們?nèi)プ龉ぷ鱵1,y2,yn ，每個(gè)人都能做其中的幾項(xiàng)工作，并且對(duì)每一項(xiàng)工作都有一個(gè)固定的效率。問能否找到一種合適的工作分配方案，使得總的效率最高。要求一個(gè)人只能參與一項(xiàng)工作，同時(shí)一項(xiàng)工作也必須由一個(gè)人獨(dú)立完成。不要求所有的人都有工作。一個(gè)實(shí)例Y1Y2Y3Y4Y5X135541X222022X324410X401100X512133若工人x完全不能參與工作y，則w(x,y)=0流程(1)首先，選取

8、可行頂標(biāo)l(v)如下： 123410,1,2,3,4,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構(gòu)造Gl，并求其最大匹配：（其流程過長(zhǎng)，此處略）流程(2)其最終得到的最大匹配如圖所示：1x5x4x3x2x1y2y3y4y5y圖中粗點(diǎn)劃線構(gòu)成最大匹配。 流程(3)Gl中無完備匹配，故修改頂標(biāo)。 443132,1234512345,min14,2,3,0,3;0,1,1,0,0lx S y Tux Sx x xTyyal xl yw xyxxxxxyy

9、yyy由于，所以修改后的頂標(biāo)為：流程(4)根據(jù)新的頂標(biāo)構(gòu)造Gl ，并求其上的一個(gè)完全匹配如圖所示： 1x5x4x3x2x1y2y3y4y5y圖中粗點(diǎn)劃線給出了一個(gè)最佳匹配，其最大權(quán)為4241314。題目完成。 小結(jié)偶圖是一種特殊的圖，所以它不但具備了信息量豐富這個(gè)圖模型共有的優(yōu)點(diǎn)，同時(shí)它也具備了大量一般圖所不具備的內(nèi)涵和算法優(yōu)勢(shì)。偶圖的結(jié)點(diǎn)分成兩個(gè)部分，這就是它和自然界、數(shù)學(xué)界的對(duì)應(yīng)關(guān)系，或者說匹配關(guān)系有著深刻的聯(lián)系。因此，匹配的算法是所有偶圖算法的核心。如果能將實(shí)際問題，通過合理的抽象，變成兩種事物之間的矛盾，則這種問題就可以抽象成偶圖的模型。所以，偶圖的模型有著廣泛的應(yīng)用。同時(shí)，偶圖的算法有著高效實(shí)用的特點(diǎn)，所以也使通過偶圖模型解決問題成為可能。綜上所述，我認(rèn)為，偶圖是一種高效的，有著廣泛使用價(jià)值的模型。合理、有效的使用偶圖模型，將大大提高編程及解決現(xiàn)實(shí)生活中實(shí)際問題的能力。 謝謝！謝謝！