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

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

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ò)路。2(一)、匈牙利算法1、偶圖中尋找完美匹配

定義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交錯樹的生長討論：3定義1設(shè)G=(X,Y),M是G的匹配，u是M非

假如扎根于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交錯樹H4假如扎根于M非飽和點(diǎn)u的M交錯樹為H,對于H,有兩種

對于情形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鄰接。因為H的所有點(diǎn)，除u外，均在M下配對。所以，或者x=u，或者x與H的某一頂點(diǎn)配對，這樣，有

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

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

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

根據(jù)上面討論，可以設(shè)計求偶圖的完美匹配算法。(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.6若y為M非飽和的，加上頂點(diǎn)y和邊xy生長H，得到情形(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)7(c)若y為M飽和點(diǎn)，且yz∈M,置S=S(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)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飽和點(diǎn)，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飽和點(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ù)雜性分析10(c)y3為M飽和點(diǎn)，x2y3∈M。此時，置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ò)路才停止。111)、最多循環(huán)|X|次可以找到完美匹配；偶圖中尋找最大匹配算法：

設(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).12偶圖中尋找最大匹配算法：設(shè)M是G=(X,(二)、最優(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!個不同完美匹配，所以枚舉計算量是n!。

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

定義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è)：

則l是G的一個可行頂點(diǎn)標(biāo)號。14定義2設(shè)G=(X,Y),若對任意的x∈X,

定義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)15定義3設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行

定理設(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)匹配。16定理設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行頂

根據(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)。否則，計算：17根據(jù)上面定理，如果找到一種恰當(dāng)可行頂點(diǎn)標(biāo)號，使得對

給出新的可行頂點(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).

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

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

解：給出初始可行頂點(diǎn)標(biāo)號l為：000005421319例2，設(shè)如下矩陣是賦權(quán)完全偶圖G的權(quán)值矩陣，求出其

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

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

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

繼續(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因子的和。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設(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ī)科學(xué)、理論物理學(xué)(量子場論)中都有重要應(yīng)用。是數(shù)學(xué)領(lǐng)域里最引人關(guān)注的方向和主流研究方向之一。創(chuàng)立者伽羅瓦。24例4證明：對n≥1,K4n+1有一個4因子分解。

(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年的“七月革命”中，伽羅瓦兩次入獄，成為堅強(qiáng)斗士。1832年5月，21歲的他因為反動派設(shè)下的愛情圈套，被迫決斗至死。這是他犯下的草率的錯誤。25(2)伽羅瓦(1811---1832)中學(xué)證明：由陪集的性質(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∈X,y∈Y,x與y間連接l條邊，當(dāng)且僅當(dāng)左陪集x和右陪集y有l(wèi)個共同元素。顯然G是k正則偶圖，于是存在完美匹配M。|M|=n在M中的邊ei的兩端點(diǎn)的陪集中選取共同元素hi,則這些元素為所求。(1≦i≦n）。26證明：由陪集的性質(zhì)：H中的任意兩個左(右)陪集,要

匹配在矩陣中的應(yīng)用

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

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

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

作業(yè)

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

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ò)路。33(一)、匈牙利算法1、偶圖中尋找完美匹配

定義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交錯樹的生長討論：34定義1設(shè)G=(X,Y),M是G的匹配，u是M非

假如扎根于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交錯樹H35假如扎根于M非飽和點(diǎn)u的M交錯樹為H,對于H,有兩種

對于情形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鄰接。因為H的所有點(diǎn)，除u外，均在M下配對。所以，或者x=u，或者x與H的某一頂點(diǎn)配對，這樣，有

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

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

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

根據(jù)上面討論，可以設(shè)計求偶圖的完美匹配算法。(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.37若y為M非飽和的，加上頂點(diǎn)y和邊xy生長H，得到情形(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)38(c)若y為M飽和點(diǎn)，且yz∈M,置S=S(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)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飽和點(diǎn)，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飽和點(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ù)雜性分析41(c)y3為M飽和點(diǎn)，x2y3∈M。此時，置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ò)路才停止。421)、最多循環(huán)|X|次可以找到完美匹配；偶圖中尋找最大匹配算法：

設(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).43偶圖中尋找最大匹配算法：設(shè)M是G=(X,(二)、最優(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!個不同完美匹配，所以枚舉計算量是n!。

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

定義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è)：

則l是G的一個可行頂點(diǎn)標(biāo)號。45定義2設(shè)G=(X,Y),若對任意的x∈X,

定義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)46定義3設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行

定理設(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)匹配。47定理設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行頂

根據(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)。否則，計算：48根據(jù)上面定理，如果找到一種恰當(dāng)可行頂點(diǎn)標(biāo)號，使得對

給出新的可行頂點(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).

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

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

解：給出初始可行頂點(diǎn)標(biāo)號l為：000005421350例2，設(shè)如下矩陣是賦權(quán)完全偶圖G的權(quán)值矩陣，求出其

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

∈M,于是：(2)(3)取：y3為飽和頂點(diǎn)，y3x3

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

繼續(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因子的和。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設(shè)H是有限群，K是H的子群。證明：存在元素h