資源描述：
《圖論課件--匈牙利算法與最優(yōu)匹配算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、圖論及其應用應用數(shù)學學院1本次課主要內(nèi)容(一)、匈牙利算法(二)、最優(yōu)匹配算法匈牙利算法與最優(yōu)匹配算法2(一)、匈牙利算法1、偶圖中尋找完美匹配(1)、問題設G=(X,Y),
2、X
3、=
4、Y
5、,在G中求一完美匹配M.(2)、基本思想從任一初始匹配M0出發(fā)，通過尋求一條M0可擴路P，令M1=M0ΔE(P),得比M0更大的匹配M1(近似于迭代思想)。(3)、M可擴擴路的尋找方法1965年，Edmonds首先提出:用扎根于M非飽和點u的M交錯樹的生長來求M可擴路。3定義1設G=(X,Y),M是G的匹配，u是M非飽和點。稱樹H是G的扎根于點u的M交錯樹,如果：1)u∈V(T)；2)對任意v∈V(T),(
6、u,v)路是M交錯路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交錯樹扎根于M非飽和點u的M交錯樹的生長討論：4假如扎根于M非飽和點u的M交錯樹為H,對于H,有兩種情形：情形1除點u外，H中所有點為M飽和點，且在M上配對；x4ux2y4y3y2扎根u的M交錯樹Hx5情形2H包含除u外的M非飽和點。x4ux2y4y3y2扎根u的M交錯樹H5對于情形1，令S=V(H)∩X,T=V(H)∩Y,顯然：1)若N(S)=T,由于S-｛u｝中點與T中點配對，所以有：
7、T
8、=
9、S
10、-1,于是有：
11、N(S)
12、=
13、S
14、-1<
15、S
16、.由Hall定理，G中不存在完美匹配；2)
17、若令y∈N(S)–T,且x與y鄰接。因為H的所有點，除u外，均在M下配對。所以，或者x=u，或者x與H的某一頂點配對，這樣，有若y為M飽和的，設yz∈M,則加上頂點y及z和邊xy與yz生長H，得到情形1；6若y為M非飽和的，加上頂點y和邊xy生長H，得到情形2.找到一條M可擴路，可以對匹配進行一次修改，過程的反復進行，最終判定G是否有完美匹配或者求出完美匹配。根據(jù)上面討論，可以設計求偶圖的完美匹配算法。(4)、偶圖完美匹配算法——匈牙利算法。設M是初始匹配。(a)、若M飽和X所有頂點，停止。否則，設u為X中M非飽和頂點，置S=｛u｝,T=Φ;(b)、若N(S)=T,則G中不存在完美匹配。否則
18、設y∈N(S)–T.7(c)若y為M飽和點，且yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(zhuǎn)(b)。否則，設P為M可擴路，置M1=MΔE(P)，轉(zhuǎn)(a).例1討論下圖G=(X,Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X,Y)解：取初始匹配M=｛x1y2,x2y3｝。(a)S=｛x3｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)8(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T(c)y2為M非飽和點，加上y2和邊x3y2生長樹H。此時，置M=MΔE(P)=｛x1y1,x2y3,x3y2｝x1x2x3x4x5y1y2y3y4y5G=
19、(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)9(a)S=｛x4｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T(c)y2為M飽和點，y2x3∈M。此時，置S=S∪｛x3｝T=T∪｛y2｝。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx4y2x310(c)y3為M飽和點，x2y3∈M。此時，置S=S∪｛x2｝T=T∪｛y3｝。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)=｛y2,y3｝=T，所
20、以，G無完美匹配。(5)、匈牙利算法復雜性分析111)、最多循環(huán)
21、X
22、次可以找到完美匹配；2)、初始匹配最多擴張
23、X
24、次可以找到完美匹配；3)、每次生長樹的生長至多2
25、X
26、-1次。所以，算法復雜性為O(
27、X
28、3),是好算法。2、偶圖中尋找最大匹配問題：在一般偶圖上求最大匹配M.分析：使用匈牙利算法求完美匹配時，當在扎根于M非飽和點u的交錯樹上有
29、N(S)
30、<
31、S
32、時，由Hall定理，算法停止。要求出最大匹配，應該繼續(xù)檢查X-S是否為空，如果不為空，則檢查是否在其上有M非飽和點。一直到所有M非飽和點均沒有M可擴路才停止。12偶圖中尋找最大匹配算法：設M是G=(X,Y)的初始匹配。(1)置S=Φ
33、,T=Φ;(2)若X-S已經(jīng)M飽和，停止；否則，設u是X-S中的一非飽和頂點，置S=S∪｛u｝。(3)若N(S)=T,轉(zhuǎn)(5)；否則，設y∈N(S)-T。(4)若y是M飽和的，設yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(zhuǎn)(3);否則，存在(u,y)交錯路是M可擴路P,置M=MΔE(P),轉(zhuǎn)(1).(5)若X-S=Φ,停止；否則轉(zhuǎn)(2).13(二)、最優(yōu)匹配算法1、問題設G=(X,Y)是邊賦權(quán)完全偶圖，且X
