圖論課件第五章匹配與因子分解

圖論課件第五章匹配與因子分解第一頁，共三十一頁，編輯于2023年，星期二2第五章匹配與因子分解主要內(nèi)容一、偶圖的匹配問題二、圖的因子分解三、匈牙利算法與最優(yōu)匹配算法教學(xué)時數(shù)安排6學(xué)時講授本章內(nèi)容第二頁，共三十一頁，編輯于2023年，星期二3本次課主要內(nèi)容(一)、圖的匹配與貝爾熱定理(二)、偶圖的匹配與覆蓋(三)、托特定理偶圖的匹配問題第三頁，共三十一頁，編輯于2023年，星期二4

1、圖的匹配相關(guān)概念

(1)、匹配M---如果M是圖G的邊子集(不含環(huán)），且M中的任意兩條邊沒有共同頂點(diǎn)，則稱M是G的一個匹配或?qū)蜻叒?dú)立集。(一)、圖的匹配與貝爾熱定理如果G中頂點(diǎn)v是G的匹配M中某條邊的端點(diǎn)，稱它為M飽和點(diǎn)，否則為M非飽和點(diǎn)。v1

v7v6Gv8v2v3v5v4

M1=｛v6v7｝

M2=｛v6v7,v1v8｝

M3=｛v6v7,v1v8,v3v4｝

M1,M2,M3等都是G的匹配。第四頁，共三十一頁，編輯于2023年，星期二5

(2)、最大匹配M---如果M是圖G的包含邊數(shù)最多的匹配，稱M是G的一個最大匹配。特別是，若最大匹配飽和了G的所有頂點(diǎn)，稱它為G的一個完美匹配。G的一個最大匹配G的一個完美匹配注：一個圖G不一定存在完美匹配。第五頁，共三十一頁，編輯于2023年，星期二6

(3)、M交錯路---如果M是圖G的匹配，G中一條由M中的邊和非M中的邊交錯形成的路，稱為G中的一條M交錯路。特別地，若M交錯路的起點(diǎn)與終點(diǎn)是M非飽和點(diǎn)，稱這種M交錯路為M可擴(kuò)路。在下圖中：v1

v7v6Gv8v2v3v5v4設(shè)M=｛v7v8,v3v4｝，則：路v6v7v8v3v4與v1v7v8v2都是M交錯路。其中后者是M可擴(kuò)路。第六頁，共三十一頁，編輯于2023年，星期二7

2、貝爾熱定理定理1(貝爾熱，1957)G的匹配M是最大匹配，當(dāng)且僅當(dāng)G不包含M可擴(kuò)路。證明：“必要性”若G包含一條M可擴(kuò)路P,則可令該可擴(kuò)路為：顯然，P中M中的邊比非M中的邊少一條。于是作新的匹配M1,它當(dāng)中的邊由P中非M中邊組成。M1中邊比M中多一條，這與M是G的最大匹配矛盾?！俺浞中浴比舨蝗?，設(shè)M1是G的一個最大匹配，則|M1|>|M|。第七頁，共三十一頁，編輯于2023年，星期二8令H=M1ΔM。容易知道：G[H]的每個分支或者是由M1與M中邊交替組成的偶圈，或者是由M1與M中邊交替組成的路。在每個偶圈中，M1與M中邊數(shù)相等；但因|M1|>|M|，所以，至少有一條路P，其起點(diǎn)和終點(diǎn)都是M非飽和點(diǎn)，于是，它是G的一條M可擴(kuò)路。這與條件矛盾。注：貝爾熱定理給我們提供了擴(kuò)充G的匹配的思路。貝爾熱(1926---2002)法國著名數(shù)學(xué)家。他的《無限圖理論及其應(yīng)用》(1958)是繼哥尼之后的圖論歷史上的第二本圖論專著。他不僅在圖論領(lǐng)域做出了許多貢獻(xiàn)，而且四處奔波傳播圖論，推動了圖論的普及和發(fā)展。

1993年，他獲得組合與圖論領(lǐng)域頒發(fā)的歐拉獎?wù)?。第八頁，共三十一頁，編輯?023年，星期二9貝爾熱在博弈論、拓?fù)鋵W(xué)領(lǐng)域里也有杰出貢獻(xiàn)。在博弈領(lǐng)域，他引入了Nash均衡之外的另一種均衡系統(tǒng)。Nash的生活被改編成電影《美麗的心靈》，獲02年奧斯卡金像獎。貝爾熱對中國的手工藝很感興趣。他也是一位象棋高手，還創(chuàng)作過小說《誰殺害了Densmore公爵》。(二)、偶圖的匹配與覆蓋在日常生活，工程技術(shù)中，常常遇到求偶圖的匹配問題。下面看一個例子：

1、問題的提出第九頁，共三十一頁，編輯于2023年，星期二10有7名研究生A,B,C,D,E,F,G畢業(yè)尋找工作。就業(yè)處提供的公開職位是：會計(jì)師(a),咨詢師(b),編輯(c),程序員(d),記者(e),秘書(f)和教師(g)。每名學(xué)生申請的職位如下：

A:b,c;B:a,b,d,f,g;C:b,e;D:b,c,e;

E:a,c,d,f;F:c,e;G:d,e,f,g;問：學(xué)生能找到理想工作嗎？解：如果令X=｛A,B,C,D,E,F,G｝,Y=｛a,b,c,d,e,f,g｝,X中頂點(diǎn)與Y中頂點(diǎn)連線當(dāng)且僅當(dāng)學(xué)生申請了該工作。于是，得到反映學(xué)生和職位之間的狀態(tài)圖：第十頁，共三十一頁，編輯于2023年，星期二11問題轉(zhuǎn)化為求飽和X每個頂點(diǎn)的一個匹配！

A:b,c;B:a,b,d,f,g;C:b,e;D:b,c,e;

E:a,c,d,f;F:c,e;G:d,e,f,g;FEDCBAGabcdefg需要解決的問題是:(1)匹配是否存在？(2)如何求出匹配？

2、偶圖匹配存在性判定----Hall定理第十一頁，共三十一頁，編輯于2023年，星期二12FEDCBAGabcdefg定理2(Hall定理）設(shè)G=(X,Y)是偶圖，則G存在飽和X每個頂點(diǎn)的匹配的充要條件是：例1，在下面偶圖中，是否存在飽和X=｛A,B,C,D,E,F,G｝的每個頂點(diǎn)的匹配？第十二頁，共三十一頁，編輯于2023年，星期二13FEDCBAGabcdefg解:(1)當(dāng)S取X中單元點(diǎn)時，容易驗(yàn)證：|N(S)|>|S|

(2)當(dāng)S取X中二元點(diǎn)集時，容易驗(yàn)證：|N(S)|≧|S|

(3)當(dāng)S取X中三元點(diǎn)集時，容易驗(yàn)證：|N(S)|≧|S|

(4)當(dāng)S取X中四元點(diǎn)集時，若取S=｛A,C,D,F｝,則有3=|N(S)|<|S|=4

所以，不存在飽和X每個頂點(diǎn)的匹配。

下面我們證明Hall定理。第十三頁，共三十一頁，編輯于2023年，星期二14

證明：“必要性”

如果G存在飽和X每個頂點(diǎn)的匹配，由匹配的定義，X的每個頂點(diǎn)在Y中至少有一個鄰接點(diǎn)，所以:

“充分性”

如果G是滿足條件(*)的偶圖,但是不存在飽和X每個頂點(diǎn)的匹配。

令M*是G的一個最大匹配，但是不飽和X的頂點(diǎn)u.u示意圖G第十四頁，共三十一頁，編輯于2023年，星期二15又令Z是通過M*與點(diǎn)u相連形成的所有M*交錯路上的點(diǎn)集。因M*是最大匹配，所以u是所有交錯路上唯一的一個未飽和點(diǎn)。令S=X∩Z,T=Z∩Y顯然，S-｛u｝中點(diǎn)與T中點(diǎn)在M*下配對，即：

|T|=|S|-1<|S|即：|N(S)|=|T|=|S|-1<|S|，與條件矛盾。uTS注:(1)G=(X,Y)存在飽和X每個頂點(diǎn)的匹配也常說成存在由X到Y(jié)的匹配。第十五頁，共三十一頁，編輯于2023年，星期二16

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

(3)Hall定理也稱為“婚姻定理”，表述如下：“婚姻定理”：在一個由r個女人和s個男人構(gòu)成的人群中，1≦r≦s。在熟識的男女之間可能出現(xiàn)r對婚姻的充分必要條件是，對每個整數(shù)k(1≦k≦r),任意k個女人共認(rèn)識至少k個男人。

(4)Hall定理是在偶圖中求最大匹配算法的理論基礎(chǔ)，即匈牙利算法基礎(chǔ)。

(5)Hall(1904---1982)英國人，20世紀(jì)最偉大的數(shù)學(xué)家之一。主要功績是在代數(shù)學(xué)領(lǐng)域。在劍橋大學(xué)工作期間，主要研究群論，1932年發(fā)表的關(guān)于素?cái)?shù)冪階群論文是他最有名第十六頁，共三十一頁，編輯于2023年，星期二17的工作。匹配定理是他1935年在劍橋大學(xué)做講師時發(fā)表的結(jié)果。Hall是一名雅致的學(xué)者，對學(xué)生特別友好，當(dāng)他覺得有必要批評學(xué)生時，他都會以一種十分溫和的方式建議他們改正。推論：若G是k(k>0)正則偶圖，則G存在完美匹配。證明：一方面，由于G是k(k>0)正則偶圖,所以k|X|=k|Y|,于是得|X|=|Y|；另一方面，對于X的任一非空子集S,設(shè)E1與E2分別是與S和N(S)關(guān)聯(lián)的邊集，顯然有：即：由Hall定理，存在由X到Y(jié)的匹配.又|X|=|Y|，所以G存在完美匹配。第十七頁，共三十一頁，編輯于2023年，星期二18例2(1)證明：每個k方體都有完美匹配(k大于等于2)

(2)求K2n和Kn,n中不同的完美匹配的個數(shù)。

(1)證明一：證明每個k方體都是k正則偶圖。事實(shí)上，由k方體的構(gòu)造：k方體有2k個頂點(diǎn)，每個頂點(diǎn)可以用長度為k的二進(jìn)制碼來表示，兩個頂點(diǎn)連線當(dāng)且僅當(dāng)代表兩個頂點(diǎn)的二進(jìn)制碼只有一位坐標(biāo)不同。如果我們劃分k方體的2k個頂點(diǎn)，把坐標(biāo)之和為偶數(shù)的頂點(diǎn)歸入X，否則歸入Y。顯然，X中頂點(diǎn)互不鄰接，Y中頂點(diǎn)也如此。所以k方體是偶圖。又不難知道k方體的每個頂點(diǎn)度數(shù)為k,所以k方體是k正則偶圖。由推論：k方體存在完美匹配。第十八頁，共三十一頁，編輯于2023年，星期二19證明二：直接在k方體中找出完美匹配。設(shè)k方體頂點(diǎn)二進(jìn)制碼為(x1,x2,…,xn),我們?nèi)?x1,x2,…,xn-1,0),和(x1,x2,…,xn-1,1)之間的全體邊所成之集為M.顯然，M中的邊均不相鄰接，所以作成k方體的匹配，又容易知道：|M|=2k-1.所以M是完美匹配。

(2)我們用歸納法求K2n和Kn,n中不同的完美匹配的個數(shù)。K2n的任意一個頂點(diǎn)有2n-1中不同的方法被匹配。所以K2n的不同完美匹配個數(shù)等于(2n-1)K2n-2,如此推下去，可以歸納出K2n的不同完美匹配個數(shù)為：(2n-1)!!

同樣的推導(dǎo)方法可歸納出Kn,n的不同完美匹配個數(shù)為：(n)!第十九頁，共三十一頁，編輯于2023年，星期二20例3證明樹至多存在一個完美匹配。證明：若不然，設(shè)M1與M2是樹T的兩個不同的完美匹配，那么M1ΔM2≠Φ,且T[M1ΔM2]每個頂點(diǎn)度數(shù)為2，即它存在圈，于是推出T中有圈，矛盾。

3、點(diǎn)覆蓋與哥尼定理

(1)、圖的點(diǎn)覆蓋概念與性質(zhì)定義1：圖的點(diǎn)覆蓋---G的一個頂點(diǎn)子集K稱為G的一個點(diǎn)覆蓋，如果G的每條邊都至少有一個端點(diǎn)在K中。G的一個包含點(diǎn)數(shù)最少的點(diǎn)覆蓋稱為G的最小點(diǎn)覆蓋，其包含的點(diǎn)數(shù)稱為G的覆蓋數(shù)，記為α(G).(a)一個覆蓋(b)一個最小覆蓋第二十頁，共三十一頁，編輯于2023年，星期二21定理2設(shè)M是G的匹配，K是G的覆蓋，若|M|=|K|,則M是最大匹配，而G是最小覆蓋。證明：設(shè)M*與K*分別是G的最大匹配和最小覆蓋。由匹配和覆蓋定義有：|M*|≦|K*|。所以，有：

|M|

≦|M*|≦|K*|≦|K|所以，當(dāng)|M|=|K|時，有|M|=|M*|，|K*|=|K|即M是最大匹配，而G是最小覆蓋。

(2)、偶圖的點(diǎn)覆蓋與偶圖匹配間的關(guān)系----哥尼定理第二十一頁，共三十一頁，編輯于2023年，星期二22定理2(哥尼，1931)在偶圖中，最大匹配的邊數(shù)等于最小覆蓋的頂點(diǎn)數(shù)。證明：設(shè)G=(X,Y),M*是偶圖G的最大匹配。U表示G中M*非飽和點(diǎn)集。Z表示由M*交錯路連到U的頂點(diǎn)的所有路上的點(diǎn)作成的集合。且令S=Z∩X,T=Z∩Y。SUT=N(S)

X\S第二十二頁，共三十一頁，編輯于2023年，星期二23由M*的最大性，T中點(diǎn)是M*飽和的，且N(S)=T。SUT=N(S)

X\S現(xiàn)在，令K*=(X-S)∪T?？梢宰C明：K*=(X-S)∪T是G的一個覆蓋。事實(shí)上，若K*=(X-S)∪T不是G的一個覆蓋。則存在G的一條邊,其一個端點(diǎn)在S中，而另一個端點(diǎn)在Y-T中，這與N(S)=T矛盾！顯然|K*|=|M*|。由定理2，K*是最小覆蓋。第二十三頁，共三十一頁，編輯于2023年，星期二24哥尼(K?nig)——第一本圖論教材的撰寫者到了1936年，第一本圖論教材才與讀者見面。作者是哥尼(1884----1944).哥尼早期學(xué)習(xí)拓?fù)鋵W(xué)，但對圖論興趣特別大。他一直工作在布達(dá)佩斯工業(yè)大學(xué)。講課很有激情，吸引了很多優(yōu)秀學(xué)生轉(zhuǎn)向圖論研究。特別是，他把一起獲得匈牙利國家高中數(shù)學(xué)競賽一等獎的3個學(xué)生都吸引來研究圖論，這3個學(xué)生是：Erd?s,Gallai,Turan.都是偉大的數(shù)學(xué)家。哥尼的著作名稱是《有限圖與無限圖理論》。這本書對青年學(xué)者產(chǎn)生了很大影響，推動了圖論的進(jìn)一步發(fā)展。在20多年時間里，它都是世界上唯一一本圖論著作。直到1958年，法國數(shù)學(xué)家貝爾熱(Berge）才出版專著《無限圖理論及其應(yīng)用》。哥尼1944年為免遭納碎迫害，只有自殺。第二十四頁，共三十一頁，編輯于2023年，星期二25例4矩陣的一行或一列稱為矩陣的一條線。證明：布爾矩陣中，包含了所有“1”的線的最少數(shù)目，等于具有性質(zhì)“任意兩個1都不在同一條線上的1的最大數(shù)目”。例如：在如下布爾矩陣中：證明：設(shè)布爾陣是n行m列矩陣，把它模型為一個偶圖如下：每行每列分別用一個點(diǎn)表示，X表示行點(diǎn)集合，Y表示列點(diǎn)集合，兩點(diǎn)連線。當(dāng)且僅當(dāng)該行該列元為1.第二十五頁，共三十一頁，編輯于2023年，星期二26于是，包含了所有“1”的線的最少數(shù)目對應(yīng)偶圖中的最小點(diǎn)覆蓋數(shù)。而具有性