計算圖中的最大對集的匈牙利方法

1、計算圖中的最大對集的匈牙利方法計算圖中的最大對集的匈牙利方法背景知識介紹背景知識介紹—在一個網(wǎng)絡中往往要求計算其中的最大對集。是由匈牙利人Egervary于1931年發(fā)現(xiàn)，后被另外一個匈牙利人Edmonds所推廣（到一般圖中的“開花算法”）基本方法基本方法—利用反圈法第一節(jié)第一節(jié)二部圖中最大對集的有效算法二部圖中最大對集的有效算法設為一個二部圖，是中一個對集。()GSTE?M型節(jié)點位于的節(jié)點；S?S型節(jié)點位于中的節(jié)點；T?T邊位于中的邊

2、；MM注意：注意：一個增廣路的長度為奇數(shù)，所以這樣的路的兩個端點必須是同型節(jié)點。反圈法基本原則反圈法基本原則（1）初始時，令；0k?(0)|XvSv??是關于M的非飽和點（2）在中選邊時，必須按照以下原則：?(k)（X）(a)如果時，則選取以為端點的非邊（即，在型節(jié)點處只選非邊）()kivXS??ivMS?M；(b)如果，則選取以為端點的邊（即，在型節(jié)點處只選邊）()kivXT??ivMT?M（3）若在某一步，出現(xiàn)下述情況之一時算法要終

3、止：情況情況1。中有非飽和的型節(jié)點（此時得到一條關于的增廣路）；()kXT?M情況情況2.。情況。情況1不出現(xiàn)，且不出現(xiàn)，且中無邊可選（此時中不存在關于的增廣路）。()()kX?GM定理定理1.當匈牙利算法結(jié)束時，得到一個最大對集解答：下面我們來證明這個方法（算法）的正確性。如果情況如果情況1發(fā)生發(fā)生，根據(jù)我們算法特點，每一步上都是森林，其中每一個樹都是()()()kkXE以中的一點為根的。根據(jù)的定義，每一個樹以一個非飽和的型節(jié)點為根。

4、按(0)X(0)XS?照選邊原則（2）可以看出：每一個樹上，根與任意節(jié)點之間的唯一的路是交錯路、。所以，當某個非飽和的型節(jié)點屬于時，這個樹上聯(lián)接根節(jié)點與它的路是一個長度為奇數(shù)T?()kX的增廣路?，F(xiàn)在假定情況2出現(xiàn)。我們用表示此時的（一定要記住：中的每一個節(jié)點都位X()kXX于一個樹中）。令記XVX??樹中所能包含的邊形成的子對集，而則是無法被這些樹所含有的子對集（可以為空M2M集）；（2）對集所能飽和的的節(jié)點集合為，沒有被飽和的節(jié)點集

5、合為MS132AA?(0)31()AX?（3）；123313244142ASXATXAAAAAA????????（4）（這是由于無法選邊決定的，否則，有些子樹可以長大）；42131[]EAAA???（5）（理由同上）。41131[]EAAA???這樣，結(jié)論結(jié)論1.所有非飽和的型節(jié)點都在中（這是根據(jù)的定義得到的。表明：每一個S?31A(0)X這樣的非飽和型節(jié)點都是一個樹的根，這個樹有可能退化為一個節(jié)點?。籗?結(jié)論結(jié)論2。所有的非飽和的型

6、節(jié)點都在中（否則，選邊原則（1）可得到增廣路）；T?41A結(jié)論3.；4131[]EAAA???結(jié)論4.3124132()()NAANAA??結(jié)論5.。（這是由圖的連通性決定的）3223241[][]EAAEAA????結(jié)論6.；2413[]EAAAM????這樣一來，若中存在增廣路，那么它的一個端點在中，另外一個端點在中。顯G31A41A然此時可以選邊使得對集增大。矛盾。因此，當情況2發(fā)生時當前的對集是最大的。注意：從上述分析中可知，我

7、們的討論可以假定。分析中得到的結(jié)構(gòu)（結(jié)論3242AA???16）非常有用，我們可以直接利用它們來計算。定理定理2.任何一個使得的二部圖中一定有一個最大對集飽和所有最|()|0EG?()GSTE?大次節(jié)點。點評點評：如果這個結(jié)果成立，那么這個圖一定是第一類的（即，邊色數(shù)。）()()GG???解答：設是這樣一個最大對集，它所飽和的最大次節(jié)點最多。我們將要證明：為MM所求。若不然，則存在一個最大次節(jié)點，沒有被所飽和。不妨設可以取使vMvS?M