圖論-第5章課件

第五章匹配與因子分解.第五章匹配與因子分解.1§5.1匹配

定義設(shè)M是圖G的一個(gè)不包含環(huán)的邊子集，且M中任意兩條邊在G中

均互不相鄰，則稱M為

G的一個(gè)匹配（對(duì)集）。M中一條邊的兩個(gè)端點(diǎn)稱為在M下是配對(duì)的。設(shè)M為

G的一個(gè)匹配，對(duì)v∈V(G)，若v是M中某邊的一個(gè)端點(diǎn)，則稱v為M飽和點(diǎn)，否則稱為M非飽和點(diǎn)。若圖G中的點(diǎn)均為M飽和點(diǎn)，則稱M為G的完美匹配。若G中沒有另外的匹配M’，使得|M|<|M’|,則稱M為G的最大匹配（含邊數(shù)最多的匹配）。

1、圖的匹配相關(guān)概念.2§5.1匹配定義設(shè)M是圖G的一個(gè)不包對(duì)M2，點(diǎn)v1是飽和點(diǎn)，點(diǎn)v2是非飽和點(diǎn)。v1v2v3v4v8v5v7v6

例1中的M1

和M2既不是最大匹配，也不是完美匹配，而M3是最大匹配，也是完美匹配。例1設(shè)圖G為:G的匹配有：M1={v1v8}M2={v1v3，v8v4，v7v5}M3={v1v2，v8v3，v7v4，v6v5}等等.3對(duì)M2，點(diǎn)v1是飽和點(diǎn)，點(diǎn)v2是非飽和點(diǎn)。v1v2v3v4

關(guān)系：

(1)

完美匹配必是最大匹配，而最大匹配不一定是完美匹配。(2)

一個(gè)圖的最大匹配必存在，但完美匹配不一定存在。(3)

圖G存在完美匹配的一個(gè)必要條件是G的點(diǎn)數(shù)為偶。G的一個(gè)最大匹配G的一個(gè)完美匹配.4關(guān)系：(2)一個(gè)圖的最大匹配必存在，但完美匹配不一定

設(shè)M為圖G的一個(gè)匹配可看出：對(duì)Г3，若取Г3中非M的邊再連同

M的不在Г3中的邊組成M’，則M’的邊數(shù)比

M的邊數(shù)多，這表明

M不是該圖的最大匹配。M交錯(cuò)路：G中由M中的邊與非M中的邊交替組成的路。M可擴(kuò)路：起點(diǎn)與終點(diǎn)均為M非飽和點(diǎn)的M交錯(cuò)路。例如，取M={紅邊}Г1Г2Г3M交錯(cuò)路M可擴(kuò)路.5設(shè)M為圖G的一個(gè)匹配可看出：對(duì)Г3，若取Г3中非M定理1（Berge,1957）

G的匹配M是最大匹配當(dāng)且僅當(dāng)

G不含M可擴(kuò)路.（等價(jià)于：M不是最大匹配當(dāng)且僅當(dāng)G含M可擴(kuò)路）證明：證明其等價(jià)結(jié)論。則M′是G的匹配，且|M′|=|M|+1，因而M就不是最大匹配。

2、貝爾熱定理充分性：設(shè)M是G的匹配，并假設(shè)G包含M可擴(kuò)充路

v0v1…v2m+1,定義M′

E為M′=(M\{v1v2,v3v4,…,v2m-1v2m})∪{v0v1,v2v3,…,v2mv2m+1}.6定理1（Berge,1957）G的匹配M是最大匹配H的每個(gè)頂點(diǎn)在H中具有的度是1或2。因?yàn)樗疃嘀荒芎蚆的一條邊以及M′的一條邊相關(guān)聯(lián)，由（1）式，M′包含的邊多于M的邊，因而H中必定有的一條路P,其邊始于M′且終止于M′，因此P的起點(diǎn)和終點(diǎn)在H中被M′所飽和，在圖G中就是M非飽和的。于是P是G的一條M可擴(kuò)路。

必要性：假設(shè)M不是最大匹配，且令M′是G的最大匹配，則

|M′|>|M|(1)置H=G[M△M′]，這里M△M′表示M和M′的對(duì)稱差。因此H的每個(gè)分支或是由M和M′中的邊交錯(cuò)組成的偶圈，或是由M和M′中的邊交錯(cuò)組成的路。取M={紅邊},M′={白邊}H中可能包含的子圖：.7H的每個(gè)頂點(diǎn)在H中具有的度是1或2。因?yàn)樗疃嘀荒芎蚆的一

貝爾熱(1926---2002)法國著名數(shù)學(xué)家。他的《無限圖理論及其應(yīng)用》(1958)是繼哥尼之后的圖論歷史上的第二本圖論專著。他不僅在圖論領(lǐng)域做出了許多貢獻(xiàn)，而且四處奔波傳播圖論，推動(dòng)了圖論的普及和發(fā)展。1993年，他獲得組合與圖論領(lǐng)域頒發(fā)的歐拉獎(jiǎng)?wù)?。貝爾熱在博弈論、拓?fù)鋵W(xué)領(lǐng)域里也有杰出貢獻(xiàn)。在博弈領(lǐng)域，他引入了Nash均衡之外的另一種均衡系統(tǒng)。Nash的生活被改編成電影《美麗的心靈》，獲02年奧斯卡金像獎(jiǎng)。貝爾熱對(duì)中國的手工藝很感興趣。他也是一位象棋高手，還創(chuàng)作過小說《誰殺害了Densmore公爵》。.8貝爾熱(1926---2002)法國著名數(shù)學(xué)家。他§5.2偶圖的匹配與覆蓋例：現(xiàn)有三個(gè)課外小組：物理組，化學(xué)組和生物組，有五個(gè)學(xué)生s1,s2,s3,s4,s5。已知s1,s2為物理組成員；s1,s3,s4為化學(xué)組成員；s3,s4,s5為生物組成員。問：在s1,s2,s3,s4,s5中選三位組長，不兼職，能否辦到？1、問題的引出解：用c1,c2,c3分別表示物理組、化學(xué)組和生物組。令V1={c1,c2,c3}， V2={s1,s2,s3,s4,s5}以V1，V2為互補(bǔ)結(jié)點(diǎn)子集，以E={(ci,sj)|ci∈V1,sj∈V2且ci中有成員sj}為邊集，構(gòu)造圖。c1c2c3s1s2s3s4s5V1V2.9§5.2偶圖的匹配與覆蓋例：現(xiàn)有三個(gè)課外小組：物理組取圖G的一個(gè)頂點(diǎn)子集S，令

N(S)={v|存在u∈S，且v與u相鄰}稱N(S)為S的鄰集。取S={v1,v2}，v1v2v3v4v8v5v7v6例如圖中2、Hall定理（相異性條件）則N(S)={v8,v3,v1,v2}.10取圖G的一個(gè)頂點(diǎn)子集S，令取S={v1,v2}，定理2（Hall，1935）設(shè)G為具有二分類（X,Y）的偶圖，則G包含飽和X的每個(gè)頂點(diǎn)的匹配當(dāng)且僅當(dāng)

|N(S)|≥|S|

（2.1）對(duì)所有S

X

成立.證明

必要性：已知G包含匹配M，它飽和X的每個(gè)頂點(diǎn)。充分性：已知G是滿足（2.1）式的偶圖，假設(shè)M*是G的最大匹配，且M*不飽和X的所有頂點(diǎn)。設(shè)u是X的一個(gè)M*非飽和點(diǎn)，并設(shè)Z={v|v∈V(G)，且v通過M*交錯(cuò)路與u連接}設(shè)S是X的子集。由于S的頂點(diǎn)在M下和N(S)中的相異頂點(diǎn)配對(duì)，顯然有|N(S)|≥|S|

。x1x2x3y1y2y3y4y5XY.11定理2（Hall，1935）設(shè)G為具有二分類（X,Y）的置S=Z∩X和

T=Z∩Y（見圖）由于M*是最大匹配，從上節(jié)定理1可知：u為Z中唯一的M*非飽和點(diǎn)(否則將含M*可擴(kuò)路)

。且任意一對(duì)配對(duì)點(diǎn)v和w,若v∈S,則必w∈T,反之亦然.因此SuT

|T|=|S|-1

（2.2）又因N(S)中每個(gè)頂點(diǎn)v均由一個(gè)M*交錯(cuò)路連接于u，故v∈Z,從而v∈T,這表明N(S)

T,于是有T=N(S)

(2.3)

Z={v|v∈V，且v通過M*交錯(cuò)路與u連接}

想推出|N(S)|<|S|

例：vv1v2…vmu,其中u為非飽和點(diǎn)而且

T

N(S)

。vx2v1x3考慮：

P=vv1v2…vmu，vm∈T，uvm不在M*中若v

∈S，P為M*交錯(cuò)路，則：

下證N(S)

Tvv1一定在M*中.12置S=Z∩X和由于M*是最大匹配，從上由（2.2）式和（2.3）式推出|N(S)|=|T|=|S|-1<|S|

這與假定（2.1）式矛盾。所以M*飽和X的所有頂點(diǎn).推論

若G是k正則偶圖（k>0），則G有完美匹配。證明設(shè)G是具有二分類（X,Y）的k正則偶圖(k>0)。首先有|X|=|Y|(習(xí)題1的9).

任取X的一個(gè)子集S，令E1={e|e∈E,并且e與S中的頂點(diǎn)關(guān)聯(lián)}E2={e|e∈E,并且e與N(S)中的頂點(diǎn)關(guān)聯(lián)}.13由（2.2）式和（2.3）式推出推論若G是k正則偶圖（k因與S中的頂點(diǎn)關(guān)聯(lián)的邊必與N(S)中的頂點(diǎn)關(guān)聯(lián)，所以E1

E2再根據(jù)定理2，可知G有一個(gè)飽和X的每個(gè)頂點(diǎn)的匹配M.E1={e|e∈E,并且e與S中的頂點(diǎn)關(guān)聯(lián)}E2={e|e∈E,并且e與N(S)中的頂點(diǎn)關(guān)聯(lián)}由于|X|=|Y|，所以M是完美匹配。

.14因與S中的頂點(diǎn)關(guān)聯(lián)的邊必與N(S)中的頂點(diǎn)關(guān)聯(lián)，所注:(1)G=(X,Y)存在飽和X每個(gè)頂點(diǎn)的匹配也常說成存在由X到Y(jié)的匹配。

(2)Hall定理也可表述為：設(shè)G=(X,Y)是偶圖，如果存在X的一個(gè)子集S,使得|N(S)|<|S|，那么G中不存在由X到Y(jié)的匹配。Hall定理也稱為“相異性條件”。

(3)Hall定理也稱為“婚姻定理”，表述如下：“婚姻定理”：在一個(gè)由r個(gè)女人和s個(gè)男人構(gòu)成的人群中，1≦r≦s。在熟識(shí)的男女之間可能出現(xiàn)r對(duì)婚姻的充分必要條件是，對(duì)每個(gè)整數(shù)k(1≦k≦r),任意k個(gè)女人共認(rèn)識(shí)至少k個(gè)男人。(5)Hall定理是在偶圖中求最大匹配算法的理論基礎(chǔ)，即匈牙利算法基礎(chǔ)。

(4)Hall定理還可以表述為：偶圖G=<V1,E,V2>中存在從V1到V2的匹配的充分必要條件是V1中任意k個(gè)結(jié)點(diǎn)至少與V2中的k個(gè)結(jié)點(diǎn)相鄰，k=1,2,…,|V1|。.15注:(1)G=(X,Y)存在飽和X每個(gè)頂點(diǎn)的匹推論：設(shè)G=<V1,E,V2>是一個(gè)偶圖。如果滿足條件（1）V1中每個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)t條邊；（2）V2中每個(gè)結(jié)點(diǎn)至多關(guān)聯(lián)t條邊；則G中存在從V1到V2的匹配。其中t為正整數(shù)。證明：由(1)知，V1中任意k個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)tk條邊(1≤k≤|V1|)，偶圖匹配存在條件——t條件：由(2)知，這tk條邊至少與V2中k個(gè)結(jié)點(diǎn)相關(guān)聯(lián)，于是V1中的k個(gè)結(jié)點(diǎn)至少與V2中的k個(gè)結(jié)點(diǎn)相鄰接，因而滿足相異性條件，所以G中存在從V1到V2的匹配。.16推論：設(shè)G=<V1,E,V2>是一個(gè)偶圖。如果滿足條件證圖G的一個(gè)覆蓋:指V(G)的一個(gè)子集K，使得G的每條邊都至少有一個(gè)端點(diǎn)在K中。G的最小覆蓋:G中點(diǎn)數(shù)最少的覆蓋一個(gè)覆蓋一個(gè)最小覆蓋例

3、點(diǎn)覆蓋與哥尼定理v1v2v3v4v5v6V1V2v1v2v3v5v6v7v8v4v9V1V2.17圖G的一個(gè)覆蓋:指V(G)的一個(gè)子集K，使得G的每條邊都匹配與覆蓋的關(guān)系:

設(shè)K是G的覆蓋，M是G的匹配,則有理由:K至少包含M中每條邊的一個(gè)端點(diǎn)。(1)|M|≤|K|,特別地,若M*是最大匹配，且是最小覆蓋,則(2)

定理4

設(shè)M是匹配，K是覆蓋，若|M|＝|K|，則M是最大匹配，且K是最小覆蓋。證明

設(shè)M*是最大匹配,是最小覆蓋，則由（2.4）式，

|M|≤|M*|≤≤|K|由于|M|＝|K|，所以|M|=|M*|,=|K|。

|M*|≤(2.4).18匹配與覆蓋的關(guān)系:設(shè)K是G的覆蓋，M是G的匹配,則哥尼(K?nig，1884----1944))——第一本圖論教材《有限圖與無限圖理論》（1936年）的撰寫者。該書對(duì)青年學(xué)者產(chǎn)生了很大影響，推動(dòng)了圖論的進(jìn)一步發(fā)展。在20多年時(shí)間里，它都是世界上唯一一本圖論著作。直到1958年，法國數(shù)學(xué)家貝爾熱(Berge）才出版專著《無限圖理論及其應(yīng)用》。哥尼早期學(xué)習(xí)拓?fù)鋵W(xué)，但對(duì)圖論興趣特別大。他一直工作在布達(dá)佩斯工業(yè)大學(xué)。講課很有激情，吸引了很多優(yōu)秀學(xué)生轉(zhuǎn)向圖論研究。特別是，他把一起獲得匈牙利國家高中數(shù)學(xué)競(jìng)賽一等獎(jiǎng)的3個(gè)學(xué)生都吸引來研究圖論，這3個(gè)學(xué)生是：Erd?s,Gallai,Turan.都是偉大的數(shù)學(xué)家。哥尼1944年為免遭納碎迫害，選擇了自殺。.19哥尼(K?nig，1884----1944))——(3)

定理5（Kǒnig，哥尼，1931）偶圖中，最大匹配的邊數(shù)等于最小覆蓋的頂點(diǎn)數(shù)。證明設(shè)G是具有二分類（X,Y）的偶圖，M*是G的最大匹配，用U表示X中的M*非飽和頂點(diǎn)的集，用Z表示由M*

交錯(cuò)路連接到U中頂點(diǎn)的所有頂點(diǎn)的集。置

S=Z∩X,T=Z∩Y。類似于定理2的證明，可知T中的每個(gè)頂點(diǎn)都是M*飽和的，并且N(S)＝T。定義=(X\S)∪T（見圖）。SUT=N(S)X\S.20(3)定理5（Kǒnig，哥尼，1931）偶圖中，最則G的每條邊必然至少有一個(gè)端點(diǎn)在

中，因?yàn)榉駝t就存在一條邊，其一個(gè)端點(diǎn)在S中，而另一個(gè)端點(diǎn)在Y\T中，這與N(S)＝T相矛盾。于是是G的覆蓋。并且顯然有|M*|=由定理4，是最小覆蓋。例1

矩陣的一行或一列統(tǒng)稱為一條線。證明：包含了一個(gè)（0,1）矩陣（布爾矩陣）中所有〝1〞的線的最小條數(shù)，等于具有性質(zhì)〝任意兩個(gè)1都不在同一條線上〞的〝1〞的最大個(gè)數(shù)。.21則G的每條邊必然至少有一個(gè)端點(diǎn)在中，因?yàn)榉駝t就這樣,此矩陣的第i行線包含1的個(gè)數(shù)就是G中點(diǎn)xi關(guān)聯(lián)的邊數(shù)，而第j列線包含1的個(gè)數(shù)就是G中點(diǎn)yj關(guān)聯(lián)的邊數(shù)，故包含了（0,1）矩陣中所有〝1〞的線的最小條數(shù)就是偶圖G中的最小覆蓋的點(diǎn)數(shù)。證明

將（0,1）矩陣對(duì)應(yīng)一個(gè)具有二分類(X,Y)的偶圖G,使其行代表X中的元素,列代表Y中的元素,且滿足（注:對(duì)應(yīng)后,1則代表邊,G含有飽和X的每個(gè)點(diǎn)的匹配當(dāng)且僅當(dāng)Q中存在|X|個(gè)不同行不同列的1).22這樣,此矩陣的第i行線包含1的個(gè)數(shù)就是G中點(diǎn)xi而（0,1）矩陣中任意兩個(gè)都不在相同線上的若干個(gè)1，就是偶圖G中的一個(gè)匹配。而具有上述性質(zhì)的1的最大個(gè)數(shù)，就是偶圖G中最大匹配的邊數(shù)，由定理5，問題得證.例如,矩陣Q及其對(duì)應(yīng)的偶圖如下圖。其最小覆蓋是{x1,y2,y4}，故包含Q中所有1的線是Q的1行，第2、4列，共3條。

x1x2x3

x4y1y2y3y4.23而（0,1）矩陣中任意兩個(gè)都不在相同線上的若干個(gè)1§5.3Tutte定理與完美匹配奇(偶)分支:圖的有奇(偶)數(shù)個(gè)頂點(diǎn)的分支,我們用o(G)表示圖G的奇分支的個(gè)數(shù)。定理5（Tutte）

G有完美匹配當(dāng)且僅當(dāng)

o(G－S)≤|S|,對(duì)所有S

V成立（3.1）推論

每個(gè)沒有割邊的3正則圖都有完美匹配。例

彼得森圖滿足推論的條件（即沒有割邊的3正則圖），故它有完美匹配.證明冗長，從略。.24§5.3Tutte定理與完美匹配奇(偶)分支:圖的有奇

證明：設(shè)S是V的任意一個(gè)非空真子集，G1,G2,…,Gk是G-S的所有奇分支。mi(1≦i≦k)表示端點(diǎn)分屬于S和Gi的邊數(shù)。SG1G2Gkm1m2mk.證明：設(shè)S是V的任意一個(gè)非空真子集，G1,G2,…25

下面分析miSG1G2Gkm1m2mk在Gi中，其總度數(shù)為2|E(Gi)|。

在Gi中，其點(diǎn)在G中的總度數(shù)為3|V(Gi)|。所以：所以mi必然為奇數(shù)，但G無割邊，所以mi≥3.這樣：

由托特定理，G有完美匹配。.26下面分析miSG1G2Gkm1m2mk在Gi中，其注:有割邊的3正則圖不一定有完美匹配沒有完美匹配有完美匹配.27注:有割邊的3正則圖不一定有完美匹配沒有完美匹配有完美匹配§5.4因子分解一.1－因子分解圖G的因子:

G的一個(gè)至少有一條邊的生成子圖；G的因子分解:將G分解為一些邊不相交的因子,使這些因子的并即為G；n-因子：指n度正則的因子。n-因子分解：每個(gè)因子均為n-因子的因子分解，此時(shí)稱G本身是n-可因子化的。.28§5.4因子分解一.1－因子分解圖G的因子:G的如果一個(gè)圖G能夠分解為若干n因子之并，稱G是可n因子分解的。圖G1在上圖中，紅色邊在G1中的導(dǎo)出子圖，是G的一個(gè)一因子；紅色邊在G2中的導(dǎo)出子圖，是G的一個(gè)二因子。圖G2研究圖的因子分解主要是兩個(gè)方面：一是能否進(jìn)行分解(因子分解的存在性),二是如何分解(分解算法)..29如果一個(gè)圖G能夠分解為若干n因子之并，稱G是可n因

圖的一個(gè)一因子實(shí)際上就是圖的一個(gè)完美匹配的導(dǎo)出子圖。一個(gè)圖能夠作一因子分解，也就是它能夠分解為若干邊不重的完美匹配的導(dǎo)出子圖之并。

定理6-7：

K2n,k-正則偶圖(k>0),可一因子分解。

定理6的證明：把K2n的2n個(gè)頂點(diǎn)編號(hào)為1，2，…,2n。作如下排列：2n132::n2n-12n-2::n+1.30圖的一個(gè)一因子實(shí)際上就是圖的一個(gè)完美匹配的導(dǎo)出子圖圖中，每行兩點(diǎn)鄰接，顯然作成K2n的一個(gè)一因子。2n132::n2n-12n-2::n+1然后按照?qǐng)D中箭頭方向移動(dòng)一個(gè)位置，又可以得到K2n的一個(gè)一因子，不斷作下去，得到K2n的2n-1個(gè)邊不重的一因子，其并恰好為K2n。

例1將K4作一因子分解。1234K4→41231234.31圖中，每行兩點(diǎn)鄰接，顯然作成K2n的一個(gè)一因子。21234423143121234例2

將K3,3作1-因子分解

1231’2’3’K3,3定理7的證明：不斷減去完美匹配解將X的點(diǎn)用數(shù)字1，2，3標(biāo)記，而Y的點(diǎn)用1’，2’，3’來標(biāo)記，用置換G來表示K3,3中X的點(diǎn)與Y的點(diǎn)間之匹配關(guān)系，則G1G2G3.1234423143121234例2將K3,3作1-因子32定理8具有H圈的三正則圖可一因子分解。證明：先從三正則圖G中抽取H圈，顯然剩下邊構(gòu)成G的一個(gè)一因子。

注：定理8的逆不一定成立。例如：

上圖是三正則圖，且可以一因子分解，但不存在H圈。而3正則圖的H圈是偶圈，可以分解為兩個(gè)一因子。所以G可以分解為3個(gè)一因子。.33定理8具有H圈的三正則圖可一因子分解。證明：先從三正則圖G定理9若3-正則圖有割邊，則不可1-因子分解。回憶：推論

每個(gè)沒有割邊的3正則圖都有完美匹配。定理5（Tutte）

G有完美匹配當(dāng)且僅當(dāng)

o(G－S)≤|S|,對(duì)所有S

V成立（3.1）證明：若不然，設(shè)G的三個(gè)一因子為G1,G2,G3。不失一般性，設(shè)割邊e∈G2。則G-G1中每個(gè)點(diǎn)的度數(shù)均為2，所以e在G的某個(gè)圈中，這與e是G的割邊矛盾。注：沒有割邊的三正則圖可能也沒有一因子分解，如彼得森圖,盡管它存在完美匹配。.34定理9若3-正則圖有割邊，則不可1-因子分解?；貞洠和普摱?2－因子分解

如果一個(gè)圖可以分解為若干2度正則因子之并，稱G可以2因子分解。注意：G的一個(gè)H圈肯定是G的一個(gè)2因子，但是G的一個(gè)2因子不一定是G的H圈。2因子可以不連通。例如，在下圖中：兩個(gè)紅色圈的并構(gòu)成圖的一個(gè)2因子，但不是H圈。

一個(gè)顯然結(jié)論是：G能進(jìn)行2因子分解，其頂點(diǎn)度數(shù)必然為偶數(shù)。(注意，不一定是歐拉圖).35二.2－因子分解如果一個(gè)圖可以分解為若干2度正其中Pi的第j點(diǎn)是vk，k=i+(-1)j+1

，并且所有下標(biāo)取為整數(shù)1，2，…，2n（mod2n）。生成圈Hi

是由v2n+1聯(lián)接于Pi的兩個(gè)端點(diǎn)構(gòu)成。證明為了在K2n+1中構(gòu)成n個(gè)邊不相交的生成圈，先標(biāo)定它的點(diǎn)v1,v2,…,v2n+1。然后，在點(diǎn)v1,v2,…,v2n上構(gòu)成n條路Pi如下：Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n定理10圖K2n+1

是n個(gè)H圈的和。.36其中Pi的第j點(diǎn)是vk，k=i+(-

例3對(duì)K7作2因子分解。(n=3)

解：v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1vk，k=i+(-1)j+1

，并且所有下標(biāo)取為整數(shù)1，2，…，2n（mod2n）。Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n.37例3對(duì)K7作2因子分解。(n=3)解：定理11完全圖K2n是一個(gè)1-因子和n-1個(gè)H圈的和。定理12每一個(gè)沒有割邊的3度正則圖是一個(gè)1-因子和一個(gè)2-因子的和。(由定理5的推論可證)例

彼得森圖是一個(gè)1-因子和一個(gè)2-因子的和

注若沒有割邊的3度正則圖中的2-因子是一些偶圈,則該圖也是1-可因子化的.定理13一個(gè)連通圖是2-可因子化的當(dāng)且僅當(dāng)它是偶數(shù)度正則的。.38定理11完全圖K2n是一個(gè)1-因子和n-1個(gè)H圈的和。定三、蔭度蔭度圖G分解為邊不相交的生成森林的最少數(shù)目,記為σ(G)。例

σ(K4)=2σ(K5)

=3

把一個(gè)圖分解為若干邊不重的森林因子的和，稱為圖的森林因子分解。.39三、蔭度蔭度圖G分解為邊不相交的生成森林的最少數(shù)目,記為σ定理14令G是一個(gè)非平凡圖，又令ms是G的任何一個(gè)有s個(gè)點(diǎn)的子圖中邊的最多數(shù)目，則σ(G)≥的證明因?yàn)槿鬐有n個(gè)點(diǎn)，則在任何一個(gè)生成森林中邊的最多數(shù)目是n－1。從而G的邊不相交的生成森林至少有m/(n-1)個(gè).但G的蔭度是一個(gè)整數(shù)，所以σ(G)≥。對(duì)于子圖H，顯然有σ(G)≥σ(H)，故σ(G)≥。.40定理14令G是一個(gè)非平凡圖，又令ms是G的任何一個(gè)有s個(gè)

例4求σ(K5)和σ(K3,3)..41例4求σ(K5)和σ(K3,3)..41拜內(nèi)克給出了完全圖和完全偶圖的最小森林因子分解。

對(duì)于K2n，將其分解為n條路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,腳標(biāo)按模2n計(jì)算。

對(duì)于K2n+1，先作n條路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,腳標(biāo)按模2n計(jì)算。在每條路外添上點(diǎn)v2n+1的n個(gè)森林因子；然后，v2n+1與v1,v2,…,v2n分別相連接得一星圖，這是G的最后一個(gè)森林因子。推論

完全圖和完全偶圖的蔭度為.42拜內(nèi)克給出了完全圖和完全偶圖的最小森林因子分解。例5分K7為生成森林的最小分解如下圖所示。v7v1v6v2

v5v3

v4v7v1v6v2

v5

v3

v4v7v7

P117---118習(xí)題5：1(2)，2，3,4,5，7，8，9,13.43例5分K7為生成森林的最小分解如下圖所示。v7人員分派問題：n個(gè)工人x1,x2,…,xn，n件工作y1,y2,…,yn。已知xi

能勝任

ki件工作，i=1，2，…,n。問能否存在一種工作安排方案，使每個(gè)人都能分配到他所能勝任的一件工作。假定每件工作只能一人做，若能，又如何安排？

建模：以工人和工作為點(diǎn)，當(dāng)且僅當(dāng)xi

能勝任工作

yj時(shí)則連線，得偶圖G.于是一種符合要求的安排對(duì)應(yīng)G中一個(gè)完美匹配。所以此問題實(shí)際上是求偶圖的完美匹配問題.

進(jìn)一步：若不要求人數(shù)與工作數(shù)相等，則問題是求偶圖的飽和X的每個(gè)點(diǎn)的匹配問題，其中X是工人的集合；進(jìn)一步，若問：能否存在一種安排使盡可能多的人能分到他能勝任的工作或使盡可能多的工作被分配，則問題為求偶圖的最大匹配問題。§5.5最優(yōu)匹配與匈牙利算法.44人員分派問題：n個(gè)工人x1,x2,…,xn，n件工

(一)、匈牙利算法

1、偶圖中尋找完美匹配

(1)、問題

設(shè)G=(X,Y),|X|=|Y|,在G中求一完美匹配M.

(2)、基本思想

從任一初始匹配M0出發(fā)，通過尋求一條M0可擴(kuò)路P，令M1=M0ΔE(P)（將可擴(kuò)路中M0

與非M0

的邊互換）,得到比M0更大的匹配M1。(3)、M可擴(kuò)擴(kuò)路的尋找方法1965年，Edmonds首先提出:用扎根于M非飽和點(diǎn)u的M交錯(cuò)樹的生長來求M可擴(kuò)路。.45(一)、匈牙利算法1、偶圖中尋找完美匹配

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

1)u∈V(H)；2)對(duì)任意v∈V(H),(u,v)路是M交錯(cuò)路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交錯(cuò)樹扎根于M非飽和點(diǎn)u的M交錯(cuò)樹的生長討論：

假如扎根于M非飽和點(diǎn)u的M交錯(cuò)樹為H。它有兩種情形：.46定義1設(shè)G=(X,Y),M是G的匹配，u是X的

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

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

對(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中不存在完美匹配；.47情形1除點(diǎn)u外，H中所有點(diǎn)為M飽和點(diǎn)，且在M上配

2)若

令y∈N(S)–T,則在樹H中存在X中的點(diǎn)x與y鄰接。因?yàn)镠的所有點(diǎn)，除u外，均在M下配對(duì)。所以，或者x=u，或者x與H的某一頂點(diǎn)配對(duì)，但無論哪種情況，都有xux2y4y3y2扎根u

的M交錯(cuò)樹Hx5yxux2y4y3y2扎根u

的M交錯(cuò)樹Hx5y

當(dāng)然，y可能為M飽和點(diǎn)，也可能為M非飽和點(diǎn)。令S=V(H)∩X,T=V(H)∩Y.482)若令y∈N(S)–T,則在樹

若y為M飽和點(diǎn)，可設(shè)yz∈M,則加上頂點(diǎn)y及z和邊xy與yz來生長H，得到情形1；xux2y4y3y2扎根u

的M交錯(cuò)樹Hx5yz

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

的M交錯(cuò)樹Hx5y令S=V(H)∩X,T=V(H)∩Y.49若y為M飽和點(diǎn)，可設(shè)yz∈M,則加上頂點(diǎn)y及z和邊

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

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

(4)、偶圖完美匹配算法——匈牙利算法。

設(shè)M是初始匹配。H是扎根于M非飽和點(diǎn)u的交錯(cuò)樹。令：S=V(H)∩X,T=V(H)∩Y。

(a)、若M飽和X所有頂點(diǎn)，停止。否則，設(shè)u為X中M非飽和頂點(diǎn)，置S=｛u｝,T=Φ;

(b)、若N(S)=T,則G中不存在完美匹配。否則設(shè)y∈N(S)–T.

(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)..50后一情況下找到一條M可擴(kuò)路，可以對(duì)匹配進(jìn)行一次修改，

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

解：取初始匹配M=｛x1y1,x2y3｝(a)S=｛x3｝,T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y).51例1討論下圖G=(X,Y)是否有完美匹配。x1

(b)N(S)=｛y2,y3｝,N(S)≠T,取y2∈N(S)-T(c)y2為M非飽和點(diǎn)，加上y2和邊x3y2生長樹H。此時(shí)，置M=MΔE(P)=｛x1y1,x2y3,x3y2｝x1x2x3x4x5y1y2y3y4y5G=(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y).52(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｝={x3，x4}T=T∪｛y2｝。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx4y2x3.53(a)S=｛x4｝,T=Φ;x1x2x3x4x5(c)y3為M飽和點(diǎn)，x2y3∈M。此時(shí)，置S=S∪{x2｝={x2,x3,x4}T=T∪｛y3｝=｛y2,y3｝

。(b)N(S)=｛y2,y3｝≠T，取y3∈N(S)-Tx1x2x3x4x5y1y2y3y4y5G=(X,Y)

(b)N(S)=｛y2,y3｝=T，所以，G無完美匹配。

(5)、匈牙利算法復(fù)雜性分析.54(c)y3為M飽和點(diǎn)，x2y3∈M。此時(shí)，置S=S∪{1)、最多循環(huán)|X|次可以找到完美