離散數(shù)學(xué) 一些特殊的圖

1、1,第8章 一些特殊的圖,8.1 二部圖8.2 歐拉圖8.3 哈密頓圖8.4 平面圖,2,8.1 二部圖,二部圖完全二部圖匹配極大匹配最大匹配匹配數(shù)完備匹配,3,二部圖,定義 設(shè)無向圖 G=, 若能將V 分成V1 和 V2 (V1?V2=V, V1?V2=?), 使得G中的每條邊的兩個端點都一個屬于V1, 另一個屬于V2, 則稱G為二部圖(二分圖), 記為, 稱V1和V2為互補頂點子集. 又若G是簡單圖, 且

2、V1中每個頂點均與V2中每個頂點都相鄰, 則稱G為完全二部圖, 記為Kr,s, 其中r=|V1|, s=|V2|.,(a),(b),以上兩個圖都是二部圖，其中(b)圖是完全二部圖。,4,例 完全二分圖Km, n=(V1,V2,E)共有 多少條邊?,,解 因為V1中每個頂點都與V2 中每個頂點相鄰接,所以V1 中每個頂點關(guān)聯(lián) |V2| = n 條邊; 而V1 中有m個頂點, 所以Km, n共有mn條邊。,5,二部圖的判別法

3、,定理 無向圖G=是二部圖當且僅當G中 無奇圈 。即G中的每一條回路都是由偶 數(shù)條邊組成。,證明：當G(V1,V2)是二部圖時，G中的任意一條回路的各邊必須往返于V1,V2之間，因此其回路必由偶數(shù)條邊組成。,6,例：判斷下圖是否為二部圖。,解：圖中的每一條回路都是由偶數(shù)條邊組成。所以此圖為二部圖。,→,7,匹配,設(shè)G = (V, E)是具有互補頂點子集V1和V2的二分圖, M ? E, 若M中任意兩條邊都不相鄰

4、, 則稱M為G中的匹配(對集)。如果M是G的匹配, 且M中再加入任何一條邊就都是不匹配了, 則稱M為極大匹配。最大匹配: 邊數(shù)最多的匹配匹配數(shù): 最大匹配中的邊數(shù), 記為?1。,8,如在下圖中，如果用a1,a2,a3,a4表示4位教師，b1,b2,b3表示三門待開的課程。當某位教師能開某門課程時，則把它們的對應(yīng)頂點用邊連接起來。如果規(guī)定一個教師只能擔(dān)任一門課程，那么匹配M就表示了一種排課方案。為了使排課方案能最大限度地作到“各盡

5、其能”，這就是最大匹配的概念。,9,匹配 (續(xù)),設(shè)M為G中一個匹配ai與bj被M匹配: (ai,bj)?Mai為M飽和點: M中有邊與ai關(guān)聯(lián)ai為M非飽和點: M中沒有邊與ai關(guān)聯(lián)M為完美匹配: G的每個頂點都是M飽和點,10,定義 設(shè)G=為二部圖, |V1|?|V2|, M是G中最大匹配, 若V1中頂點全是M飽和點, 則稱M為G中V1到V2的完備匹配. 當|V1|=|V2|時, 完備匹配變成完美匹配.,,(1),(2

6、),(3),圖中紅邊組成各圖的一個匹配，(1)為完備的, 但不是完美的; (2)不是完備的, 其實(2)中無完備匹配; (3) 是完美的.,匹配 (續(xù)),例：如圖,11,例 求下圖的飽和點，并判斷哪個圖是完美匹配？,解：關(guān)于M1, a,b,e,d是飽和點f,c是非飽和點 M1不是完美匹配 M2是完美匹配，所以M2中 a,b,c,d,e,f都是飽和點。,12,設(shè)G=?V1,V2,E?是二部圖，M是G的一個匹配，如果對G的

7、任意匹配M′，都有|M′|≤|M|，則M為G的最大匹配 為了尋求二部圖的最大匹配，以下引進交替通路和增長通路兩個概念。,定義 設(shè)G=?V1,V2,E?是二部圖，M是G的匹配，P是G中的一條路，如果P是由G中屬于M的邊和不屬于M的邊交替組成，則稱P為G的M交替通路。如果交替通路的始點和終點都是M的非飽和點，則稱為G的M增長通路。,13,例如，在圖中匹配M={(a1,b2), (a2,b3), (a3,b5)}， 路

8、 L1：a1b2a2b3a3， L2：a2b3a3b5a4， L3：b1a3b5a4， L4：b1a1b2a2b3a3b5a4 都是M的交替通路，其中后兩條交替通路L3和L4的始點和終點都是M的非飽和點，所以這兩條路是M增長通路。,14,設(shè)G=?V1,V2,E?是二部圖，M是G的一個匹配，P是G中的一條M增長通路。把P中所有屬于M的邊從M中去掉，而把P中所有不屬于M的邊添加

9、到M中，得到一個新的邊集M′，則M′也是一個匹配，其所含邊數(shù)比匹配M所含的邊數(shù)多1。,15,例如在圖中，把M增長通路L3：b1a3b5a4中屬于M的邊(a3,b5) 從M中去掉，而把L3中不屬于M的邊(a3,b1)和(a4,b5) 添加到M中，得到一個新的邊集M′=?(a1,b2),(a2,b3),(a3,b1), (a4,b5)?，顯然M′也是匹配且M′的邊數(shù)比M的邊數(shù)多l(xiāng)，即|M′|＝|M|+1。,16,由此可見，利用增長通路可以增

10、加匹配所含的邊數(shù)。不斷地尋求G的增長通路，直到再也找不到新的增長通路，就可得到一個最大匹配。將這個結(jié)論寫成下列的定理。 定理 設(shè)G=?V1,V2,E?是二部圖，M為G的最大匹配的充分必要條件是G中不存在M增長通路。,證明：設(shè)M為G的最大匹配，下證G中不存在M可擴路。 如果G中存在一條M可擴路，則可以得到比M的邊數(shù)多1的匹配，所以M不是最大匹配，矛盾。所以G中不存在M可擴路。 設(shè)G中不存在M可擴路，下證

11、M為G的最大匹配。 設(shè)M1是最大匹配，證明|M|=|M1|。 考察屬于M而不屬于M1和屬于M1而不屬于M中的邊，由這些邊連同它們的端點一起構(gòu)成G的子圖H。,17,在子圖H中，任一頂點至多與M中的一條邊關(guān)聯(lián)且與M1中一條邊關(guān)聯(lián)。因而任一頂點的度數(shù)是1或2。故H的連通分支是一條路，或者是一個回路。 如果H的連通分支是一條路P，則它是M交替路，也是M1交替路。如果P的兩個端點均與M中的邊關(guān)聯(lián)，則P是M1可擴路

12、。由假設(shè)知，M1是最大匹配，所以，不存在M1可擴路，得到矛盾。如果P的兩個端點均與M1的邊關(guān)聯(lián)，那么P是一條M可擴路與題設(shè)矛盾。故P只能是一個端點與M中的邊關(guān)聯(lián)，另一個端點與M1中的邊關(guān)聯(lián)，這樣P中屬于M的邊數(shù)與屬于M1的邊數(shù)相等。,18,如果H的連通分支是一個回路，回路中的邊交替地屬于M和M1，因而屬于M的邊數(shù)與屬于M1的邊數(shù)相等。 從上面可以看到，H中屬于M的邊與屬于M1的邊的數(shù)目相等。再加上既屬于M又屬于M1的邊，

13、可以得出：M中的邊數(shù)與M1中的邊數(shù)相等。所以M是最大匹配。,19,有了上面的準備以后，就可以進一步討論如何在二部圖中求最大匹配的問題。 設(shè)G=?V1,V2,E?是二部圖，通常先作G的一個匹配M，再看V1中有沒有M的非飽和點。如果沒有，那么M肯定是最大匹配；如果有，就從這些點出發(fā)找M增長通路。由M增長通路作出一個更大的匹配。所以，在G中求最大匹配的關(guān)鍵是尋找M增長通路。,20,尋找增長通路的一個有效方法是標記法，其基本思想

14、如下： 設(shè)G=?V1,V2,E?是二部圖，在G中作一個匹配M，用(*)標記V1中所有M的非飽和點，然后交替地進行以下①和②兩步：,②選一個V2的新標記過的頂點，比如說bi，用(bi)標記通過M中的邊與bi鄰接且尚未標記過的V1的所有頂點。對V2所有新標記過的頂點重復(fù)這一過程。,①選一個V1的新標記過的頂點，比如說ai，用(ai)標記不通過M中的邊與ai鄰接且尚未標記過的V2的所有頂點。對V1所有新標記過的頂點重復(fù)這一過程

15、。,21,直至標記到一個V2中的M的非飽和點。從該頂點倒向追蹤到標記有(*)的頂點，就得到了一個M增長通路。把M增長通路中所有屬于M的邊從M中去掉，而把M可擴路中所有不屬于M的邊添加到M中，得到一個新的匹配M′且其所含邊數(shù)比匹配M所含的邊數(shù)多1。對M′重復(fù)上述過程，……，直到G中已不存在增長通路，此時的匹配就是最大匹配。,22,【例】如圖是二部圖，求其最大匹配。,23,【例】如圖是二部圖，求其最大匹配。,24,解：取二部圖的一個匹配M=

16、 {(a3,b1), (a5,b2)}。用(*)標記V1中所有M的非飽和點a1, a2, a4。 ①選V1的新標記過的頂點a1，用(a1)標記不通過M的邊與a1鄰接且尚未標記過的V2的頂點b1；類似地用(a2)標記b2。 ②選V2的新標記過的頂點b1，用(b1)標記通過M的邊與b1鄰接且尚未標記過的V1的頂點a3；類似地用(b2)標記a5。,25,③選V1的新標記過的頂點a3，因為不存在不通過M的邊與

17、a3鄰接的V2的頂點，所以不用(a3)標記V2的頂點；用(a5)標記b3或b4，假定用(a5)標記b3。如圖所示。 b3是M的非飽和點，標記結(jié)束。 從b3倒向追蹤到標記有(*)的頂點，就得到了M增長通路：a4b2a5b3或a2b2a5b3，取后者。把M增長通路a2b2a5b3中的邊(a5,b2)從M中去掉，而把(a2,b2)和(a5,b3)添加到M中得到新的匹配M′={(a3,b1), (a2,b2),

18、 (a5,b3)}，如圖9.61所示。,26,27,對匹配M′= {(a3,b1), (a2,b2), (a5,b3) }再用標記法： 用(*)標記V1中所有M′的非飽和點a1和 a4。 ①選V1的新標記過的頂點a1，用(a1)標記不通過M′的邊與a1鄰接且尚未標記過的V2的所有頂點b1；再用(a4)標記b2。 ②選V2的新標記過的頂點b1，用(b1)標記通過M′的邊與b1鄰接且尚未標記

19、過的V1的所有頂點a3；再用(b2)標記a2。 ③選V1的新標記過的頂點a2和a3，V2中已無可標記的頂點。 圖中已不存在增長通路，所以M′就是最大匹配。,28,【例】求下圖的最大匹配。,29,解：取二部圖圖9.62的一個匹配 M={(a2,b2), (a3,b3), (a5,b5)}。用(*)標記V1中所有M的非飽和點a1, a4。 ①選V1的新標記過的頂點a1，用(a1)標記b2

20、和b3。 ②選V2的新標記過的頂點b2和b3，用(b2)標記a2，用(b3)標記a3。 ③選V1的新標記過的頂點a2，用(a2)標記b1, b4和b5。 由于b1和b4都是M的非飽和點，說明找到了M可擴路。 它們是：a1b2a2b4和a1b2a2b1。選前者，把邊(a2,b2)從M中去掉，而把(a1,b2)和(a2,b4)添加到M中，得到新的匹配M′=?(a1,b2),(a2,b4),(

21、a3,b3), (a5,b5)?，如圖9.63所示。 對于匹配M′= {(a1,b2),(a2,b4),(a3,b3), (a5,b5)}重復(fù)上述過程，已找不到M′可擴路。所以M′就是最大匹配。,30,31,Hall定理,定理(Hall定理) 設(shè)二部圖G=中，|V1|?|V2|. G中存在從V1到V2的完備匹配當且僅當V1中任意k 個頂點至少與V2中的k個頂點相鄰(k=1,2,…,|V1|).由Hall定理不難證明, 上一

22、頁圖(2)沒有完備匹配. Hall定理中的條件稱為“相異性條件”,32,定理 設(shè)二部圖G=中, 如果存在t?1, 使得(1)V1中每個頂點至少關(guān)聯(lián) t 條邊, (2)而V2中每個頂點至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配. (充分條件)證明 如果(1)成立, 則與V1中k (1≤k≤|V1|)個頂點相關(guān)聯(lián)的邊的總數(shù), 至少是kt條。根據(jù)(2)這些邊至少要與V2中k個頂點相關(guān)聯(lián)。這就得出V1中每k (1≤k≤|V1|)個頂

23、點, 至少鄰接到到V2中k個頂點。定理中的條件稱為 t 條件. 滿足 t 條件的二部圖一定滿足相異性條件.,33,因此，當給出一個二分圖后。 判斷G中存在從V1到V2的完備匹配方法:先找出V１中的每個結(jié)點的度數(shù)，令r＝minv∈V1{d(v)}。再找出V２中的每個結(jié)點的度數(shù)，令R＝maxv∈V2 {d(v)}。若r≥R，則問題有解，取t為r即可。但這只是充分條件，若不滿足，則還要用充要條件來判斷。,34,圖9.64中的二部圖滿足t的

24、條件。其中t=3。因此在圖9.64中存在V1到V2的完備匹配。,35,一個應(yīng)用實例,例 某課題組要從a, b, c, d, e 5人中派3人分別到上海、廣州、香港去開會. 已知a只想去上海，b只想去廣州，c, d, e都表示想去廣州或香港. 問該課題組在滿足個人要求的條件下，共有幾種派遣方案？ 解 令G=, 其中V1={s, g, x}, V2={a, b, c, d, e}, E={(u,v) | u?V1,

25、v?V2, v想去u},其中s, g, x分別表示上海、廣州和香港. G如圖所示. G 滿足相異性條件，因而可給出派遣方案，共有9種派遣方案(請給出這9種方案).,,36,練習(xí)：1.某單位按編制有7個空缺：p1, p2, …..p7.有10個申請者： a1, a2, …..a10.他們合格的工作崗位依次為：, {p1,p5,p6},{p2,p6,p7},{p3,p4},{p1,p5}{p6,p7},{p3},{p2,

26、p3}, {p1,p3},{p1},{p5}，如何安排他們的工作，使有工作的人最多。,2.某單位有6個未婚女子L1,L2,…,L6和6個未婚男子g1,g2,…,g6,每個人都有意中人，L1:{g1,g2,g4},L2:{g3,g5},L3:{g1,g2,g4},L4:{g2,g5,g6},L5:{g5,g6},L6:{g3,g5,g6};而g1:{L1,L3,L6},g2:{L2,L4,L6},g3:{L2,L5},g4:{L1,L3