圖論課件匈牙利算法與最優(yōu)匹配算法1第一頁，共三十二頁，編輯于2023年，星期二本次課主要內(nèi)容(一)、匈牙利算法(二)、最優(yōu)匹配算法匈牙利算法與最優(yōu)匹配算法2第二頁，共三十二頁，編輯于2023年，星期二(一)、匈牙利算法

1、偶圖中尋找完美匹配(1)、問題

設(shè)G=(X,Y),|X|=|Y|,在G中求一完美匹配M.(2)、基本思想

從任一初始匹配M0出發(fā)，通過尋求一條M0可擴(kuò)路P，令M1=M0ΔE(P),得比M0更大的匹配M1(近似于迭代思想)。(3)、M可擴(kuò)擴(kuò)路的尋找方法1965年，Edmonds首先提出:用扎根于M非飽和點(diǎn)u的M交錯樹的生長來求M可擴(kuò)路。3第三頁，共三十二頁，編輯于2023年，星期二

定義1設(shè)G=(X,Y),M是G的匹配，u是M非飽和點(diǎn)。稱樹H是G的扎根于點(diǎn)u的M交錯樹,如果：

1)u∈V(T)；2)對任意v∈V(T),(u,v)路是M交錯路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交錯樹扎根于M非飽和點(diǎn)u的M交錯樹的生長討論：4第四頁，共三十二頁，編輯于2023年，星期二

假如扎根于M非飽和點(diǎn)u的M交錯樹為H,對于H,有兩種情形：

情形1除點(diǎn)u外，H中所有點(diǎn)為M飽和點(diǎn)，且在M上配對；x4ux2y4y3y2扎根u

的M交錯樹Hx5

情形2H包含除u外的M非飽和點(diǎn)。x4ux2y4y3y2扎根u

的M交錯樹H5第五頁，共三十二頁，編輯于2023年，星期二

對于情形1，令S=V(H)∩X,T=V(H)∩Y,顯然：

1)若N(S)=T,由于S-｛u｝中點(diǎn)與T中點(diǎn)配對，所以有：

|T|=|S|-1,于是有：|N(S)|=|S|-1<|S|.由Hall定理，G中不存在完美匹配；

2)若

令y∈N(S)–T,且x與y鄰接。因?yàn)镠的所有點(diǎn)，除u外，均在M下配對。所以，或者x=u，或者x與H的某一頂點(diǎn)配對，這樣，有

若y為M飽和的，設(shè)yz∈M,則加上頂點(diǎn)y及z和邊xy與yz生長H，得到情形1；6第六頁，共三十二頁，編輯于2023年，星期二

若y為M非飽和的，加上頂點(diǎn)y和邊xy生長H，得到情形2.

找到一條M可擴(kuò)路，可以對匹配進(jìn)行一次修改，過程的反復(fù)進(jìn)行，最終判定G是否有完美匹配或者求出完美匹配。

根據(jù)上面討論，可以設(shè)計(jì)求偶圖的完美匹配算法。(4)、偶圖完美匹配算法——匈牙利算法。

設(shè)M是初始匹配。(a)、若M飽和X所有頂點(diǎn)，停止。否則，設(shè)u為X中M非飽和頂點(diǎn)，置S=｛u｝,T=Φ;(b)、若N(S)=T,則G中不存在完美匹配。否則設(shè)y∈N(S)–T.7第七頁，共三十二頁，編輯于2023年，星期二(c)若y為M飽和點(diǎn)，且yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(zhuǎn)(b)。否則，設(shè)P為M可擴(kuò)路，置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第八頁，共三十二頁，編輯于2023年，星期二(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T(c)y2為M非飽和點(diǎn)，加上y2和邊x3y2生長樹H。此時，置M=MΔE(P)=｛x1y1,x2y3,x3y2｝x1x2x3x4x5y1y2y3y4y5G=(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)9第九頁，共三十二頁，編輯于2023年，星期二(a)S=｛x4｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T(c)y2為M飽和點(diǎn)，y2x3∈M。此時，置S=S∪｛x3｝T=T∪｛y2｝。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx4y2x310第十頁，共三十二頁，編輯于2023年，星期二(c)y3為M飽和點(diǎn)，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，所以，G無完美匹配。(5)、匈牙利算法復(fù)雜性分析11第十一頁，共三十二頁，編輯于2023年，星期二1)、最多循環(huán)|X|次可以找到完美匹配；2)、初始匹配最多擴(kuò)張|X|次可以找到完美匹配；3)、每次生長樹的生長至多2|X|-1次。

所以，算法復(fù)雜性為O(|X|3),是好算法。

2、偶圖中尋找最大匹配

問題：在一般偶圖上求最大匹配M.

分析：使用匈牙利算法求完美匹配時，當(dāng)在扎根于M非飽和點(diǎn)u的交錯樹上有|N(S)|<|S|時，由Hall定理，算法停止。要求出最大匹配，應(yīng)該繼續(xù)檢查X-S是否為空，如果不為空，則檢查是否在其上有M非飽和點(diǎn)。一直到所有M非飽和點(diǎn)均沒有M可擴(kuò)路才停止。12第十二頁，共三十二頁，編輯于2023年，星期二偶圖中尋找最大匹配算法：

設(shè)M是G=(X,Y)的初始匹配。(1)置S=Φ,T=Φ;(2)若X-S已經(jīng)M飽和，停止；否則，設(shè)u是X-S中的一非飽和頂點(diǎn)，置S=S∪｛u｝。(3)若N(S)=T,轉(zhuǎn)(5)；否則，設(shè)y∈N(S)-T。(4)若y是M飽和的，設(shè)yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(zhuǎn)(3);否則，存在(u,y)交錯路是M可擴(kuò)路P,置M=MΔE(P),轉(zhuǎn)(1).(5)若X-S=Φ,停止；否則轉(zhuǎn)(2).13第十三頁，共三十二頁，編輯于2023年，星期二(二)、最優(yōu)匹配算法1、問題

設(shè)G=(X,Y)是邊賦權(quán)完全偶圖，且X=｛x1,x2,…,xn｝Y=｛y1,y2,…,yn｝,wij=w(xiyj)。在G中求出一個具有最大權(quán)值的完美匹配。

由于Kn,n有n!個不同完美匹配，所以枚舉計(jì)算量是n!。

在匈牙利算法的基礎(chǔ)上，Kuhn（1955）與Munkres(1957)提出了上面問題的好算法。2、可行頂點(diǎn)標(biāo)號與相等子圖14第十四頁，共三十二頁，編輯于2023年，星期二

定義2設(shè)G=(X,Y),若對任意的x∈X,y∈Y,有：

稱l是賦權(quán)完全偶圖G的可行頂點(diǎn)標(biāo)號。

對于任意的賦權(quán)完全偶圖G，均存在G的可行頂點(diǎn)標(biāo)號。事實(shí)上，設(shè)：

則l是G的一個可行頂點(diǎn)標(biāo)號。15第十五頁，共三十二頁，編輯于2023年，星期二

定義3設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行頂點(diǎn)標(biāo)號，令：

稱Gl=G[El]為G的對應(yīng)于l的相等子圖。

例如，設(shè)如下矩陣是賦權(quán)完全偶圖G的權(quán)值矩陣并注明了一種可行頂點(diǎn)標(biāo)號l0000054213x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)16第十六頁，共三十二頁，編輯于2023年，星期二

定理

設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行頂點(diǎn)標(biāo)號，若相等子圖Gl有完美匹配M*,則M*是G的最優(yōu)匹配。

證明：設(shè)M*是Gl的完美匹配，則：

又設(shè)M是G的任一完美匹配，則：

所以，w(M*)≥w(M)。即M*是G的最優(yōu)匹配。17第十七頁，共三十二頁，編輯于2023年，星期二

根據(jù)上面定理，如果找到一種恰當(dāng)可行頂點(diǎn)標(biāo)號，使得對應(yīng)的相等子圖有完美匹配M*,則求出了G的最優(yōu)匹配。Kuhn采用頂點(diǎn)標(biāo)號修改策略，找到了求最優(yōu)匹配好算法，介紹如下：

給一初始頂點(diǎn)標(biāo)號l,在Gl中任選一個匹配M。(1)若X是M飽和的，則M是最優(yōu)匹配。否則，令u是一個M非飽和點(diǎn)，置：S=｛u｝,T=Φ。(2)若，轉(zhuǎn)(3)。否則，計(jì)算：18第十八頁，共三十二頁，編輯于2023年，星期二

給出新的可行頂點(diǎn)標(biāo)號。(3)在NGl(S)-T中選擇點(diǎn)y。若y是M飽和的，yz∈M,則置S=S∪｛z｝,T=T∪｛y｝轉(zhuǎn)(2)。否則，設(shè)P是Gl中M可擴(kuò)路，置M=MΔE(P),轉(zhuǎn)(1).

注：該算法把匈牙利算法用于其中，主要是用來判定和求完美匹配。19第十九頁，共三十二頁，編輯于2023年，星期二

例2，設(shè)如下矩陣是賦權(quán)完全偶圖G的權(quán)值矩陣，求出其最優(yōu)匹配。

解：給出初始可行頂點(diǎn)標(biāo)號l為：000005421320第二十頁，共三十二頁，編輯于2023年，星期二

對應(yīng)的相等子圖Gl為：給出初始匹配M為：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)21第二十一頁，共三十二頁，編輯于2023年，星期二

(1)u=x4為M非飽和頂點(diǎn)。置：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)

(2)

(3)取：

y2為飽和頂點(diǎn)，y2x1

∈M,于是：

(2)

(3)取：

y3為飽和頂點(diǎn)，y3x3

∈M,于是：22第二十二頁，共三十二頁，編輯于2023年，星期二x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)

(2)于是修改標(biāo)號：由得新標(biāo)號為：0110043203x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)23第二十三頁，共三十二頁，編輯于2023年，星期二

繼續(xù)使用算法后得：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)

最優(yōu)匹配權(quán)值為14.

例3證明：K6n-2有一個3因子分解。證明：K6n-2=K2(3n-1),所以，可以分解為6n-3個邊不重的1因子之和。而任意3個1因子可以并成一個3因子。所以，共可以并成2n-1個3因子。即K6n-2可以分解為2n-1個3因子的和。24第二十四頁，共三十二頁，編輯于2023年，星期二

例4證明：對n≥1,K4n+1有一個4因子分解。證明：K4n+1=K2(2n)+1,所以，可以分解為2n個邊不重的2因子之和。而任意2個2因子可以并成一個4因子。所以，共可以并成n個4因子。即K4n+1可以分解為n個4因子的和。

例5設(shè)H是有限群，K是H的子群。證明：存在元素h1,h2,…,hn

∈H,使得h1K,h2K,…,hnK都是K的左陪集。而Kh1,Kh2,…,Khn都是K的右陪集。注:(1)上面結(jié)論是群論學(xué)家Hall的一個結(jié)論。群論是近世代數(shù)的重要組成部分。在數(shù)學(xué)、計(jì)算機(jī)科學(xué)、理論物理學(xué)(量子場論)中都有重要應(yīng)用。是數(shù)學(xué)領(lǐng)域里最引人關(guān)注的方向和主流研究方向之一。創(chuàng)立者伽羅瓦。25第二十五頁，共三十二頁，編輯于2023年，星期二

(2)伽羅瓦(1811---1832)中學(xué)時受到數(shù)學(xué)老師里沙的影響而對數(shù)學(xué)產(chǎn)生極大興趣。里沙對教學(xué)工作十分負(fù)責(zé)，且具有很高數(shù)學(xué)才能，但把精力耗在了學(xué)生身上，欣慰的是培養(yǎng)了好幾位歐洲杰出數(shù)學(xué)家。中學(xué)時的伽羅瓦

在里沙幫助下創(chuàng)立了群論。群論是19世紀(jì)最突出的數(shù)學(xué)成就。有點(diǎn)象相對論在物理學(xué)中的地位。

在法國歷史上著名的1830年的“七月革命”中，伽羅瓦兩次入獄，成為堅(jiān)強(qiáng)斗士。1832年5月，21歲的他因?yàn)榉磩优稍O(shè)下的愛情圈套，被迫決斗至死。這是他犯下的草率的錯誤。26第二十六頁，共三十二頁，編輯于2023年，星期二證明：由陪集的性質(zhì)：H中的任意兩個左(右)陪集,要么相等，要么沒有共同元素。所以H可按某子群的左(右)陪集，劃分為左(右)陪集族。如果K是H的子群，則aK或者Kb的元素個數(shù)等于K中元素個數(shù)。

設(shè)|K|=k。且假設(shè)子群K在群H中的指數(shù)為n。我們構(gòu)造偶圖G=(X,Y)如下：

X表示H關(guān)于K的左陪集族，Y表示H關(guān)于K的右陪集族。對于x∈