離散第5講 容斥原理與排列組合31-32

1、 計(jì)算機(jī)專業(yè)基礎(chǔ)課程計(jì)算機(jī)專業(yè)基礎(chǔ)課程 授課人：梁妍授課人：梁妍-2-第第21講講 二分圖二分圖vPowerPoint Template_Sub 1二分圖二分圖2平面圖平面圖3樹樹v二分圖二分圖離散數(shù)學(xué)離散數(shù)學(xué)第第2121講講 Page 138 to 142 Page 138 to 142-4-第第21講講 二分圖二分圖v基本概念基本概念定義：定義：無向圖無向圖G=稱為稱為，如果有非空，如果有非空集合集合X，Y使使，且對(duì)，且對(duì)。此時(shí)常用。此時(shí)常用表示二表示二分圖分圖G。若對(duì)若對(duì)X中中 及及Y中中 一邊一邊e E，使，使e =x, y, 則稱則稱 G 為為完全二分圖完全二分圖。當(dāng)當(dāng) X = m，

2、Y = n時(shí)，完全二分圖時(shí)，完全二分圖G 記為記為。 -5-第第21講講 二分圖二分圖v示例示例(a)二分圖二分圖(b)二分圖二分圖(c)完全二分圖完全二分圖K3,3(d)非二分圖非二分圖(e)非二分圖非二分圖-6-第第21講講 二分圖二分圖v二分圖的判定二分圖的判定定理：定理：無向圖無向圖G G為二分圖的充分必要條件為為二分圖的充分必要條件為G G至少有至少有兩個(gè)頂點(diǎn)且其所有回路的長度為偶數(shù)。兩個(gè)頂點(diǎn)且其所有回路的長度為偶數(shù)。 設(shè)設(shè)G為二分圖為二分圖。由于。由于X，Y非空，故非空，故G至少有至少有兩個(gè)頂點(diǎn)。若兩個(gè)頂點(diǎn)。若C為為G中任一長度為中任一長度為k 的回路，令的回路，令 C = ( v

3、0,v1,v2,vk-1,v k = v0 ) 其中諸其中諸vi ( i = 0,1,k)必定相間出現(xiàn)于必定相間出現(xiàn)于X 及及Y 中，顯然中，顯然 v0,v2,v4, vk = v0 X v1,v3,v5, vk-1 Y 因此因此k 必為偶數(shù)，從而必為偶數(shù)，從而C 中有偶數(shù)條邊。中有偶數(shù)條邊。 -7-第第21講講 二分圖二分圖v二分圖的判定二分圖的判定 設(shè)設(shè)G的所有回路具有偶數(shù)長度，且的所有回路具有偶數(shù)長度，且G中不少于兩個(gè)頂點(diǎn)。假中不少于兩個(gè)頂點(diǎn)。假設(shè)設(shè)G連通，否則可對(duì)其每個(gè)連通分支作如下討論。連通，否則可對(duì)其每個(gè)連通分支作如下討論。 令令G的頂點(diǎn)集為的頂點(diǎn)集為V, 邊集為邊集為E, 現(xiàn)構(gòu)造

4、兩個(gè)集合現(xiàn)構(gòu)造兩個(gè)集合X,Y，使，使 = G。取。取v0 V, 置置 X = v v = v0或或v到到v0的最短通路為偶數(shù)長度的最短通路為偶數(shù)長度 Y = V-X X非空?，F(xiàn)證非空?，F(xiàn)證Y非空，且沒有任何邊的兩個(gè)端點(diǎn)都在非空，且沒有任何邊的兩個(gè)端點(diǎn)都在X或都在或都在Y中中. （1）因?yàn)椋┮驗(yàn)镚連通，所以連通，所以v0至少有一個(gè)相鄰頂點(diǎn)，設(shè)相鄰頂點(diǎn)至少有一個(gè)相鄰頂點(diǎn)，設(shè)相鄰頂點(diǎn)為為v1，那么，那么v1 Y（為什么？為什么？）；故）；故Y不空。不空。 -8-第第21講講 二分圖二分圖v二分圖的判定二分圖的判定 （2）設(shè)有邊）設(shè)有邊u, v, 使使u X，v X。證明一定存在奇數(shù)長度的證明一定存在

5、奇數(shù)長度的回路回路，與題設(shè)矛盾。故不可能有邊與題設(shè)矛盾。故不可能有邊u, v使使u, v均在均在X中。中。 因?yàn)橐驗(yàn)閡 X，v X，所以，所以v0到到u有偶數(shù)長度的通路，或有偶數(shù)長度的通路，或u = v0；v0到到v有偶數(shù)長度的通路，或有偶數(shù)長度的通路，或v = v0。這樣，無論何種情況，。這樣，無論何種情況，連同邊連同邊u, v均有一條從均有一條從v0到到v0的奇數(shù)長度的閉的擬路徑，在的奇數(shù)長度的閉的擬路徑，在此閉的擬路徑中此閉的擬路徑中一定存在奇數(shù)長度的回路一定存在奇數(shù)長度的回路(定理定理7.5)。同理可。同理可證證“”。uvv0v0v0-9-第第21講講 二分圖二分圖v匹配匹配定義定義:

6、 : 設(shè)設(shè)G = G = 為二分圖，為二分圖，M M E E，如果，如果M M中的任意二中的任意二條邊都沒有公共端點(diǎn)，則說條邊都沒有公共端點(diǎn)，則說M M是是G G的一個(gè)的一個(gè)匹配匹配。G G的所有匹配中邊數(shù)最多的匹配稱為的所有匹配中邊數(shù)最多的匹配稱為最大匹配最大匹配。如果如果X(Y)X(Y)中任一頂點(diǎn)均為匹配中任一頂點(diǎn)均為匹配M M中邊的端點(diǎn)，那么稱中邊的端點(diǎn)，那么稱M M為為X(Y) X(Y) - -完全匹配完全匹配。若若M M既是既是X-X-完全匹配又是完全匹配又是Y-Y-完全匹配，則稱完全匹配，則稱M M為為G G的的完全匹配完全匹配。 -10-第第21講講 二分圖二分圖v匹配的性質(zhì)匹配

7、的性質(zhì)1) 最大匹配總是存在但未必唯一；最大匹配總是存在但未必唯一； X(或或Y) -完全匹配及完全匹配及G的完全匹配必定是最大的的完全匹配必定是最大的, 反之不然；反之不然； X(或或Y) -完全匹配未必存在，若存在則為最大匹配。完全匹配未必存在，若存在則為最大匹配。-11-第第21講講 二分圖二分圖v求取最大匹配求取最大匹配術(shù)語：術(shù)語：設(shè)設(shè)G = 為二分圖，為二分圖，M是是G的一個(gè)匹的一個(gè)匹配配M M中邊的端點(diǎn)稱為中邊的端點(diǎn)稱為M-M-頂點(diǎn)頂點(diǎn)，其它頂點(diǎn)稱為，其它頂點(diǎn)稱為非非M-M-頂點(diǎn)。頂點(diǎn)。 M M中的邊稱為中的邊稱為匹配邊匹配邊；其它邊稱為；其它邊稱為非匹配邊非匹配邊。設(shè)設(shè)P P是是

8、G G中以中以v vk k為起點(diǎn)，為起點(diǎn)，v vh h為終點(diǎn)的一條通路，如果為終點(diǎn)的一條通路，如果v vh h、v vk k均為非均為非M-M-頂點(diǎn)，且頂點(diǎn)，且P P中非匹配邊與匹配邊交替出現(xiàn)，則稱中非匹配邊與匹配邊交替出現(xiàn)，則稱P P為為G G關(guān)于匹配關(guān)于匹配M M的一條的一條交替鏈交替鏈。當(dāng)某邊。當(dāng)某邊(u,v)(u,v)的兩端點(diǎn)均的兩端點(diǎn)均為非為非M-M-頂點(diǎn)時(shí)，頂點(diǎn)時(shí)，(u,v)(u,v)也稱為交替鏈。也稱為交替鏈。 -12-第第21講講 二分圖二分圖v交替鏈交替鏈M-M-頂點(diǎn)頂點(diǎn)非非M-M-頂點(diǎn)頂點(diǎn)匹配邊匹配邊非匹配邊非匹配邊-13-第第21講講 二分圖二分圖v交替鏈交替鏈交替鏈交替

9、鏈-14-第第21講講 二分圖二分圖v交替鏈交替鏈多了一條匹配邊！多了一條匹配邊！-15-第第21講講 二分圖二分圖v求取最大匹配求取最大匹配匈牙利算法匈牙利算法算法算法基本思想基本思想不斷尋找交替鏈，每找到一條交不斷尋找交替鏈，每找到一條交替鏈即將其中的匹配邊和非匹配邊對(duì)換，從而增加替鏈即將其中的匹配邊和非匹配邊對(duì)換，從而增加一條匹配邊，直至從初始匹配擴(kuò)充為最大匹配一條匹配邊，直至從初始匹配擴(kuò)充為最大匹配-16-第第21講講 二分圖二分圖v匈牙利算法匈牙利算法 (1) (1) 首先首先用用( (* *) )標(biāo)記標(biāo)記X X中的所有中的所有非非M-M-頂點(diǎn)頂點(diǎn)，然后交替進(jìn)行下列，然后交替進(jìn)行下列

10、步驟步驟(2)(2)和和(3)(3)。(2) (2) 選取一個(gè)剛標(biāo)記過的選取一個(gè)剛標(biāo)記過的X X中的頂點(diǎn)設(shè)為中的頂點(diǎn)設(shè)為x xi i，用用(x(xi i) )去去標(biāo)記標(biāo)記Y Y中的與中的與x xi i通過非匹配邊相聯(lián)的并且還沒有被標(biāo)記過的端點(diǎn)通過非匹配邊相聯(lián)的并且還沒有被標(biāo)記過的端點(diǎn)y y，對(duì)對(duì)X X中新標(biāo)記的結(jié)點(diǎn)重復(fù)上述過程。中新標(biāo)記的結(jié)點(diǎn)重復(fù)上述過程。(3) (3) 選一個(gè)選一個(gè)Y Y中新標(biāo)記的頂點(diǎn)設(shè)為中新標(biāo)記的頂點(diǎn)設(shè)為y yj j，用用(y(yj j) )去去標(biāo)記標(biāo)記X X中的與中的與y yj j通過匹配邊相聯(lián)的，并且還沒有標(biāo)記過的結(jié)點(diǎn)通過匹配邊相聯(lián)的，并且還沒有標(biāo)記過的結(jié)點(diǎn)x x，對(duì)，

11、對(duì)Y Y中新中新標(biāo)記的結(jié)點(diǎn)重復(fù)上述過程。標(biāo)記的結(jié)點(diǎn)重復(fù)上述過程。 (2)(3)(2)(3)交替執(zhí)行，這一過程稱為標(biāo)記過程交替執(zhí)行，這一過程稱為標(biāo)記過程。標(biāo)記到最。標(biāo)記到最后可能出現(xiàn)下列后可能出現(xiàn)下列兩種情況兩種情況：-17-第第21講講 二分圖二分圖v匈牙利算法匈牙利算法 情況情況(a)(a)：標(biāo)記到：標(biāo)記到Y(jié) Y中的某一頂點(diǎn)中的某一頂點(diǎn)y y，它不是，它不是M-M-頂點(diǎn)。這時(shí)由頂點(diǎn)。這時(shí)由y y逆溯而上，一直到用逆溯而上，一直到用* *標(biāo)記的標(biāo)記的X X中的頂點(diǎn)中的頂點(diǎn)x x，這是一條，這是一條交替鏈交替鏈。情況情況(b)(b)：步驟：步驟(2)(2)或或(3)(3)找不到可標(biāo)記的結(jié)點(diǎn)，而又

12、不是找不到可標(biāo)記的結(jié)點(diǎn)，而又不是(a)(a)，這時(shí)這時(shí)M M已是最大匹配了。已是最大匹配了。(4) (4) 當(dāng)當(dāng)(2)(2)、(3)(3)步驟中斷于情況步驟中斷于情況(a)(a)時(shí)，將所得交替鏈中的匹配時(shí)，將所得交替鏈中的匹配邊與非匹配邊交換即可得到一新的匹配邊與非匹配邊交換即可得到一新的匹配MM，這一匹配比原匹，這一匹配比原匹配配M M多一條邊多一條邊。回到步驟。回到步驟(1)(1)，并消除一切現(xiàn)有標(biāo)記。，并消除一切現(xiàn)有標(biāo)記。(5) (5) 對(duì)一切可能，對(duì)一切可能，(2)(2)、(3)(3)步驟均中斷于情況步驟均中斷于情況(b)(b)，或步驟，或步驟(1)(1)無可標(biāo)記頂點(diǎn)，則算法終止，無可

13、標(biāo)記頂點(diǎn)，則算法終止，已得到最大匹配已得到最大匹配。 -18-第第21講講 二分圖二分圖v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例用匈牙利算法求下圖的一個(gè)最大匹配。用匈牙利算法求下圖的一個(gè)最大匹配。 M=x1,y1,x2,y2-19-第第21講講 二分圖二分圖找到交替鏈找到交替鏈(x3,y1,x1,y4)，其中匹配邊，其中匹配邊x1,y1，非匹配邊非匹配邊x3,y1,x1,y4置置M=x3,y1,x1,y4 ,x2,y2v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例(*)(*)(*)(*)(x3)(y1)(x1)不是不是MM的的頂頂點(diǎn)，點(diǎn)，開開始回溯始回溯-20-第第21講講 二分圖二分圖找到交替鏈找到交

14、替鏈(x4,y3)置置M=x3,y1,x1,y4 ,x2,y2,x4,y3v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例(*)(*)(*)(x4)不是不是MM的的頂頂點(diǎn)，點(diǎn)，開開始回溯始回溯-21-第第21講講 二分圖二分圖找到交替鏈找到交替鏈(x5,y4,x1,y1,x3,y7)其中匹配邊其中匹配邊x1,y4,x3,y1;非匹配邊非匹配邊x5,y4, x1,y1, x3,y7置置M=x4,y3,x2,y2,x5,y4,x1,y1,x3,y7v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例(*)(*)(x5)(y4)(x1)(y1)(x3)不是不是MM的的頂頂點(diǎn)，點(diǎn)，開開始回溯始回溯-22-第第21講講 二分圖

15、二分圖v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例(*)(x6)(y4)找不到可標(biāo)記頂點(diǎn)找不到可標(biāo)記頂點(diǎn)M=x4,y3,x2,y2,x5,y4,x1,y1,x3,y7已為最大匹配已為最大匹配-23-第第21講講 二分圖二分圖v匹配匹配 -相鄰頂點(diǎn)集相鄰頂點(diǎn)集圖圖G = 的頂點(diǎn)子集的頂點(diǎn)子集S V的的相鄰頂點(diǎn)集相鄰頂點(diǎn)集N(S)所有與所有與S中頂點(diǎn)相鄰的頂點(diǎn)組成的集合中頂點(diǎn)相鄰的頂點(diǎn)組成的集合N(S) = v v V u e(u Se Ee = u, v)N(S) = v u e(u Se = u, v)Hall定理：定理：設(shè)圖設(shè)圖G = 。G有有X-完全匹配完全匹配的充分必要條件是：的充分必要條件是

16、：對(duì)每一對(duì)每一S X，有有 N(S) S -24-第第21講講 二分圖二分圖v匹配的應(yīng)用匹配的應(yīng)用某單位有四個(gè)崗位空缺：一項(xiàng)木器制造，三項(xiàng)修理水管某單位有四個(gè)崗位空缺：一項(xiàng)木器制造，三項(xiàng)修理水管道。兩個(gè)木匠和一個(gè)同時(shí)能做木工、水管工的人前來應(yīng)道。兩個(gè)木匠和一個(gè)同時(shí)能做木工、水管工的人前來應(yīng)征。能否每個(gè)人都如愿以償？征。能否每個(gè)人都如愿以償？解：解：不能。把崗位和應(yīng)征者看成頂點(diǎn)，把應(yīng)征者對(duì)崗位的適合不能。把崗位和應(yīng)征者看成頂點(diǎn)，把應(yīng)征者對(duì)崗位的適合關(guān)系看成邊時(shí)，構(gòu)成一個(gè)二分圖關(guān)系看成邊時(shí)，構(gòu)成一個(gè)二分圖。雖然崗位數(shù)目多于應(yīng)征人數(shù)，但對(duì)于兩個(gè)木匠構(gòu)成的集合雖然崗位數(shù)目多于應(yīng)征人數(shù)，但對(duì)于兩個(gè)木匠構(gòu)

17、成的集合S來來說，說，N(S)中只有一項(xiàng)工作，即中只有一項(xiàng)工作，即|N(S)|S|，沒有，沒有X-完全匹配。完全匹配。木器木器水管水管水管水管水管水管木匠木匠 木匠木匠 水管工水管工 -25-第第21講講 二分圖二分圖v匹配的應(yīng)用匹配的應(yīng)用k-正則二分圖（正則二分圖（k 0）有完全匹配。）有完全匹配。證明：設(shè)證明：設(shè)G = 為為k-正則二分圖，那么正則二分圖，那么kX = E = k Y 從而從而 X = Y 。設(shè)設(shè)S為為X的任一子集，的任一子集，E1為為S中頂點(diǎn)所關(guān)聯(lián)的邊的集合，中頂點(diǎn)所關(guān)聯(lián)的邊的集合，E2為為N(S)中頂點(diǎn)所關(guān)聯(lián)的邊的集合。據(jù)中頂點(diǎn)所關(guān)聯(lián)的邊的集合。據(jù)N(S)的定義，的定義，E1 E2，于是，于是 k N(S) = E2 E1 = k S N(S) S 因此因