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

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

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

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

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

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

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

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