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

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

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

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

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

6、 : 設設G = G = 為二分圖，為二分圖，M M E E，如果，如果M M中的任意二中的任意二條邊都沒有公共端點，則說條邊都沒有公共端點，則說M M是是G G的一個的一個匹配匹配。G G的所有匹配中邊數最多的匹配稱為的所有匹配中邊數最多的匹配稱為最大匹配最大匹配。如果如果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匹配的性質匹配

7、的性質1) 最大匹配總是存在但未必唯一；最大匹配總是存在但未必唯一； X(或或Y) -完全匹配及完全匹配及G的完全匹配必定是最大的的完全匹配必定是最大的, 反之不然；反之不然； X(或或Y) -完全匹配未必存在，若存在則為最大匹配。完全匹配未必存在，若存在則為最大匹配。-11-第第21講講 二分圖二分圖v求取最大匹配求取最大匹配術語：術語：設設G = 為二分圖，為二分圖，M是是G的一個匹的一個匹配配M M中邊的端點稱為中邊的端點稱為M-M-頂點頂點，其它頂點稱為，其它頂點稱為非非M-M-頂點。頂點。 M M中的邊稱為中的邊稱為匹配邊匹配邊；其它邊稱為；其它邊稱為非匹配邊非匹配邊。設設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關于匹配關于匹配M M的一條的一條交替鏈交替鏈。當某邊。當某邊(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) 首先首先用用( (* *) )標記標記X X中的所有中的所有非非M-M-頂點頂點，然后交替進行下列，然后交替進行下列

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

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

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

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

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

15、二分圖v匈牙利算法應用示例匈牙利算法應用示例(*)(x6)(y4)找不到可標記頂點找不到可標記頂點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定理：定理：設圖設圖G = 。G有有X-完全匹配完全匹配的充分必要條件是：的充分必要條件是

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

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