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

1、 計算機專業(yè)基礎(chǔ)課程計算機專業(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使使，且對，且對。此時常用。此時常用表示二表示二分圖分圖G。若對若對X中中 及及Y中中 一邊一邊e E，使，使e =x, y, 則稱則稱 G 為為完全二分圖完全二分圖。當(dāng)當(dāng) X = m，

2、Y = n時，完全二分圖時，完全二分圖G 記為記為。 -5-第第21講講 二分圖二分圖v示例示例(a)二分圖二分圖(b)二分圖二分圖(c)完全二分圖完全二分圖K3,3(d)非二分圖非二分圖(e)非二分圖非二分圖-6-第第21講講 二分圖二分圖v二分圖的判定二分圖的判定定理：定理：無向圖無向圖G G為二分圖的充分必要條件為為二分圖的充分必要條件為G G至少有至少有兩個頂點且其所有回路的長度為偶數(shù)。兩個頂點且其所有回路的長度為偶數(shù)。 設(shè)設(shè)G為二分圖為二分圖。由于。由于X，Y非空，故非空，故G至少有至少有兩個頂點。若兩個頂點。若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中不少于兩個頂點。假中不少于兩個頂點。假設(shè)設(shè)G連通，否則可對其每個連通分支作如下討論。連通，否則可對其每個連通分支作如下討論。 令令G的頂點集為的頂點集為V, 邊集為邊集為E, 現(xiàn)構(gòu)造

4、兩個集合現(xiàn)構(gòu)造兩個集合X,Y，使，使 = G。取。取v0 V, 置置 X = v v = v0或或v到到v0的最短通路為偶數(shù)長度的最短通路為偶數(shù)長度 Y = V-X X非空?，F(xiàn)證非空?，F(xiàn)證Y非空，且沒有任何邊的兩個端點都在非空，且沒有任何邊的兩個端點都在X或都在或都在Y中中. （1）因為）因為G連通，所以連通，所以v0至少有一個相鄰頂點，設(shè)相鄰頂點至少有一個相鄰頂點，設(shè)相鄰頂點為為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中。中。 因為因為u 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中的任意二中的任意二條邊都沒有公共端點，則說條邊都沒有公共端點，則說M M是是G G的一個的一個匹配匹配。G G的所有匹配中邊數(shù)最多的匹配稱為的所有匹配中邊數(shù)最多的匹配稱為最大匹配最大匹配。如果如果X(Y)X(Y)中任一頂點均為匹配中任一頂點均為匹配M M中邊的端點，那么稱中邊的端點，那么稱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的一個匹的一個匹配配M M中邊的端點稱為中邊的端點稱為M-M-頂點頂點，其它頂點稱為，其它頂點稱為非非M-M-頂點。頂點。 M M中的邊稱為中的邊稱為匹配邊匹配邊；其它邊稱為；其它邊稱為非匹配邊非匹配邊。設(shè)設(shè)P P是是

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

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

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

11、對Y Y中新中新標(biāo)記的結(jié)點重復(fù)上述過程。標(biāo)記的結(jié)點重復(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中的某一頂點中的某一頂點y y，它不是，它不是M-M-頂點。這時由頂點。這時由y y逆溯而上，一直到用逆溯而上，一直到用* *標(biāo)記的標(biāo)記的X X中的頂點中的頂點x x，這是一條，這是一條交替鏈交替鏈。情況情況(b)(b)：步驟：步驟(2)(2)或或(3)(3)找不到可標(biāo)記的結(jié)點，而又

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

13、標(biāo)記頂點，則算法終止，已得到最大匹配已得到最大匹配。 -18-第第21講講 二分圖二分圖v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例用匈牙利算法求下圖的一個最大匹配。用匈牙利算法求下圖的一個最大匹配。 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的的頂頂點，點，開開始回溯始回溯-20-第第21講講 二分圖二分圖找到交替鏈找到交

14、替鏈(x4,y3)置置M=x3,y1,x1,y4 ,x2,y2,x4,y3v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例(*)(*)(*)(x4)不是不是MM的的頂頂點，點，開開始回溯始回溯-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的的頂頂點，點，開開始回溯始回溯-22-第第21講講 二分圖

15、二分圖v匈牙利算法應(yīng)用示例匈牙利算法應(yīng)用示例(*)(x6)(y4)找不到可標(biāo)記頂點找不到可標(biāo)記頂點M=x4,y3,x2,y2,x5,y4,x1,y1,x3,y7已為最大匹配已為最大匹配-23-第第21講講 二分圖二分圖v匹配匹配 -相鄰頂點集相鄰頂點集圖圖G = 的頂點子集的頂點子集S V的的相鄰頂點集相鄰頂點集N(S)所有與所有與S中頂點相鄰的頂點組成的集合中頂點相鄰的頂點組成的集合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、：對每一對每一S X，有有 N(S) S -24-第第21講講 二分圖二分圖v匹配的應(yīng)用匹配的應(yīng)用某單位有四個崗位空缺：一項木器制造，三項修理水管某單位有四個崗位空缺：一項木器制造，三項修理水管道。兩個木匠和一個同時能做木工、水管工的人前來應(yīng)道。兩個木匠和一個同時能做木工、水管工的人前來應(yīng)征。能否每個人都如愿以償？征。能否每個人都如愿以償？解：解：不能。把崗位和應(yīng)征者看成頂點，把應(yīng)征者對崗位的適合不能。把崗位和應(yīng)征者看成頂點，把應(yīng)征者對崗位的適合關(guān)系看成邊時，構(gòu)成一個二分圖關(guān)系看成邊時，構(gòu)成一個二分圖。雖然崗位數(shù)目多于應(yīng)征人數(shù)，但對于兩個木匠構(gòu)成的集合雖然崗位數(shù)目多于應(yīng)征人數(shù)，但對于兩個木匠構(gòu)

17、成的集合S來來說，說，N(S)中只有一項工作，即中只有一項工作，即|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中頂點所關(guān)聯(lián)的邊的集合，中頂點所關(guān)聯(lián)的邊的集合，E2為為N(S)中頂點所關(guān)聯(lián)的邊的集合。據(jù)中頂點所關(guān)聯(lián)的邊的集合。據(jù)N(S)的定義，的定義，E1 E2，于是，于是 k N(S) = E2 E1 = k S N(S) S 因此因