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

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

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

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

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

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

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

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

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

的M交錯(cuò)樹Hx5

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

的M交錯(cuò)樹H4假如扎根于M非飽和點(diǎn)u的M交錯(cuò)樹為H,對(duì)于H,有兩種

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

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

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

2)若

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

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

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

找到一條M可擴(kuò)路，可以對(duì)匹配進(jìn)行一次修改，過(guò)程的反復(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.6若y為M非飽和的，加上頂點(diǎn)y和邊xy生長(zhǎng)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生長(zhǎng)樹H。此時(shí)，置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。此時(shí)，置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。此時(shí)，置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無(wú)完美匹配。(5)、匈牙利算法復(fù)雜性分析10(c)y3為M飽和點(diǎn)，x2y3∈M。此時(shí)，置1)、最多循環(huán)|X|次可以找到完美匹配；2)、初始匹配最多擴(kuò)張|X|次可以找到完美匹配；3)、每次生長(zhǎng)樹的生長(zhǎng)至多2|X|-1次。

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

2、偶圖中尋找最大匹配

問(wèn)題：在一般偶圖上求最大匹配M.

分析：使用匈牙利算法求完美匹配時(shí)，當(dāng)在扎根于M非飽和點(diǎn)u的交錯(cuò)樹上有|N(S)|<|S|時(shí)，由Hall定理，算法停止。要求出最大匹配，應(yīng)該繼續(xù)檢查X-S是否為空，如果不為空，則檢查是否在其上有M非飽和點(diǎn)。一直到所有M非飽和點(diǎn)均沒(méi)有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)交錯(cuò)路是M可擴(kuò)路P,置M=MΔE(P),轉(zhuǎn)(1).(5)若X-S=Φ,停止；否則轉(zhuǎn)(2).12偶圖中尋找最大匹配算法：設(shè)M是G=(X,(二)、最優(yōu)匹配算法1、問(wèn)題

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

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

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

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

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

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

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

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

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

例如，設(shè)如下矩陣是賦權(quán)完全偶圖G的權(quán)值矩陣并注明了一種可行頂點(diǎn)標(biāo)號(hào)l0000054213x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)15定義3設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行

定理設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行頂點(diǎn)標(biāo)號(hà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)號(hào)，使得對(duì)應(yīng)的相等子圖有完美匹配M*,則求出了G的最優(yōu)匹配。Kuhn采用頂點(diǎn)標(biāo)號(hào)修改策略，找到了求最優(yōu)匹配好算法，介紹如下：

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

給出新的可行頂點(diǎn)標(biāo)號(hà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).

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

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

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

對(duì)應(yīng)的相等子圖Gl為：給出初始匹配M為：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)20對(duì)應(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,于是：21(1)u=x4為M非飽和頂點(diǎn)。置：x1x2x3x4x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)于是修改標(biāo)號(hào)：由得新標(biāo)號(hào)為：0110043203x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)22x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)

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

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

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

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

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

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

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

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

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

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

匹配在矩陣中的應(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列中每個(gè)元素為零。即得到A中有一個(gè)零子陣。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)、問(wèn)題

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

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

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

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

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

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

的M交錯(cuò)樹Hx5

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

的M交錯(cuò)樹H35假如扎根于M非飽和點(diǎn)u的M交錯(cuò)樹為H,對(duì)于H,有兩種

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

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

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

2)若

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

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

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

找到一條M可擴(kuò)路，可以對(duì)匹配進(jìn)行一次修改，過(guò)程的反復(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.37若y為M非飽和的，加上頂點(diǎn)y和邊xy生長(zhǎng)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生長(zhǎng)樹H。此時(shí)，置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。此時(shí)，置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。此時(shí)，置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無(wú)完美匹配。(5)、匈牙利算法復(fù)雜性分析41(c)y3為M飽和點(diǎn)，x2y3∈M。此時(shí)，置1)、最多循環(huán)|X|次可以找到完美匹配；2)、初始匹配最多擴(kuò)張|X|次可以找到完美匹配；3)、每次生長(zhǎng)樹的生長(zhǎng)至多2|X|-1次。

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

2、偶圖中尋找最大匹配

問(wèn)題：在一般偶圖上求最大匹配M.

分析：使用匈牙利算法求完美匹配時(shí)，當(dāng)在扎根于M非飽和點(diǎn)u的交錯(cuò)樹上有|N(S)|<|S|時(shí)，由Hall定理，算法停止。要求出最大匹配，應(yīng)該繼續(xù)檢查X-S是否為空，如果不為空，則檢查是否在其上有M非飽和點(diǎn)。一直到所有M非飽和點(diǎn)均沒(méi)有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)交錯(cuò)路是M可擴(kuò)路P,置M=MΔE(P),轉(zhuǎn)(1).(5)若X-S=Φ,停止；否則轉(zhuǎn)(2).43偶圖中尋找最大匹配算法：設(shè)M是G=(X,(二)、最優(yōu)匹配算法1、問(wèn)題

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

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

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

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

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

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

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

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

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

例如，設(shè)如下矩陣是賦權(quán)完全偶圖G的權(quán)值矩陣并注明了一種可行頂點(diǎn)標(biāo)號(hào)l0000054213x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)46定義3設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行

定理設(shè)l是賦權(quán)完全偶圖G=(X,Y的可行頂點(diǎn)標(biāo)號(hà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)號(hào)，使得對(duì)應(yīng)的相等子圖有完美匹配M*,則求出了G的最優(yōu)匹配。Kuhn采用頂點(diǎn)標(biāo)號(hào)修改策略，找到了求最優(yōu)匹配好算法，介紹如下：

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

給出新的可行頂點(diǎn)標(biāo)號(hà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).

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

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

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

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

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

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

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

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

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

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

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