偶圖的匹配問題

1、1(一)、圖的匹配與貝爾熱定理(二)、偶圖的匹配與覆蓋(三)、托特定理偶圖的匹配問題2 1、圖的匹配相關概念 (1)、匹配 M- 如果M是圖G的邊子集(不含環(huán)），且M中的任意兩條邊沒有共同頂點，則稱M是G的一個匹配或對集或邊獨立集。(一)、圖的匹配與貝爾熱定理 如果G中頂點v是G的匹配 M中某條邊的端點，稱它為M飽和點，否則為M非飽和點。v1 v7v6 Gv8v2v3v5v4 M1=v6v7 M2=v6v7, v1v8 M3=v6v7, v1v8, v3v4 M1,M2,M3等都是G的匹配。3 (2)、最大匹配 M- 如果M是圖G的包含邊數最多的匹配，稱M是G的一個最大匹配。特別是，若最大匹配

2、飽和了G的所有頂點，稱它為G的一個完美匹配。G的一個 最大匹配G的一個完美匹配 注：一個圖G不一定存在完美匹配。4 (3)、M交錯路- 如果M是圖G的匹配，G中一條由M中的邊和非M中的邊交錯形成的路，稱為G中的一條M交錯路。特別地，若M交錯路的起點與終點是M非飽和點，稱這種M交錯路為M可擴路。 在下圖中：v1 v7v6 Gv8v2v3v5v4 設M=v7v8 , v3v4，則： 路v6v7v8v3v4與v1v7v8v2都是M交錯路。其中后者是M可擴路。5 2、貝爾熱定理 定理1 (貝爾熱，1957) G的匹配M是最大匹配，當且僅當G不包含M可擴路。 證明：“必要性” 若G包含一條M可擴路P,則

3、可令該可擴路為： 顯然，P中M中的邊比非M中的邊少一條。于是作新的匹配M1,它當中的邊由P中非M中邊組成。M1中邊比M中多一條，這與M是G的最大匹配矛盾。 “充分性” 若不然，設M1是G的一個最大匹配，則|M1|M|。6 令H = M1M。 容易知道：GH的每個分支或者是由M1與M中邊交替組成的偶圈，或者是由M1與M中邊交替組成的路。 在每個偶圈中，M1與M中邊數相等；但因|M1|M|，所以，至少有一條路P，其起點和終點都是M非飽和點，于是，它是G的一條M可擴路。這與條件矛盾。 注：貝爾熱定理給我們提供了擴充G的匹配的思路。7(二)、偶圖的匹配與覆蓋 在日常生活，工程技術中，常常遇到求偶圖的匹

4、配問題。下面看一個例子： 1、問題的提出8 有7名研究生 A, B, C, D, E, F, G畢業(yè)尋找工作。就業(yè)處提供的公開職位是：會計師(a) ,咨詢師(b),編輯(c ),程序員(d), 記者(e), 秘書(f)和教師(g)。每名學生申請的職位如下： 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 ; 問：學生能找到理想工作嗎？ 解：如果令X=A, B, C, D, E, F, G,Y=a, b, c, d, e, f , g,X中頂點與Y

5、中頂點連線當且僅當學生申請了該工作。于是，得到反映學生和職位之間的狀態(tài)圖：9 問題轉化為求飽和X每個頂點的一個匹配！ 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定理10FEDCBAGabcdefg 定理2 (Hall定理）設G=(X, Y)是偶圖，則G存在飽和X每個頂點的匹配的充要條件是： 例1，在下面偶圖中，

6、是否存在飽和X=A, B, C, D, E, F, G的每個頂點的匹配？11FEDCBAGabcdefg 解: (1) 當S取X中單元點時，容易驗證：|N(S)|S| (2) 當S取X中二元點集時，容易驗證：|N(S)|S| (3) 當S取X中三元點集時，容易驗證：|N(S)|S| (4) 當S取X中四元點集時，若取S=A,C,D,F,則有3=|N(S)|S|=4 所以，不存在飽和X每個頂點的匹配。 下面我們證明Hall定理。12 證明：“必要性” 如果G存在飽和X每個頂點的匹配，由匹配的定義，X的每個頂點在Y中至少有一個鄰接點，所以: “充分性” 如果G是滿足條件(*)的偶圖,但是不存在飽和

7、X每個頂點的匹配。 令M*是G的一個最大匹配，但是不飽和X的頂點u.u示意圖G13 又令Z是通過M*與點u相連形成的所有M*交錯路上的點集。 因M*是最大匹配，所以u是所有交錯路上唯一的一個未飽和點。 令S=XZ , T=ZY 顯然，S-u中點與T中點在M*下配對，即： |T| = |S| -1 |S| 即： |N(S)| = |T| = |S| -1 |S| ，與條件矛盾。uTS 注: (1) G=(X,Y)存在飽和X每個頂點的匹配也常說成存在由X到Y的匹配。14 (2) Hall定理也可表述為：設G=(X,Y)是偶圖，如果存在X的一個子集S,使得|N(S)| 0)正則偶圖，則G存在完美匹配

8、。 證明：一方面，由于G是k (k0)正則偶圖,所以k|X|=k|Y|,于是得|X| = |Y|； 另一方面，對于X的任一非空子集S, 設E1與E2分別是與S和N(S)關聯的邊集，顯然有： 即： 由Hall定理，存在由X到Y的匹配.又|X| = |Y|，所以G存在完美匹配。16 例2 (1) 證明：每個k方體都有完美匹配(k大于等于2) (2) 求K2n和Kn,n中不同的完美匹配的個數。 (1) 證明一：證明每個k方體都是k正則偶圖。 事實上，由k方體的構造：k方體有2k個頂點，每個頂點可以用長度為k的二進制碼來表示，兩個頂點連線當且僅當代表兩個頂點的二進制碼只有一位坐標不同。 如果我們劃分k

9、方體的2k個頂點，把坐標之和為偶數的頂點歸入X，否則歸入Y。顯然，X中頂點互不鄰接，Y中頂點也如此。所以k方體是偶圖。 又不難知道k方體的每個頂點度數為k,所以k方體是k正則偶圖。 由推論：k方體存在完美匹配。17 (2) 我們用歸納法求K2n和Kn,n中不同的完美匹配的個數。 K2n的任意一個頂點有2n-1中不同的方法被匹配。所以K2n的不同完美匹配個數等于(2n-1)K2n-2,如此推下去，可以歸納出K2n的不同完美匹配個數為：(2n-1)! 同樣的推導方法可歸納出K n, n的不同完美匹配個數為：(n)!18 例3 證明樹至多存在一個完美匹配。 證明：若不然，設M1與M2是樹T的兩個不同的完美匹配，那么M1M2,且TM1M2每個頂點度數為2，即它存在圈，于是推出T中有圈，矛盾。19(三)、托特定理 定理4 (托特定理，1947) 圖G有完美匹配當且僅當對V的任意非空真子集S, 有： 注：o (G-S)表示奇分支數目。20 推論 (彼得森定理) 沒有割邊的3正則圖存在完美匹配。 證明：設S是V的任意一個非空真子集，G1,G2,Gk是G-S的所有奇分支。mi (1ik)表示端點分屬于S和Gi的邊數。SG1G2Gkm1m2mk21 下面分析mi