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

1、A,1,偶圖的算法及應(yīng)用,南京師范大學附屬中學 孫方成,A,2,目錄,匹配的概念 偶圖的定義和判定 偶圖的最大匹配 偶圖的最小覆蓋問題 偶圖的最佳匹配問題 小結(jié),A,3,匹配的概念(1),A,4,匹配的概念(2),A,5,偶圖的定義,A,6,偶圖的判定,A,7,偶圖的最大匹配,Edmonds于1965年提出了解決偶圖的最大匹配的匈牙利算法：,A,8,偶圖的最小覆蓋問題,一般圖的最小覆蓋問題是一個已被證明的NPC問題。換一句話說，一般圖的最小覆蓋問題，是沒有有效算法的圖論模型。所以，將一個實際問題抽象成最小覆蓋問題，是沒有任何意義和價值的。 但是，如果問題可以抽象成偶圖的最小覆蓋問題，結(jié)局就不一

2、樣了。由于偶圖的特殊性，偶圖的最小覆蓋問題存在多項式算法。,A,9,最大匹配與最小覆蓋的關(guān)系,在證明這個定理的過程中，要用到Hall婚姻定理：,1931年Knig給出最大匹配與最小覆蓋的關(guān)系定理如下：,A,10,偶圖的最佳匹配問題,由于引入了權(quán)，所以最佳匹配不能直接套用最大匹配算法進行求解。同時，由于對最佳匹配的定義是建立在完全加權(quán)偶圖的基礎(chǔ)上的，對于不完全圖，可以通過引入權(quán)為0（或是其他不影響最終結(jié)果的值），使得偶圖稱為完全偶圖，從而使用最佳匹配算法來解決。,A,11,KM算法前的準備,在介紹求最佳匹配的KM算法前，首先介紹一些相關(guān)的概念：,可以證明，Gl的完備匹配即為G的最佳匹配。,以此為

3、基礎(chǔ)，1955年Kuhn，1957年Munkres給出修改頂標的方法，使新的相等子圖的最大匹配逐漸擴大，最后出現(xiàn)相等子圖的完備匹配。 這就是KM算法。,A,12,KM算法,A,13,一個例題,某公司有工作人員x1,x2,xn ，他們?nèi)プ龉ぷ鱵1,y2,yn ，每個人都能做其中的幾項工作，并且對每一項工作都有一個固定的效率。問能否找到一種合適的工作分配方案，使得總的效率最高。要求一個人只能參與一項工作，同時一項工作也必須由一個人獨立完成。不要求所有的人都有工作。,A,14,一個實例,若工人x完全不能參與工作y，則w(x,y)=0,A,15,流程(1),首先，選取可行頂標l(v)如下：,構(gòu)造Gl，

4、并求其最大匹配：（其流程過長，此處略）,A,16,流程(2),其最終得到的最大匹配如圖所示：,圖中粗點劃線構(gòu)成最大匹配。,A,17,流程(3),Gl中無完備匹配，故修改頂標。,A,18,流程(4),根據(jù)新的頂標構(gòu)造Gl ，并求其上的一個完全匹配如圖所示：,圖中粗點劃線給出了一個最佳匹配，其最大權(quán)為4241314。題目完成。,A,19,小結(jié),偶圖是一種特殊的圖，所以它不但具備了信息量豐富這個圖模型共有的優(yōu)點，同時它也具備了大量一般圖所不具備的內(nèi)涵和算法優(yōu)勢。 偶圖的結(jié)點分成兩個部分，這就是它和自然界、數(shù)學界的對應(yīng)關(guān)系，或者說匹配關(guān)系有著深刻的聯(lián)系。因此，匹配的算法是所有偶圖算法的核心。 如果能將實際問題，通過合理的抽象，變成兩種事物之間的矛盾，則這種問題就可以抽象成偶圖的模型。所以，偶圖的模型有著廣泛的應(yīng)用。同時，偶圖的算法有著高效實用的特點，所以也使通過偶圖模型解決問題成為可能。 綜上所述，我認為