偶圖的匹配問題

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

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

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

4、配問題。下面看一個(gè)例子： 1、問題的提出8 有7名研究生 A, B, C, D, E, F, G畢業(yè)尋找工作。就業(yè)處提供的公開職位是：會(huì)計(jì)師(a) ,咨詢師(b),編輯(c ),程序員(d), 記者(e), 秘書(f)和教師(g)。每名學(xué)生申請(qǐng)的職位如下： 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

5、中頂點(diǎn)連線當(dāng)且僅當(dāng)學(xué)生申請(qǐng)了該工作。于是，得到反映學(xué)生和職位之間的狀態(tài)圖：9 問題轉(zhuǎn)化為求飽和X每個(gè)頂點(diǎn)的一個(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 ; FEDCBAGabcdefg 需要解決的問題是: (1) 匹配是否存在？(2) 如何求出匹配？ 2、偶圖匹配存在性判定-Hall定理10FEDCBAGabcdefg 定理2 (Hall定理）設(shè)G=(X, Y)是偶圖，則G存在飽和X每個(gè)頂點(diǎn)的匹配的充要條件是： 例1，在下面偶圖中，

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

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

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

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