計(jì)算圖中的最大對集的匈牙利方法

1、計(jì)算圖中的最大對集的匈牙利方法背景知識介紹在一個(gè)網(wǎng)絡(luò)中往往要求計(jì)算其中的最大對集。是由匈牙利人Egervary于1931年發(fā)現(xiàn)，后被另外一個(gè)匈牙利人Edmonds所推廣（到一般圖中的“開花算法”）基本方法利用反圈法第一節(jié) 二部圖中最大對集的有效算法設(shè)為一個(gè)二部圖，是中一個(gè)對集。型節(jié)點(diǎn)-位于的節(jié)點(diǎn)；型節(jié)點(diǎn)-位于中的節(jié)點(diǎn)；-邊-位于中的邊；注意：一個(gè)增廣路的長度為奇數(shù)，所以這樣的路的兩個(gè)端點(diǎn)必須是同型節(jié)點(diǎn)。反圈法基本原則-（1）初始時(shí)，令；（2）在中選邊時(shí)，必須按照以下原則：(a)如果時(shí)，則選取以為端點(diǎn)的非邊（即，在型節(jié)點(diǎn)處只選非邊）；(b)如果 ，則選取以為端點(diǎn)的邊（即，在型節(jié)點(diǎn)處只選邊）（3）

2、若在某一步，出現(xiàn)下述情況之一時(shí)算法要終止：情況1。中有非飽和的型節(jié)點(diǎn)（此時(shí)得到一條關(guān)于的增廣路）；情況2.。情況1不出現(xiàn)，且中無邊可選（此時(shí)中不存在關(guān)于的增廣路）。定理1.當(dāng)匈牙利算法結(jié)束時(shí)，得到一個(gè)最大對集解答：下面我們來證明這個(gè)方法（算法）的正確性。如果情況1發(fā)生，根據(jù)我們算法特點(diǎn)，每一步上都是森林，其中每一個(gè)樹都是以中的一點(diǎn)為根的。根據(jù)的定義，每一個(gè)樹以一個(gè)非飽和的型節(jié)點(diǎn)為根。按照選邊原則（2）可以看出：每一個(gè)樹上，根與任意節(jié)點(diǎn)之間的唯一的路是交錯(cuò)路、。所以，當(dāng)某個(gè)非飽和的型節(jié)點(diǎn)屬于時(shí)，這個(gè)樹上聯(lián)接根節(jié)點(diǎn)與它的路是一個(gè)長度為奇數(shù)的增廣路?，F(xiàn)在假定情況2出現(xiàn)。我們用表示此時(shí)的（一定要記?。?/p>

3、中的每一個(gè)節(jié)點(diǎn)都位于一個(gè)樹中）。令記其幾何意義如圖所示：（注意：這是其中一種結(jié)構(gòu)，也是最重要的結(jié)構(gòu)，即，假定對集中所有邊都被包含在以為根的樹中）。結(jié)論1.所有非飽和的型節(jié)點(diǎn)都在中（這是根據(jù)的定義得到的。表明：每一個(gè)這樣的非飽和型節(jié)點(diǎn)都是一個(gè)樹的根，這個(gè)樹有可能退化為一個(gè)節(jié)點(diǎn)！）；結(jié)論2。所有的非飽和的型節(jié)點(diǎn)都在中（否則，選邊原則（1）可得到增廣路）；結(jié)論3.（前提是：連通）事實(shí)上，如果有使得，則因?yàn)椋廊绻麆t是可選邊（事實(shí)上此時(shí)有增廣路聯(lián)接與中點(diǎn)），與情況2的定義相違背；如果，則，必然有使得，與是對集相違背。結(jié)論4. （這個(gè)顯然成立）注意：上述圖形仍有地方要知道：中含有未被飽和的非根節(jié)點(diǎn)（因

4、此，）注意：上述的有些東西可能描述的不太精確。我們下面詳細(xì)說明。記住當(dāng)前算法執(zhí)行到情況2，無法選邊而且情況1不發(fā)生?？蛇x邊時(shí)有兩種選法：沿著對集中的邊向下走，沿著非中邊向上走。（1）：將對集分成兩類：和，其中是以中的節(jié)點(diǎn)為根的樹中所能包含的邊形成的子對集，而則是無法被這些樹所含有的子對集（可以為空集）；（2）對集所能飽和的的節(jié)點(diǎn)集合為，沒有被飽和的節(jié)點(diǎn)集合為（3）；（4）（這是由于無法選邊決定的，否則，有些子樹可以長大）；（5）（理由同上）。這樣，結(jié)論1.所有非飽和的型節(jié)點(diǎn)都在中（這是根據(jù)的定義得到的。表明：每一個(gè)這樣的非飽和型節(jié)點(diǎn)都是一個(gè)樹的根，這個(gè)樹有可能退化為一個(gè)節(jié)點(diǎn)?。?；結(jié)論2。所有的

5、非飽和的型節(jié)點(diǎn)都在中（否則，選邊原則（1）可得到增廣路）；結(jié)論3. ；結(jié)論4.結(jié)論5.。（這是由圖的連通性決定的）結(jié)論6. ；這樣一來，若中存在增廣路，那么它的一個(gè)端點(diǎn)在中，另外一個(gè)端點(diǎn)在中。顯然此時(shí)可以選邊使得對集增大。矛盾。因此，當(dāng)情況2發(fā)生時(shí)當(dāng)前的對集是最大的。注意：從上述分析中可知，我們的討論可以假定。分析中得到的結(jié)構(gòu)（結(jié)論1-6）非常有用，我們可以直接利用它們來計(jì)算。定理2.任何一個(gè)使得的二部圖中一定有一個(gè)最大對集飽和所有最大次節(jié)點(diǎn)。點(diǎn)評：如果這個(gè)結(jié)果成立，那么這個(gè)圖一定是第一類的（即，邊色數(shù)。）解答：設(shè)是這樣一個(gè)最大對集，它所飽和的最大次節(jié)點(diǎn)最多。我們將要證明：為所求。若不然，則存

6、在一個(gè)最大次節(jié)點(diǎn)，沒有被所飽和。不妨設(shè)可以取使得是唯一一個(gè)未被飽和的最大次節(jié)點(diǎn)。對于這個(gè)執(zhí)行匈牙利算法?？芍闆r2一定出現(xiàn)（即，無邊可選的結(jié)構(gòu)一定出現(xiàn)）。注意到上述結(jié)論1-結(jié)論6暗示：。此時(shí)一定有一個(gè)節(jié)點(diǎn)不是最大次的。不然，則有，這與相悖（這里利用了性質(zhì)：中非根節(jié)點(diǎn)的領(lǐng)域全部被包含在）。設(shè)不是最大次節(jié)點(diǎn)，記為執(zhí)行匈牙利算法終止時(shí)得到的交錯(cuò)樹里面唯一的-路。意見它的長度為偶數(shù)。令，則也是最大對集，它飽和最大節(jié)點(diǎn)數(shù)目比多（事實(shí)上，飽和了，但是沒有飽和。這正是我們需要的；同時(shí)，前面中其他節(jié)點(diǎn)還是被所飽和）。這與定義相違背。點(diǎn)評：關(guān)于這個(gè)結(jié)果有許多證明。我們將要提供另外一個(gè)富有技巧性的證明（但是說真的

7、，我不喜歡這種過于簡短的證明，因?yàn)樗鼈兺谏w了很多的事物真相!）。例3. 如果二部圖G中節(jié)點(diǎn)次數(shù)的最大值是，那么可以將它的邊進(jìn)行著色，每一條邊染這中顏色中的一種，使得同一個(gè)節(jié)點(diǎn)引出的邊顏色不同。解：如果G是正則圖，則由Hall定理知道結(jié)論成立。否則，G不是正則圖。我們可以將G擴(kuò)展成為一個(gè)正則二部圖（即，是的子圖）如下：增加一些節(jié)點(diǎn)使得G的兩部分的節(jié)點(diǎn)數(shù)目相同，然后在兩部分之間盡可能地連邊，直到。再連一條邊則最大次數(shù)就超過為止。這樣得到的圖一定是正則圖。理由如下：因?yàn)槿粲械拇螖?shù)小于，則總邊數(shù)，從而必有的次數(shù)小于。于是可以連邊而不破壞的最大性。根據(jù)上面所講，可以對的邊進(jìn)行著色，使得每一種顏色的邊

8、恰好是一個(gè)完美對集。在此結(jié)構(gòu)下，的邊也相應(yīng)地被染上了種顏色，使得每一種顏色的邊形成一個(gè)對集。點(diǎn)評；這個(gè)例子表明：如果一個(gè)二部圖的最大次為，則其中一定有對集飽和所有最大次節(jié)點(diǎn)。這個(gè)對集可以是最大的。推論4.每一個(gè)正則二部圖一定有1-因子。下面要用匈牙利算法終止時(shí)得到的結(jié)構(gòu)來證明著名的Konig定理和Hall定理。定理5(Konig,1931) 對于任何二部圖，最小節(jié)點(diǎn)覆蓋階數(shù)=最大對集階數(shù)。證明：設(shè)是一個(gè)最大對集，是最小覆蓋集合的階數(shù)。容易看出：根據(jù)我們在對當(dāng)前的執(zhí)行匈牙利算法時(shí)，一開始就無邊可選。于是，就有前面圖形所示結(jié)構(gòu)，那里有以下事實(shí)：這里，?？梢钥闯觯菏且粋€(gè)覆蓋，從而必有。證明完畢。注意

9、到，對于任何的子集，形成一個(gè)覆蓋。推論6.對于任何二部圖，最小節(jié)點(diǎn)覆蓋階數(shù)=最大對集階數(shù)=如果中有對集飽和中所有節(jié)點(diǎn)，那么自然有（Hall條件）成立。反過來，假定上述條件成立，一定有最大對集飽和中所有節(jié)點(diǎn)。推論7（Hall定理1935）對于任何二部圖，存在對集飽和中所有節(jié)點(diǎn)的充分必要條件是：注意：組合學(xué)中有幾個(gè)著名的“max=min”-型定理：Menger定理，Hall定理，Konig定理以及Dilworth定理。它們在本質(zhì)上都是等價(jià)的，以后我們還要介紹它們之間的相互推導(dǎo)。第二節(jié) 一般圖中的最大對集值Edmonds開花算法?；鞠敕?將二部圖中的匈牙利算法推廣到一般圖。首先我們來回顧一下我們在

10、二部圖中始怎么做的。給定一個(gè)二部圖和一個(gè)對集，算法開始時(shí)，令是所有非飽和的型節(jié)點(diǎn)集合。一般地，設(shè)已經(jīng)有。我們在中開始選邊，選邊的原則是：在型節(jié)點(diǎn)處選非邊，在型節(jié)點(diǎn)處選邊；把被選到的邊放入到中去，得到。放入節(jié)點(diǎn)時(shí)會有兩個(gè)情況發(fā)生：若有某個(gè)非飽和的型節(jié)點(diǎn)在中，則得到增廣路；否則繼續(xù)選邊過程。若在某一步，沒有邊可以選擇，則說明沒有增廣路，當(dāng)前的便是最大對集。在前一節(jié)的匈牙利算法執(zhí)行過程中，所有被選邊生成的子圖是由個(gè)交錯(cuò)樹組成的森林。每一個(gè)交錯(cuò)樹恰好有一個(gè)非飽和節(jié)點(diǎn)（是型節(jié)點(diǎn)）。形象地講，匈牙利算法的執(zhí)行過程就是以中每一個(gè)節(jié)點(diǎn)為根的交錯(cuò)樹的生長過程。擴(kuò)大交錯(cuò)樹的方式有兩種：一是選入一條邊（圖（a）；一

11、是選入一條非邊，而這條邊在中始飽和的（圖（b）。在這兩種情況下，我們稱此時(shí)的交錯(cuò)樹為可擴(kuò)的。若被選入的非邊在中始非飽和節(jié)點(diǎn)（圖（c），這個(gè)交錯(cuò)樹中有一個(gè)增廣路，這個(gè)樹稱為增廣樹。若增廣樹即不是可擴(kuò)的，也不是增光的，我們就稱其為匈牙利樹（圖(d)）。每一個(gè)匈牙利樹種必有奇數(shù)個(gè)節(jié)點(diǎn)，其中僅有根節(jié)點(diǎn)為非飽和節(jié)點(diǎn)下面我們來把上述算法改造一下，以便可以適用于一般圖。開始時(shí)，令為所有未飽和節(jié)點(diǎn)并且記它們?yōu)樾凸?jié)點(diǎn)。選邊原則不變。當(dāng)選一條非邊時(shí)，把它在中的端點(diǎn)記為型節(jié)點(diǎn)；當(dāng)選一條邊時(shí)，把它在中端點(diǎn)記為型節(jié)點(diǎn)。整個(gè)過程仍然是擴(kuò)大交錯(cuò)樹，或者得到增廣樹，或者得到匈牙利樹。不過要注意的是：這是的增廣樹除了上述所講的

12、一種形式以外（圖(c)），還有一種可能：它可能由兩個(gè)交錯(cuò)樹“合并”而成的，即，當(dāng)兩個(gè)交錯(cuò)樹的兩個(gè)型節(jié)點(diǎn)之間有非邊相連，或者兩個(gè)型節(jié)點(diǎn)之間有邊相連時(shí)，也會產(chǎn)生增廣樹（下圖(a),(b)）.此時(shí)必須隨時(shí)檢驗(yàn)這種情況是否會出現(xiàn)。為了避免這種檢驗(yàn)，我們可以任取一個(gè)非飽和節(jié)點(diǎn)作為。當(dāng)以它為根的交錯(cuò)樹成為了匈牙利樹后，再任取另外一個(gè)非飽和節(jié)點(diǎn)放入（令它為型節(jié)點(diǎn)）。繼續(xù)做下去，就是說，在執(zhí)行過程中，總是某一個(gè)交錯(cuò)樹，只是在這個(gè)樹不可擴(kuò)大時(shí)，即成為匈牙利樹以后，才去擴(kuò)大另外一個(gè)交錯(cuò)樹。這個(gè)原則對于下面要介紹的一般圖的情況也是一樣適用。我們知道，非二部圖中會有奇圈。Edmonds在1965年對匈牙利算法做了一個(gè)

13、十分重要的寫該，從而克服了從二部圖到一般圖時(shí)出現(xiàn)的困難。首先介紹所謂“花”的概念。給定圖是它的一個(gè)對集。若是其中一個(gè)奇圈，使得上恰好有條邊。因此有唯一一個(gè)節(jié)點(diǎn)，它在中的兩條關(guān)聯(lián)邊均不是邊。設(shè)是一條交錯(cuò)路，其中是關(guān)于的非飽和節(jié)點(diǎn)，是長度為偶數(shù)的路，。我們稱由路與奇圈所成的子圖是一個(gè)花型結(jié)構(gòu)（注意：可以是1，這時(shí)，不是飽和節(jié)點(diǎn)）。由生成的子圖，成為花苞，為花托，是花柄，是花根。結(jié)論1。設(shè)是一個(gè)花型結(jié)構(gòu)。顯然，從的根到花苞上任何一點(diǎn)有一條長度為偶數(shù)的交錯(cuò)路。Edmonds 的做法是：在執(zhí)行匈牙利算法擴(kuò)大交錯(cuò)路的過程中，一旦發(fā)現(xiàn)花型結(jié)構(gòu)，則在圖中收縮花苞，得到一個(gè)偽節(jié)點(diǎn)。令這個(gè)偽節(jié)點(diǎn)為-型節(jié)點(diǎn)，然后繼

14、續(xù)擴(kuò)大交錯(cuò)樹。結(jié)論2.若收縮圖中有關(guān)于的可擴(kuò)交錯(cuò)路，那么原圖中也有關(guān)于的可擴(kuò)交錯(cuò)路。結(jié)論3.如果在收縮圖中沒有可擴(kuò)交錯(cuò)路，那么就是最大對集。注意：（1）在交錯(cuò)樹中，花型結(jié)構(gòu)的出現(xiàn)有兩種可能：一是同一個(gè)交錯(cuò)樹中，兩個(gè)型節(jié)點(diǎn)之間有非邊相連；一是同一個(gè)交錯(cuò)樹中，兩個(gè)型節(jié)點(diǎn)之間有邊相連。所謂花型結(jié)構(gòu)出現(xiàn)，就是針對于某一個(gè)匈牙利樹，有奇長的基本圈出現(xiàn)。（2）在執(zhí)行過程中，可能由某個(gè)偽節(jié)點(diǎn)又出現(xiàn)在另外一個(gè)花型結(jié)構(gòu)的花苞中。因而，一般地講，說到偽節(jié)點(diǎn)，也包括這種包含偽節(jié)點(diǎn)的偽節(jié)點(diǎn)。結(jié)論4.每一個(gè)偽節(jié)點(diǎn)對應(yīng)于圖的一個(gè)奇數(shù)階生成子圖。下面陳述一般圖中求最大對集的匈牙利算法：任取一個(gè)非飽和節(jié)點(diǎn)，記。令為型節(jié)點(diǎn)（若

15、中沒有非飽和節(jié)點(diǎn)，那么為最大對集）。一般地，設(shè)已有。用反圈法在中進(jìn)行選邊，若在某一步，發(fā)現(xiàn)花苞，則收縮花苞。令偽節(jié)點(diǎn)為型節(jié)點(diǎn)，繼續(xù)選邊：若在某一邊，得到增廣樹，則得到增廣路并且調(diào)節(jié)；若在某一步得到匈牙利樹，則再去一個(gè)非飽和節(jié)點(diǎn)，放入中，繼續(xù)選邊；若不再有非飽和節(jié)點(diǎn)，則是最大對集。下面將要證明：當(dāng)算法終止時(shí)，是最大對集。為此，考察一下算法終止時(shí)我們得到什么結(jié)構(gòu)。當(dāng)中無邊可選，并且所有的非飽和節(jié)點(diǎn)都在中時(shí)，算法終止。此時(shí)得到的交錯(cuò)樹都是匈牙利樹。是這些匈牙利樹的節(jié)點(diǎn)集合，其中每一個(gè)節(jié)點(diǎn)或是型節(jié)點(diǎn)，或是型節(jié)點(diǎn)（可能是偽節(jié)點(diǎn)），每一個(gè)樹種恰好有一個(gè)節(jié)點(diǎn)是非飽和節(jié)點(diǎn)。我們稱中節(jié)點(diǎn)生成的子圖中的連通分支為

16、無型分支。在每一個(gè)無型分支中，由于不含有非飽和節(jié)點(diǎn)，股必有偶數(shù)個(gè)節(jié)點(diǎn)。結(jié)論5.圖的邊必是下列情況之一：（1） 在某一個(gè)偽節(jié)點(diǎn)所對應(yīng)的奇數(shù)階生成子圖中；（2） 是某一個(gè)樹上的邊或是連接樹內(nèi)部兩個(gè)節(jié)點(diǎn)；（3） 連接兩個(gè)匈牙利樹；（4） 在某個(gè)無型分之內(nèi)部；注意：在情況（2）-（3）之下，每一邊的端點(diǎn)中有一個(gè)-節(jié)點(diǎn)。下面介紹所謂的“奇節(jié)點(diǎn)集合覆蓋”，它是Konig關(guān)于二部圖中點(diǎn)覆蓋概念的自然推廣。對于圖中的節(jié)點(diǎn)集合，如果，則說是一個(gè)奇點(diǎn)集合。若，則說覆蓋了與它關(guān)聯(lián)的所有邊；并且定義；如果，我們說覆蓋了生成子圖中的所有邊，并且定義假定是一個(gè)圖中的奇點(diǎn)集合族，如果的每一邊至少被某一個(gè)所覆蓋，則說構(gòu)成了的

17、一個(gè)奇集覆蓋。定義。結(jié)論6.對于任何一個(gè)對集和和任何一個(gè)奇集覆蓋，。現(xiàn)在設(shè)是一個(gè)對集，我們可以執(zhí)行匈牙利算法，算法終止，得到一個(gè)對集，一批匈牙利樹和一些無型分圖，現(xiàn)在來制造一個(gè)奇集覆蓋如下：每一個(gè)型節(jié)點(diǎn)自然形成一個(gè)奇集合；每一個(gè)偽節(jié)點(diǎn)所對應(yīng)的奇數(shù)階生成子圖為一個(gè)奇點(diǎn)集合；對于無型分圖，取其中一個(gè)端點(diǎn)為一個(gè)奇集；根據(jù)結(jié)論5，我們有下面的結(jié)論7.上述奇集合全體是圖的一個(gè)奇集覆蓋。在結(jié)論7基礎(chǔ)上自然有，這樣，就是一個(gè)最大對集。定理（Edmonds1965）對于任何一個(gè)圖，注意：因?yàn)橐粋€(gè)而部圖中不含有奇圈，在二部圖中執(zhí)行匈牙利算法時(shí)不會有花型結(jié)構(gòu)出現(xiàn)，并且每一個(gè)無型分圖是不含非飽和節(jié)點(diǎn)的二部圖，可以用

18、個(gè)節(jié)點(diǎn)去覆蓋所有無型分圖的節(jié)點(diǎn)。因此，對于二部圖以及一個(gè)最大對集，總可以找到一個(gè)由單元素集合形成的奇集覆蓋使得，這就是Konig定理。例。 給定如圖所示，粗邊表示邊。，是非飽和點(diǎn)。令，為型節(jié)點(diǎn)，在中選邊，令，為型節(jié)點(diǎn)，在中選邊，令為型節(jié)點(diǎn)，如此等等，得到以為根的匈牙利樹（下圖）現(xiàn)在再取節(jié)點(diǎn)為根節(jié)點(diǎn)，也是型節(jié)點(diǎn)，繼續(xù)選邊，最終得到以為根節(jié)點(diǎn)的匈牙利樹（下圖）余下的是無型分圖（下圖）算法終止時(shí)，。選取奇集合覆蓋為滿足條件下面要用Edmonds 的這個(gè)算法證明下面的定理（Berge,1958）.設(shè)是圖中最大對集，則非飽和節(jié)點(diǎn)數(shù)為從而解答：（1）首先證明：對于任何一個(gè)集合，有。設(shè)是所有的奇分支，若中每一個(gè)節(jié)點(diǎn)都被飽和，那么至少有一條邊，它要連接中一個(gè)節(jié)點(diǎn)與中一點(diǎn)，并且不同的對應(yīng)的也不相同。這樣，不含有非飽和節(jié)點(diǎn)的奇分支數(shù)目。由于含有非飽和節(jié)點(diǎn)的奇分支數(shù)目這樣，。（2）證明：存在設(shè)是最