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

1、偶圖的算法及應(yīng)用1目錄匹配的概念偶圖的定義和判定偶圖的最大匹配偶圖的最小覆蓋問(wèn)題偶圖的最佳匹配問(wèn)題小結(jié)2匹配的概念(1)3匹配的概念(2)4偶圖的定義5偶圖的判定6偶圖的最大匹配Edmonds于1965年提出了解決偶圖的最大匹配的匈牙利算法：7偶圖的最小覆蓋問(wèn)題一般圖的最小覆蓋問(wèn)題是一個(gè)已被證明的NPC問(wèn)題。換一句話說(shuō)，一般圖的最小覆蓋問(wèn)題，是沒(méi)有有效算法的圖論模型。所以，將一個(gè)實(shí)際問(wèn)題抽象成最小覆蓋問(wèn)題，是沒(méi)有任何意義和價(jià)值的。但是，如果問(wèn)題可以抽象成偶圖的最小覆蓋問(wèn)題，結(jié)局就不一樣了。由于偶圖的特殊性，偶圖的最小覆蓋問(wèn)題存在多項(xiàng)式算法。8最大匹配與最小覆蓋的關(guān)系在證明這個(gè)定理的過(guò)程中，要用

2、到Hall婚姻定理：1931年Knig給出最大匹配與最小覆蓋的關(guān)系定理如下： 9偶圖的最佳匹配問(wèn)題由于引入了權(quán)，所以最佳匹配不能直接套用最大匹配算法進(jìn)行求解。同時(shí)，由于對(duì)最佳匹配的定義是建立在完全加權(quán)偶圖的基礎(chǔ)上的，對(duì)于不完全圖，可以通過(guò)引入權(quán)為0（或是其他不影響最終結(jié)果的值），使得偶圖稱為完全偶圖，從而使用最佳匹配算法來(lái)解決。10KM算法前的準(zhǔn)備在介紹求最佳匹配的KM算法前，首先介紹一些相關(guān)的概念：可以證明，Gl的完備匹配即為G的最佳匹配。 以此為基礎(chǔ)，1955年Kuhn，1957年Munkres給出修改頂標(biāo)的方法，使新的相等子圖的最大匹配逐漸擴(kuò)大，最后出現(xiàn)相等子圖的完備匹配。 這就是KM算

3、法。11KM算法12一個(gè)例題某公司有工作人員x1,x2,xn ，他們?nèi)プ龉ぷ鱵1,y2,yn ，每個(gè)人都能做其中的幾項(xiàng)工作，并且對(duì)每一項(xiàng)工作都有一個(gè)固定的效率。問(wèn)能否找到一種合適的工作分配方案，使得總的效率最高。要求一個(gè)人只能參與一項(xiàng)工作，同時(shí)一項(xiàng)工作也必須由一個(gè)人獨(dú)立完成。不要求所有的人都有工作。13一個(gè)實(shí)例若工人x完全不能參與工作y，則w(x,y)=014流程(1)首先，選取可行頂標(biāo)l(v)如下：構(gòu)造Gl，并求其最大匹配：（其流程過(guò)長(zhǎng)，此處略）15流程(2)其最終得到的最大匹配如圖所示：圖中粗點(diǎn)劃線構(gòu)成最大匹配。 16流程(3)Gl中無(wú)完備匹配，故修改頂標(biāo)。 17流程(4)根據(jù)新的頂標(biāo)構(gòu)造Gl ，并求其上的一個(gè)完全匹配如圖所示： 圖中粗點(diǎn)劃線給出了一個(gè)最佳匹配，其最大權(quán)為4241314。題目完成。 18小結(jié)偶圖是一種特殊的圖，所以它不但具備了信息量豐富這個(gè)圖模型共有的優(yōu)點(diǎn)，同時(shí)它也具備了大量一般圖所不具備的內(nèi)涵和算法優(yōu)勢(shì)。偶圖的結(jié)點(diǎn)分成兩個(gè)部分，這就是它和自然界、數(shù)學(xué)界的對(duì)應(yīng)關(guān)系，或者說(shuō)匹配關(guān)系有著深刻的聯(lián)系。因此，匹配的算法是所有偶圖算法的核心。如果能將實(shí)際問(wèn)題，通過(guò)合理的抽象，變成兩種事物之間的矛盾，則這種問(wèn)題就可以抽象成偶圖的模型。所以，偶圖的模型有著廣泛的應(yīng)用。同時(shí)，偶圖的算法有著高效實(shí)用的特點(diǎn)，所以也使通過(guò)偶圖模型解決問(wèn)題成為可能。綜上所述，我認(rèn)為，偶圖是