1、第五章 獨立集與匹配 第一節(jié) 獨立集定義1 設(shè)G=是簡單圖無向圖,SV,S,若S中任何兩個頂點都不相鄰,則稱這個頂點集合S為圖G的獨立集.若S是圖G的獨立集,但是任意增加一個頂點就破壞它的獨立性,則稱這個獨立集S為極大獨立集. 獨立集S稱為最大獨立集,如果不存在獨立集S,使 ,其中 為集合S的數(shù).G的最大獨立集S的基數(shù)稱為G的獨立數(shù),記作 (G).說明1:簡單無向圖G的獨立集,實際是對圖G的頂點進行著色的結(jié)果.把圖G的頂點集V劃分成若干不相交的子集, ,SSSS把圖G的頂點集V劃分成若干不相交的子集,每個子集中的各結(jié)點著同一色.上述不相交的子集的最少個數(shù)即為圖G的色數(shù).說明2:圖G的極大獨立集

2、不是唯一的,且頂點數(shù)目最多的極大獨立集是最大獨立集.定義2 設(shè)G=是簡單無向圖,同時將G的鄰接矩陣第I行與第j行, 第i列與第j列互換,稱為一次平移變換.說明3:平移變換不改變鄰接矩陣所表示圖G的各頂點之間的關(guān)系,緊緊僅僅改變了i,j的編號.也就是說,鄰接矩陣的平移變換對應(yīng)于圖中結(jié)點的一個重新編號.反之,結(jié)點的重新編號對應(yīng)于鄰接矩陣的一系列平移變換.定理1 設(shè)G=是具有n個結(jié)點的無向簡單圖,A是G的鄰接矩陣,且A具有如下形式:令 ,若 ,則其已確定一極大集S=V1,V2,Vi,其中Vt(1t i)為A下三角陣的第t行.證明:由矩陣A可知,akj(1 ji),即結(jié)點V1,V2,Vi互不相鄰.在A

3、21中,因bj(i+1 jn),則aj1,aj2,aji中必有一 innniiiiiiiiininTaaaaaaaaaARAAAAA,2,1 , 22, 21 , 2, 12, 11 , 121)()(22222121,0),.,1(1nijabikjkj),.,1(0nijbj 元素為1,不妨設(shè)ajk=1(1 ji),即Vj與Vk相鄰.由j=i+1,i+2,n的任意性得Vi+1,Vi+,Vn中所有元素都與S=V1,V2,Vi相鄰接,而S=V1,V2,Vi中任何兩點不鄰接.由極大獨立集的定義可知 S=V1,V2,Vi即為G的一個極大獨立集.定理2.設(shè)A是簡單無向圖G=的鄰接矩陣,則總可以通過若

4、干次平移將A化為標準型,從而得到圖G的一個極大獨立集. 基于布爾運算的圖G的所有極大獨立集的求法.幾個約定:已知簡單無向圖G=,且V=V1,V2,Vn,規(guī)定:(1)G的每個頂點Vi當作一個布爾變量;(2)ViVj表示包含Vi和Vj;(3) ViVj表示或者包含一頂點Vi;或者包含一頂點Vj;或者包含Vi和Vj兩個頂點.說明:(2)和(3)中的運算有類似集合運算的性質(zhì).基于布爾運算的圖G的所有極大獨立集的求法:由于過圖G的頂點Vi,Vj的邊對應(yīng)布爾表達式 ,即中的每一項ViVj對應(yīng)G的一條邊, 表示對所有的邊求和.由德.摩根律,有 .設(shè) 都是含有布爾變量V1,V2,Vn的表達式,又G的極大獨立集

5、不包含任何一邊的兩個頂點,故表達式在任一極)(,jijViVVVV)(_,_jiEjViVVV _21_,k 大獨立集上取布爾值0(F);反之,使取值0的點集是獨立集.即取布爾值0是獨立集的的充要條件.或 取布爾值1也是獨立集的充要條件.從而分別使1, 2, k取布爾值1的點集都是極大獨立集.例1.通過布爾運算,求下圖G的極大獨立集. 圖Gk 21_v1v2v4v3v6v5定義2.設(shè)G=是無向簡單圖,SV,S.若E中每條邊都與S中某點關(guān)聯(lián),則稱S為G的點覆蓋.如果G中的任何異于S的點覆蓋S,均有 ,則稱S為G的最小點覆蓋.最小點覆蓋S的基數(shù) 稱為G的點覆蓋數(shù),記作(G).點覆蓋S稱為極小點覆蓋

6、,若對任何xS,S-x都不是點覆蓋.定理3.設(shè)G=是無向簡單圖,SV,S,則S是G的獨立集V-S是G的點覆蓋.證:S是G的獨立集G中每條邊的兩端點都不同時屬于S G中每條邊至少有一端點在V-S中V-S是G的點覆蓋.推論1 S是G的極大獨立集V-S是G的極小點覆蓋.SS S推論2.(G)+(G)=V(G).證明:設(shè)S1是G的最大獨立集,S2是G的最小點覆蓋,由定理3知V(G)-S1是點覆蓋,V(G)-S2是獨立集.因而V(G)- (G)= V(G) -S1 (G)V(G)- (G)= V(G) S2 (G)所以(G)+(G)=V(G).定義2.設(shè)G=是無向簡單圖,LE,L.若G中每個頂點都與L中

7、某條邊關(guān)聯(lián),則稱L為G的邊覆蓋.如果G中的任何異于L的邊覆蓋L,均有L L ,則稱S為G的最小邊覆蓋.最小邊覆蓋L的基數(shù) L 稱為G的邊覆蓋數(shù),記作(G).第二節(jié) 獨立集的應(yīng)用定義1 設(shè)G1=和G2=是兩個無向簡單圖,其中V1=a1,a2,an,V2=b1,b2,bm.圖G=G1G2稱為圖G1和G2的乘積,若滿足:(1)V=aiV1,bj V2;(2)adj()= ak adj( ai) bt adj(bj) ak adj( ai), btadj(bj) ,其中adj(vi)表示與vi相鄰的點的集合.例1.已知G1和G2,則G1G2如下:G1G2G1G2獨立集的應(yīng)用舉例例2.(收款臺的設(shè)置問題

8、)某大型商場為加強經(jīng)營管理,對商品的零售收入實行統(tǒng)一收款制度.為了使顧客在任何一個貨架前都能看到收款臺,問收款臺應(yīng)設(shè)置在什么地方且至少要設(shè)置多少個收款臺?問題分析:建立簡單無向圖G=,該商場兩排貨架之間的通道為G的邊,通道交叉處為G的頂點.為使顧客在任何一個貨架前都能看到收款臺,從盡可能減少收款臺的數(shù)目來說,收款臺應(yīng)設(shè)在通道的交叉處.故收款臺的設(shè)置問題轉(zhuǎn)化為在G中找出一個最小點覆蓋或G的一個最大獨立集.例3 求下圖G的最小點覆蓋定義2:(圖G的團)設(shè)G=是無向簡單圖,TV,T.若T中任意兩個頂點都相鄰,則稱T是圖G的團.若T是圖G的團,但任意增加一個新頂點后,它就不是團,則稱T是圖G的極大團.

9、v1v2v5v6v3v4G團的應(yīng)用團的應(yīng)用 用團可以求圖的極大獨立集用團可以求圖的極大獨立集:一個圖的團的概念在一個圖的團的概念在下述意義下與獨立集是下述意義下與獨立集是“互補的互補的”.設(shè)設(shè)G=是簡單無是簡單無向圖向圖,其中其中V=1,2,n. 是是G的補圖的補圖,其中其中頂點頂點i與與j在補圖中相鄰在補圖中相鄰,當且僅當頂點當且僅當頂點i與與j在在G中不相鄰中不相鄰.由獨立集與團的定義可知由獨立集與團的定義可知S是是G的極大獨立集當且僅當?shù)臉O大獨立集當且僅當S是其補圖的極大團是其補圖的極大團,因此因此,求圖求圖G的極大獨立集可轉(zhuǎn)化的極大獨立集可轉(zhuǎn)化為求其補圖的極大團為求其補圖的極大團.請同

10、學(xué)們看請同學(xué)們看p178的例的例2. 說明說明:一般來說一般來說,如何求出一個圖如何求出一個圖G的所有極大團是的所有極大團是圖論中的一個難題圖論中的一個難題.,GV E第三節(jié) 支配集定義1.設(shè)G=是無向簡單圖,SV,S,若對于xV-S,x與S里至少一個頂點相鄰,則稱S是圖G的支配集. S是圖G的支配集,若S的任何真子集都不是支配集,則稱S為圖G的極小支配集. S是圖G的支配集,若不存在任何其他支配集S,使得S S,則稱S是圖G的最小支配集, S為圖G的支配數(shù),記作(G).例1.求下圖G的一個最小支配集p179.14 56923107811支配集的應(yīng)用支配集的應(yīng)用 支配集首先出現(xiàn)在國際象棋比賽中

11、支配集首先出現(xiàn)在國際象棋比賽中. .一個一個8 8* *8 8的的棋盤具有棋盤具有8 8* *8 8配置下的配置下的6464個格子個格子. .在所給某個位置的在所給某個位置的皇后控制著同行皇后控制著同行、同列以及包含這個格子的兩同列以及包含這個格子的兩條斜線上的所有格子條斜線上的所有格子.1862.1862年年,De Jaenisch,De Jaenisch考考慮了控制整個棋盤所需要的最少的皇后最少慮了控制整個棋盤所需要的最少的皇后最少個數(shù)為個數(shù)為5.5.若要求任兩個皇后都不相互攻擊若要求任兩個皇后都不相互攻擊, ,即即任兩個皇后都不在同一行任兩個皇后都不在同一行、同一列或同一斜同一列或同一斜

12、線上線上,那么這種皇后的最少個數(shù)為那么這種皇后的最少個數(shù)為7.請同學(xué)們請同學(xué)們看看p180的圖的圖5-8. 棋盤問題可以轉(zhuǎn)化為求支配集的基數(shù)棋盤問題可以轉(zhuǎn)化為求支配集的基數(shù): 作簡單圖G,G的頂點集與棋盤上的64個格子一一對應(yīng),且兩個頂點在G中相鄰當且僅當兩個對應(yīng)格子中的一個格子可以由位于另一個格子中的皇后控制,則支配棋盤中全部格子的皇后的最少個數(shù)為圖G的支配數(shù).關(guān)于支配集的幾個性質(zhì)定理定理1.圖G的支配集S是G的極小支配集當且僅當S中的每個頂點x滿足如下條件之一:(1)存在yV(G)-S使得N(y)S=x,其中N(y)為y的鄰接點集合.(2) N(x)S=.證明:充分性:如果S中每個頂點至少

13、滿足(1)和(2)中一個,則S-x就不是支配集,故S是G的一個極小支配集.必要性;若S是G的極小支配集,則對每個xS,S-x就不是G的支配集.故存在頂點y V(G)-(S-x),使得沒有S-x中頂點與y鄰接.如果y=x,則S中沒有頂點與x鄰接.所以SN(x)= .若yx,因為S是G的支配集且yS,故頂點y至少與S中一個頂點相鄰.又y不與S-x中頂點相鄰,故N(y)S=x.定理2.若G是沒有孤立結(jié)點的圖,且S是G的極小支配集,則V(G)-S也是G的支配集.證明:因為G是沒有孤立結(jié)點的圖,且S是G的極小支配集,所以S中無孤立結(jié)點,且對于S中任何一個頂點,在V-S中有一個頂點與之相鄰,所以V(G)-

14、S也是G的支配集.推論1.若G是n階無孤立結(jié)點的圖,則(G)n/2.證明:不妨設(shè)S是G的一個極小支配集,由定理2,V(G)-S也是G的一個支配集,從而(G)min|S|,|V(G)-S| n/2.定理3.若G是無孤立結(jié)點的圖,則存在G的最小支配集S使得對S中每個頂點x,存在V(G)-S中的頂點y滿足:N(y)S=x,其中N(y)為y的鄰接點集合.證明證明:用反證法用反證法.以以GS表示表示S的導(dǎo)出子圖的導(dǎo)出子圖.在在G的全部最的全部最小支配集中小支配集中,設(shè)設(shè)S是使是使GS滿足滿足|E(GS)| 達到最大的一個最小支配集最小支配集.假設(shè)定理結(jié)論不成立假設(shè)定理結(jié)論不成立,S至少包含一個不具備上至

15、少包含一個不具備上述性質(zhì)的頂點述性質(zhì)的頂點x,即對即對 y V(G)-S,N(y) S x.由定理由定理1,x是是GS的孤立結(jié)點的孤立結(jié)點.又因為又因為S為為G的最小支配集的最小支配集,所以對所以對 y V(G)-S,N(y) S即與即與x鄰接的鄰接的V(G)-S中的每個頂點一定與中的每個頂點一定與S中的另外一個中的另外一個頂點鄰接頂點鄰接.由于由于G不含孤立結(jié)點不含孤立結(jié)點,所以所以x與與V(G)-S中某個頂點中某個頂點y鄰接鄰接,故故(S-x) y是是G的最小支配集的最小支配集,且其導(dǎo)出子圖中至且其導(dǎo)出子圖中至少包含一條與少包含一條與y關(guān)聯(lián)的邊關(guān)聯(lián)的邊,要比要比GS中的邊數(shù)多中的邊數(shù)多,與

16、與S的構(gòu)造的構(gòu)造矛盾矛盾.定理4.若G是n階圖,則n/1+(G)(G)n- (G).證明:設(shè)S是G的最小支配集,則定理5.圖G的一個頂點集S是一個獨立支配集當且僅當S是一個極大獨立集.證明:必要性:因為S既是一個獨立集又是一個支配集,故在S中任意增加V-S中一個頂點時,S就不是獨立集,所以S是一個極大獨立集.充分性:因為S是一個極大獨立集,所以在S中任意增加V-S中一個頂點時,S中必有一頂點與之相鄰,故S也是支配集.( )( ),( )( ).n(G).1(G)x SV GSN xV GSSG即從而推論2.圖G的每個極大獨立集是一個極小支配集.證明:設(shè)S是圖G的一個極大獨立集.由定理5,S是一

17、個支配集.因為S是獨立集,故S中的每個頂點不與S中其他頂點鄰接.即S的每個頂點滿足定理1中的性質(zhì)(2),所以S是極小獨立集.說明:不是每個支配集都是獨立集,也不是每個最小支配集都是獨立集,請看p183的圖5-9. 支配集的實際應(yīng)用背景:要在n座城市中建一個通信系統(tǒng),需在這n個城市中選其中的幾個建立通訊站,為減少造價,要使通訊站數(shù)目最少,應(yīng)如何選址?問題解決辦法:作圖G:以城市作為圖G的頂點,當兩城市之間有直通訊線路時,相應(yīng)的兩頂點連一邊,則圖G的最小支配集為所求. 極小支配集的布爾計算:請看p184-185.第四節(jié) 匹配 匹配問題是運籌學(xué)的重要問題之一,也是圖論研究的重點內(nèi)容,它提供了解決“人

18、員分配問題”和“最優(yōu)分配問題”一種新的思想.定義1.設(shè)G=是無環(huán)圖,ME(G),M,若M中任意兩條邊都不相鄰,則稱M是圖G的一個匹配.若對圖G的任何匹配M ,均有MM,則稱M是圖G的最大匹配,G中最大匹配中的邊數(shù)稱為匹配數(shù)，記作(G).定義2.設(shè)M是圖G的匹配,G中與M中的邊關(guān)聯(lián)的頂點稱為M飽和點.若圖G的頂點都是M飽和,則稱M為G的完美匹配.說明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定義與邊的方向無關(guān),故匹配是針對無向圖而言.(3)圖G的邊不交匹配的最小數(shù)目即為G的邊色數(shù).定義3.(可增廣路):設(shè)M是圖G的匹配,P是G的一條路,且在P中,M的邊和E(G)-M的邊交替出現(xiàn),則稱P是

19、G的一條交錯路.若M交錯路P的兩個端點為M非飽和點,則稱P為M可增廣路.例1.求下圖G的一條交錯路和一條可增廣路.62341587匹配的幾個性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個不同匹配,記H=M1M2則H的任意連通分支是下列情況之一: (1)邊在M1和M2中交錯出現(xiàn)的偶圈. (2)邊在M1和M2中交錯出現(xiàn)的路.(3)孤立結(jié)點.證明:若H中無邊,顯然是第三種情況.若H是邊導(dǎo)出子圖,由連通性易知(H)1.由于M1和M2是圖G的兩個不同匹配,所以H的任意頂點x至多與一條M1的邊關(guān)聯(lián),同時也至多與一條M2的邊關(guān)聯(lián),所以Deg(x)2,所以 2,故H的每個連通分支或者是一條路或者是一個圈.據(jù)匹配的定

20、義,H的任意兩條鄰接邊一定分別屬于不同的匹配M1和M2,從而每條路或者圈的邊交錯地屬于M1和M2且每個圈是偶圈.定理2.M是圖G的最大匹配,當且僅當G中不存在M可增廣路.證明:()假設(shè)存在M可增廣路P,則M=MP是G的一個新的匹配,且|M|M|1|M|,矛盾.()若M不是G的最大匹配,則存在匹配M,使得|M|M|,作H=MM,由定理1,H的任意連通分支Q是下列三種情況之一:(1)交錯偶圈:Q中每個結(jié)點度數(shù)為2.(2)交錯路.Q中除端點外,其余結(jié)點度數(shù)均為2.(3)孤立結(jié)點.Q中的每個結(jié)點度數(shù)均為0,該結(jié)點即為關(guān)聯(lián)MM中邊的結(jié)點. 因為|M|M|,故|E(H)M|E(H)M|,因而H中必有一條起

21、始于M且終止于M的連通分支P,故P是M可增廣路,矛盾,所以命題正確. 定義:NG(S):設(shè)S是圖G的任意頂點子集,G中與S的頂點鄰接的所有頂點的集合,稱為S的鄰集,記做NG(S).定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V2)的二分圖,則G含有飽和V1的每個頂點的匹配M的充要條件是,對SV1,有N(S)S.證明:()對SV1,匹配M將S中的每個頂點與N(S)中的頂點配對,所以N(S)S.()當對SV1,有N(S)S時.可按下述方法作出飽和V1的匹配M. 先作一初始匹配M1,若已經(jīng)飽和V1,定理得證.否則,V1中至少有一非飽和點x1,檢查以x1為起點,終點在V2中的交錯路.考慮下

22、面兩種情形:(1)不存在任何一條交錯路可以到達V2的非飽和點.此時從X1開始的一切交錯路的終點還是在V1中.故存在AV1,使得N(A)M1,因此,重復(fù)該過程就可以找到飽和V1的全部頂點的匹配M.推論1具有二部劃分(V1,V2)的二分圖G有完美匹配 V1=V2,且對SV1(或V2),有N(S)S.證明:必要性.若二分圖G有完美匹配,由定理3有V2=N(V1)V1,即V2V1,同理V1V2,因此V1=V2.充分性:因為對對SV1,有N(S)S,由定理1,G中存在飽和V1的每個頂點匹配M,又G是二分圖,故匹配M的每一邊的兩個端點分別屬于V1和V2,據(jù)V1=V2即知M飽和V2,所以M為完美匹配.推論2

23、.設(shè)G是k(0)正則二分圖,則G有完美匹配.證明:因為G是二部劃分(V1,V2)的k正則二分圖,故 kV1=E(G)=kV2 又k0,所以V1=V2.任取SV1,并用E1和E2分別表示G中與S和N(S)中關(guān)聯(lián)的邊集,則E1E2,則對 SV1, kN(S)=E2E1=kS即N(S)S, 由定理3可知,G有飽和V1的匹配M,再據(jù)V1=V2和推論1即知M是完美匹配.推論3.設(shè)G是二部劃分(V1,V2)的簡單二分圖,且V1=V2=n,若(G)n/2,則G有完美匹配.證明:SV1,(1)若S中至少有兩個頂點,由(G)n/2可知N(S)n/2+n/2=n=V1S(2)若S中只有一個頂點,由(G)n/2可知

24、N(S)n/2,所以 N(S)1S=1.綜上,對SV1,均有N(S)S,所以G中有完美匹配.定理4.G有完美匹配O(G-S) S,SV(G),其中O(G-S)是G-S的奇數(shù)階連通分支數(shù)目.例1.有n張紙牌,每張紙牌的正反兩面都寫上1,2,n的某一個數(shù),證明:如果每個數(shù)字恰好出現(xiàn)兩次,則這些紙牌一定可以這樣攤開,使朝上的面中1,2,n都出現(xiàn).解:作一個二分圖G=,其中V1=1,2,n,V2=y1,y2,yn表示這n張紙牌.i與yi之間連接的邊數(shù)等于數(shù)i在紙牌yj中出現(xiàn)的次數(shù),這樣得到的圖G是一個2-正則二分圖,因此圖G中有完美匹配,設(shè)為M=1yi1,2yi2,nyin 則只要把紙牌yi1中的1朝

25、上,yi2中的2朝上,yin的n朝上,這樣攤開,這樣攤開的紙牌就能使上面中1,2,n都出現(xiàn).例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該廠所生產(chǎn)的雙色布中,每一種顏色至少和其他三種顏色搭配.證明可以挑選出三種不同的雙色布,它們含有所有的6種顏色.證明:構(gòu)造圖G=,其中V=v1,v2,v3,v4,v5,v6表示6種顏色,工廠生產(chǎn)出一種顏色vi與vj搭配而成的雙色布邊vi,vjE(G).由題意知,G為簡單圖,且每個結(jié)點的度數(shù)至少為3,下證G中含有一個完美匹配. 今設(shè)v1,v2E(G),由于d(v3) 3,所以存在一個不同于v1和v2的頂點vi(4i6),使v3,viE(G),不妨設(shè)vi=

26、4,即v3,v4E(G). 如果邊v5,v6E(G),由于d(v5)3,v1,v2,v3,v4中至少有3個頂點與v5相鄰,即v5與邊v1,v2,v3,v4中的每一邊的某一個端點相鄰,不妨設(shè)v1,v5E(G)和v3,v5E(G). 對于頂點v6,同樣與v1,v2,v3,v4中至少3個頂點相鄰,即在v2和v4中至少有一個頂點與v6相鄰.如果v2,v6E(G),則邊v1,v5,v3,v4,v2,v6是G的一個完美匹配;如果v4,v6E(G),則v1,v5,v3,v5,v4,v6是G的一個完美匹配. 綜上所述,G總存在完美匹配,完美匹配中的三條邊所對應(yīng)的三種雙色布即為所求.第五節(jié) 最大匹配的生成算法-

27、匈牙利算法定義1.根在x的M交錯子圖:設(shè)M是圖G的匹配,x是G中非M飽和點.G中由起點為x的M交錯路所能連接的頂點集所導(dǎo)出的G的導(dǎo)出子圖稱為根在x的M交錯子圖.定理1.設(shè)M是具有二部劃分(V1,V2)的二分圖G的匹配,xV1是非M飽和點,H是G中根在x的M交錯子圖的頂點集S=HV1,T=HV2,則:(1)TNG(S);(2)下述三條等價:(a)G中不存在以x為端點的M可增廣路;(b)x是H中唯一的非M飽和點;(c) T=NG(S),且T=S-1.證明證明:(1) y T,則則G中存在以中存在以x和和y為端點的為端點的M交錯路交錯路P.令令u Np(y),由于由于G是二分圖且是二分圖且y T V

28、2,所以所以u H V1=S,即即y NG(S),因而因而T NG(S),.(2)(a)(b)設(shè)設(shè)y是是H中異于中異于x的非的非M飽和點飽和點,則則G中存在以中存在以x和和y為端點的為端點的M交錯路交錯路P.P是是G中以中以x為端點的為端點的M可增廣路可增廣路,與與(a)矛盾矛盾.(b)(c)任取任取y NG(S) V2,則存在則存在u S=H V1和邊和邊e E(G)使使 G(e)=u,y.若若u=x,顯然有顯然有y T.若若u x,則則G中存在以中存在以x和和u為端點的交錯路為端點的交錯路P.因為因為x是唯一非是唯一非M飽和點飽和點,所以所以u為為M飽和飽和點點.若若P不含不含y,則則e

29、M.由由H的定義知的定義知,y H V2=T,所以所以NG(S) T,再由再由(1),T= NG(S).(3) (c)(a)反設(shè)反設(shè)G中存在以中存在以x為端點的為端點的M可增廣路可增廣路,則則G中至中至少還存在一個異于少還存在一個異于x的非的非M飽和點飽和點y,若若y S,則則y T NG(S),顯然顯然y T(交錯路中不可能含有兩個非交錯路中不可能含有兩個非M飽和點飽和點),與與T=NG(S)矛盾矛盾.若若y S,則顯然有則顯然有T=S-2.矛盾矛盾. 所以所以G中不存在以中不存在以x為端點的為端點的M可增廣路可增廣路.匈牙利算法基本思想:設(shè)G是具有二部劃分(V1,V2)的二分圖,從圖G的任

30、意匹配M開始.若M飽和V1,則M是G的匹配.若M不能飽和V1,則在V1中選擇一個非M飽和點x,若G中存在以x為起點的M可增廣路P,則M=MP就是比M更大的匹配,利用M代替M,并重復(fù)這個過程.若G中不存在以x為起點的M可增廣路,則令H是根在x的M交錯子圖的頂點集,并令S=HV1,T=HV2, 由定理1,T=NG(S),且G中不存在以x為起點的M可增廣路,此時稱x為檢驗過的非M飽和點.對V1中其它未檢驗過的非M飽和點重復(fù)該過程,直到V1中的所有非M飽和點全部檢驗過為止.當整個過程結(jié)束時,由于G中不存在M可增廣路,從而M為G的最大匹配.匈牙利算法步驟:設(shè)G是具有二部劃分(V1,V2)的二分圖.(1)

31、任給初始匹配M;(2)若M飽和V1則結(jié)束.否則轉(zhuǎn)(3);(3)在V1中找一非M飽和點x,置S=x,T=;(4)若N(S)=T,則停止,否則任選一點yN(S)-T;(5)若y為M飽和點轉(zhuǎn)(6),否則作求一條從x到y(tǒng)的M可增廣路P,置M=MP,轉(zhuǎn)(2)(6)由于y是M飽和點,故M中有一邊y,u,置S=Su,T=Ty,轉(zhuǎn)(4).例1.如圖G所示,V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5試求圖G的最大匹配. 圖(a) 圖(b) x1, x2 x3 x4 x5y1 y2 y3 y4 y5x1 x2 x3 x4 x5y1 y2 y3 y4 y5解:任取初始匹配M=x2y2,x3y3,x5y5,如圖(a)中虛線所示.解題過程如下表:MxSTN(S)yN(S)-Ty,u MPx2y2,x3y3,x5y5 x1x1y2,y3y2飽和y2,x2x1,x2y2y1,y2,y3,y4,y5y1非飽和(x1y2y2y2)x1y2,x2y1,x3y3 x5y5x4x4y2,x3y2飽和y2,x1x4,x1y2y2,y3y3飽和y3,x3x4,x1,x3y2,y3y2,y3N(S)=T,停止因此,M=x1y2,x2y1,x3y3,x5y5即為圖G的最大匹配,如圖(b)虛線所示.匈牙利算法的時間復(fù)雜度分析