圖論課件匈牙利算法與最優(yōu)匹配算法

本次課主要內(nèi)容(一)、匈牙利算法(二)、最優(yōu)匹配算法匈牙利算法與最優(yōu)匹配算法1本次課主要內(nèi)容(一)、匈牙利算法(二)、最優(yōu)匹配算法匈牙利算(一)、匈牙利算法

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

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

從任一初始匹配M0出發(fā)，通過尋求一條M0可擴路P，令M1=M0ΔE(P),得比M0更大的匹配M1(近似于迭代思想)。(3)、M可擴擴路的尋找方法1965年，Edmonds首先提出:用扎根于M非飽和點u的M交錯樹的生長來求M可擴路。2(一)、匈牙利算法1、偶圖中尋找完美匹配

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

1)u∈V(T)；2)對任意v∈V(T),(u,v)路是M交錯路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交錯樹扎根于M非飽和點u的M交錯樹的生長討論：3定義1設G=(X,Y),M是G的匹配，u是M非

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

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

的M交錯樹Hx5

情形2H包含除u外的M非飽和點。x4ux2y4y3y2扎根u

的M交錯樹H4假如扎根于M非飽和點u的M交錯樹為H,對于H,有兩種

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

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

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

2)若

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

若y為M飽和的，設yz∈M,則加上頂點y及z和邊xy與yz生長H，得到情形1；5對于情形1，令S=V(H)∩X,T=V(H)∩

若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中不存在完美匹配。否則設y∈N(S)–T.6若y為M非飽和的，加上頂點y和邊xy生長H，得到情形(c)若y為M飽和點，且yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(b)。否則，設P為M可擴路，置M1=MΔE(P)，轉(a).

例1討論下圖G=(X,Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X,Y)

解：取初始匹配M=｛x1y2,x2y3｝。(a)S=｛x3｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)7(c)若y為M飽和點，且yz∈M,置S=S(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=(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)8(b)N(S)=｛y2,y3｝,N(S)≠(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)-Tx4y2x39(a)S=｛x4｝,T=Φ;x1x2x3x4x5(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，所以，G無完美匹配。(5)、匈牙利算法復雜性分析10(c)y3為M飽和點，x2y3∈M。此時，置1)、最多循環(huán)|X|次可以找到完美匹配；2)、初始匹配最多擴張|X|次可以找到完美匹配；3)、每次生長樹的生長至多2|X|-1次。

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

2、偶圖中尋找最大匹配

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

分析：使用匈牙利算法求完美匹配時，當在扎根于M非飽和點u的交錯樹上有|N(S)|<|S|時，由Hall定理，算法停止。要求出最大匹配，應該繼續(xù)檢查X-S是否為空，如果不為空，則檢查是否在其上有M非飽和點。一直到所有M非飽和點均沒有M可擴路才停止。111)、最多循環(huán)|X|次可以找到完美匹配；偶圖中尋找最大匹配算法：

設M是G=(X,Y)的初始匹配。(1)置S=Φ,T=Φ;(2)若X-S已經(jīng)M飽和，停止；否則，設u是X-S中的一非飽和頂點，置S=S∪｛u｝。(3)若N(S)=T,轉(5)；否則，設y∈N(S)-T。(4)若y是M飽和的，設yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(3);否則，存在(u,y)交錯路是M可擴路P,置M=MΔE(P),轉(1).(5)若X-S=Φ,停止；否則轉(2).12偶圖中尋找最大匹配算法：設M是G=(X,(二)、最優(yōu)匹配算法1、問題

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

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

在匈牙利算法的基礎上，Kuhn（1955）與Munkres(1957)提出了上面問題的好算法。2、可行頂點標號與相等子圖13(二)、最優(yōu)匹配算法1、問題設G=(X

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

稱l是賦權完全偶圖G的可行頂點標號。

對于任意的賦權完全偶圖G，均存在G的可行頂點標號。事實上，設：

則l是G的一個可行頂點標號。14定義2設G=(X,Y),若對任意的x∈X,

定義3設l是賦權完全偶圖G=(X,Y的可行頂點標號，令：

稱Gl=G[El]為G的對應于l的相等子圖。

例如，設如下矩陣是賦權完全偶圖G的權值矩陣并注明了一種可行頂點標號l0000054213x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)15定義3設l是賦權完全偶圖G=(X,Y的可行

定理設l是賦權完全偶圖G=(X,Y的可行頂點標號，若相等子圖Gl有完美匹配M*,則M*是G的最優(yōu)匹配。

證明：設M*是Gl的完美匹配，則：

又設M是G的任一完美匹配，則：

所以，w(M*)≥w(M)。即M*是G的最優(yōu)匹配。16定理設l是賦權完全偶圖G=(X,Y的可行頂

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

給一初始頂點標號l,在Gl中任選一個匹配M。(1)若X是M飽和的，則M是最優(yōu)匹配。否則，令u是一個M非飽和點，置：S=｛u｝,T=Φ。(2)若，轉(3)。否則，計算：17根據(jù)上面定理，如果找到一種恰當可行頂點標號，使得對

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

注：該算法把匈牙利算法用于其中，主要是用來判定和求完美匹配。18給出新的可行頂點標號。(3)在NGl

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

解：給出初始可行頂點標號l為：000005421319例2，設如下矩陣是賦權完全偶圖G的權值矩陣，求出其

對應的相等子圖Gl為：給出初始匹配M為：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)20對應的相等子圖Gl為：給出初始匹配M為：(1)u=x4為M非飽和頂點。置：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)(3)?。簓2為飽和頂點，y2x1

∈M,于是：(2)(3)?。簓3為飽和頂點，y3x3

∈M,于是：21(1)u=x4為M非飽和頂點。置：x1x2x3x4x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)于是修改標號：由得新標號為：0110043203x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)22x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)

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

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

例3證明：K6n-2有一個3因子分解。證明：K6n-2=K2(3n-1),所以，可以分解為6n-3個邊不重的1因子之和。而任意3個1因子可以并成一個3因子。所以，共可以并成2n-1個3因子。即K6n-2可以分解為2n-1個3因子的和。23繼續(xù)使用算法后得：x1x2x3x4x5y1y2y3

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

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

∈H,使得h1K,h2K,…,hnK都是K的左陪集。而Kh1,Kh2,…,Khn都是K的右陪集。注:(1)上面結論是群論學家Hall的一個結論。群論是近世代數(shù)的重要組成部分。在數(shù)學、計算機科學、理論物理學(量子場論)中都有重要應用。是數(shù)學領域里最引人關注的方向和主流研究方向之一。創(chuàng)立者伽羅瓦。24例4證明：對n≥1,K4n+1有一個4因子分解。

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

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

在法國歷史上著名的1830年的“七月革命”中，伽羅瓦兩次入獄，成為堅強斗士。1832年5月，21歲的他因為反動派設下的愛情圈套，被迫決斗至死。這是他犯下的草率的錯誤。25(2)伽羅瓦(1811---1832)中學證明：由陪集的性質(zhì)：H中的任意兩個左(右)陪集,要么相等，要么沒有共同元素。所以H可按某子群的左(右)陪集，劃分為左(右)陪集族。如果K是H的子群，則aK或者Kb的元素個數(shù)等于K中元素個數(shù)。

設|K|=k。且假設子群K在群H中的指數(shù)為n。我們構造偶圖G=(X,Y)如下：X表示H關于K的左陪集族，Y表示H關于K的右陪集族。對于x∈X,y∈Y,x與y間連接l條邊，當且僅當左陪集x和右陪集y有l(wèi)個共同元素。顯然G是k正則偶圖，于是存在完美匹配M。|M|=n在M中的邊ei的兩端點的陪集中選取共同元素hi,則這些元素為所求。(1≦i≦n）。26證明：由陪集的性質(zhì)：H中的任意兩個左(右)陪集,要

匹配在矩陣中的應用

1、矩陣與偶圖設A=(aij)是n階方陣。構造偶圖G=(X,Y)如下：X表示行集合，Y表示列集合。X中元素xi與Y中元素yj連線，當且僅當aij≠0y1y2y3y4y5x1x3x2x4x5x1x2x3x4x5y1y2y3y4y5Gw=(X,Y)27匹配在矩陣中的應用1、矩陣與偶圖

2、下面研究detA和GA=(X,Y)之間關系若|S|=n,則在A中存在n行，這n行中至多有n-1列元非零，而其余的ν-n+1列中每個元素為零。即得到A中有一個零子陣。282、下面研究detA和GA=(X,Y)之

于是有如下定理：29于是有如下定理：29

作業(yè)

P117---118習題4：1330作業(yè)P117---118習題4：1330ThankYou!31ThankYou!31本次課主要內(nèi)容(一)、匈牙利算法(二)、最優(yōu)匹配算法匈牙利算法與最優(yōu)匹配算法32本次課主要內(nèi)容(一)、匈牙利算法(二)、最優(yōu)匹配算法匈牙利算(一)、匈牙利算法

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

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

從任一初始匹配M0出發(fā)，通過尋求一條M0可擴路P，令M1=M0ΔE(P),得比M0更大的匹配M1(近似于迭代思想)。(3)、M可擴擴路的尋找方法1965年，Edmonds首先提出:用扎根于M非飽和點u的M交錯樹的生長來求M可擴路。33(一)、匈牙利算法1、偶圖中尋找完美匹配

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

1)u∈V(T)；2)對任意v∈V(T),(u,v)路是M交錯路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交錯樹扎根于M非飽和點u的M交錯樹的生長討論：34定義1設G=(X,Y),M是G的匹配，u是M非

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

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

的M交錯樹Hx5

情形2H包含除u外的M非飽和點。x4ux2y4y3y2扎根u

的M交錯樹H35假如扎根于M非飽和點u的M交錯樹為H,對于H,有兩種

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

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

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

2)若

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

若y為M飽和的，設yz∈M,則加上頂點y及z和邊xy與yz生長H，得到情形1；36對于情形1，令S=V(H)∩X,T=V(H)∩

若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中不存在完美匹配。否則設y∈N(S)–T.37若y為M非飽和的，加上頂點y和邊xy生長H，得到情形(c)若y為M飽和點，且yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(b)。否則，設P為M可擴路，置M1=MΔE(P)，轉(a).

例1討論下圖G=(X,Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X,Y)

解：取初始匹配M=｛x1y2,x2y3｝。(a)S=｛x3｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)38(c)若y為M飽和點，且yz∈M,置S=S(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=(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)39(b)N(S)=｛y2,y3｝,N(S)≠(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)-Tx4y2x340(a)S=｛x4｝,T=Φ;x1x2x3x4x5(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，所以，G無完美匹配。(5)、匈牙利算法復雜性分析41(c)y3為M飽和點，x2y3∈M。此時，置1)、最多循環(huán)|X|次可以找到完美匹配；2)、初始匹配最多擴張|X|次可以找到完美匹配；3)、每次生長樹的生長至多2|X|-1次。

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

2、偶圖中尋找最大匹配

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

分析：使用匈牙利算法求完美匹配時，當在扎根于M非飽和點u的交錯樹上有|N(S)|<|S|時，由Hall定理，算法停止。要求出最大匹配，應該繼續(xù)檢查X-S是否為空，如果不為空，則檢查是否在其上有M非飽和點。一直到所有M非飽和點均沒有M可擴路才停止。421)、最多循環(huán)|X|次可以找到完美匹配；偶圖中尋找最大匹配算法：

設M是G=(X,Y)的初始匹配。(1)置S=Φ,T=Φ;(2)若X-S已經(jīng)M飽和，停止；否則，設u是X-S中的一非飽和頂點，置S=S∪｛u｝。(3)若N(S)=T,轉(5)；否則，設y∈N(S)-T。(4)若y是M飽和的，設yz∈M,置S=S∪｛z｝,T=T∪｛y｝,轉(3);否則，存在(u,y)交錯路是M可擴路P,置M=MΔE(P),轉(1).(5)若X-S=Φ,停止；否則轉(2).43偶圖中尋找最大匹配算法：設M是G=(X,(二)、最優(yōu)匹配算法1、問題

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

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

在匈牙利算法的基礎上，Kuhn（1955）與Munkres(1957)提出了上面問題的好算法。2、可行頂點標號與相等子圖44(二)、最優(yōu)匹配算法1、問題設G=(X

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

稱l是賦權完全偶圖G的可行頂點標號。

對于任意的賦權完全偶圖G，均存在G的可行頂點標號。事實上，設：

則l是G的一個可行頂點標號。45定義2設G=(X,Y),若對任意的x∈X,

定義3設l是賦權完全偶圖G=(X,Y的可行頂點標號，令：

稱Gl=G[El]為G的對應于l的相等子圖。

例如，設如下矩陣是賦權完全偶圖G的權值矩陣并注明了一種可行頂點標號l0000054213x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)46定義3設l是賦權完全偶圖G=(X,Y的可行

定理設l是賦權完全偶圖G=(X,Y的可行頂點標號，若相等子圖Gl有完美匹配M*,則M*是G的最優(yōu)匹配。

證明：設M*是Gl的完美匹配，則：

又設M是G的任一完美匹配，則：

所以，w(M*)≥w(M)。即M*是G的最優(yōu)匹配。47定理設l是賦權完全偶圖G=(X,Y的可行頂

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

給一初始頂點標號l,在Gl中任選一個匹配M。(1)若X是M飽和的，則M是最優(yōu)匹配。否則，令u是一個M非飽和點，置：S=｛u｝,T=Φ。(2)若，轉(3)。否則，計算：48根據(jù)上面定理，如果找到一種恰當可行頂點標號，使得對

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

注：該算法把匈牙利算法用于其中，主要是用來判定和求完美匹配。49給出新的可行頂點標號。(3)在NGl

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

解：給出初始可行頂點標號l為：000005421350例2，設如下矩陣是賦權完全偶圖G的權值矩陣，求出其

對應的相等子圖Gl為：給出初始匹配M為：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)51對應的相等子圖Gl為：給出初始匹配M為：(1)u=x4為M非飽和頂點。置：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)(3)?。簓2為飽和頂點，y2x1

∈M,于是：(2)(3)?。簓3為飽和頂點，y3x3

∈M,于是：52(1)u=x4為M非飽和頂點。置：x1x2x3x4x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)于是修改標號：由得新標號為：0110043203x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)53x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)

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

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

例3證明：K6n-2有一個3因子分解。證明：K6n-2=K2(3n-1),所以，可以分解為6n-3個邊不重的1因子之和。而任意3個1因子可以并成一個3因子。所以，共可以并成2n-1個3因子。即K6n-2可以分解為2n-1個3因子的和。54繼續(xù)使用算法后得：x1x2x3x4x5y1y2y3

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

例5設H是有限群，K是H的子群。證明：存在元素h