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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、 {(a3,b1), (a5,b2)}。用(*)標(biāo)記V1中所有M的非飽和點(diǎn)a1, a2, a4。 ①選V1的新標(biāo)記過(guò)的頂點(diǎn)a1，用(a1)標(biāo)記不通過(guò)M的邊與a1鄰接且尚未標(biāo)記過(guò)的V2的頂點(diǎn)b1；類(lèi)似地用(a2)標(biāo)記b2。 ②選V2的新標(biāo)記過(guò)的頂點(diǎn)b1，用(b1)標(biāo)記通過(guò)M的邊與b1鄰接且尚未標(biāo)記過(guò)的V1的頂點(diǎn)a3；類(lèi)似地用(b2)標(biāo)記a5。,25,③選V1的新標(biāo)記過(guò)的頂點(diǎn)a3，因?yàn)椴淮嬖诓煌ㄟ^(guò)M的邊與

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

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

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

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

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

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

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

24、條件。其中t=3。因此在圖9.64中存在V1到V2的完備匹配。,35,一個(gè)應(yīng)用實(shí)例,例 某課題組要從a, b, c, d, e 5人中派3人分別到上海、廣州、香港去開(kāi)會(huì). 已知a只想去上海，b只想去廣州，c, d, e都表示想去廣州或香港. 問(wèn)該課題組在滿(mǎn)足個(gè)人要求的條件下，共有幾種派遣方案？ 解 令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 滿(mǎn)足相異性條件，因而可給出派遣方案，共有9種派遣方案(請(qǐng)給出這9種方案).,,36,練習(xí)：1.某單位按編制有7個(gè)空缺：p1, p2, …..p7.有10個(gè)申請(qǐng)者： 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個(gè)未婚女子L1,L2,…,L6和6個(gè)未婚男子g1,g2,…,g6,每個(gè)人都有意中人，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