離散數(shù)學(xué)：6-1-1 特殊的圖

1、第6章 特殊的圖 6.1 二部圖6.2 歐拉圖6.3 哈密頓圖6.4 平面圖 6.1 二部圖 n在實(shí)際工作中可能會(huì)遇到一類問(wèn)題：n單位有不同類型的工作空缺，也有一群填補(bǔ)空缺的應(yīng)單位有不同類型的工作空缺，也有一群填補(bǔ)空缺的應(yīng)征者，每個(gè)人能勝任其中的某些工作，如何聘任應(yīng)征征者，每個(gè)人能勝任其中的某些工作，如何聘任應(yīng)征者，使得被聘任的人得到他適合的工作崗位。者，使得被聘任的人得到他適合的工作崗位。n在在CBA聯(lián)賽中，如何把參賽隊(duì)聯(lián)賽中，如何把參賽隊(duì)配對(duì)配對(duì)？n學(xué)校有多個(gè)社團(tuán)，各學(xué)生可參加多個(gè)社團(tuán)，若社長(zhǎng)不學(xué)校有多個(gè)社團(tuán)，各學(xué)生可參加多個(gè)社團(tuán)，若社長(zhǎng)不可兼任，在什么情況下可選出合法的社長(zhǎng)？可兼任，在什

2、么情況下可選出合法的社長(zhǎng)？n 這些都涉及到匹配問(wèn)題。x y za b c d二部圖 n定義定義 設(shè)無(wú)向圖 G=,n若能將若能將V 分成分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得使得G中中的每邊的兩個(gè)端點(diǎn)都一個(gè)屬于的每邊的兩個(gè)端點(diǎn)都一個(gè)屬于V1, 另一個(gè)屬于另一個(gè)屬于V2, 則稱則稱G為為二部圖二部圖, 記為記為, 稱稱V1和和V2為為互補(bǔ)頂點(diǎn)子集互補(bǔ)頂點(diǎn)子集. 完全二部圖 n 定義定義 設(shè)無(wú)向圖 G=,n若能將若能將V 分成分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得簡(jiǎn)單使得簡(jiǎn)單圖圖G中的每邊的兩個(gè)端點(diǎn)都一個(gè)屬于中的每邊的兩個(gè)端點(diǎn)都一個(gè)屬于V1, 另一

3、個(gè)屬于另一個(gè)屬于V2, 且且V1中每個(gè)頂點(diǎn)均與中每個(gè)頂點(diǎn)均與V2中每個(gè)頂點(diǎn)都相鄰中每個(gè)頂點(diǎn)都相鄰, 則稱則稱G為為完完全二部圖全二部圖, 記為記為Kr,s, 其中其中r =|V1|, s=|V2|. n 注意注意: n 階零圖為二部圖階零圖為二部圖. K3,3K2,3二部圖的判別法 例例: : 下述各圖是否是二部圖下述各圖是否是二部圖? ? 定理定理 無(wú)無(wú)向圖向圖G=是二部圖當(dāng)且僅當(dāng)是二部圖當(dāng)且僅當(dāng)G中中無(wú)奇無(wú)奇長(zhǎng)度的回路。長(zhǎng)度的回路。 不是不是匹配 設(shè)設(shè)G=n 匹配匹配(邊獨(dú)立集邊獨(dú)立集): 任任2條邊均條邊均不相鄰不相鄰的邊子集。的邊子集。n 極大匹配極大匹配: 添加任一條邊后都不再是匹配

4、的邊子集。添加任一條邊后都不再是匹配的邊子集。n 最大匹配最大匹配: 邊數(shù)最多的匹配。邊數(shù)最多的匹配。n匹配數(shù)匹配數(shù): : 最大匹配中的邊數(shù)最大匹配中的邊數(shù), 記為記為 1 n 例求下面例求下面 3個(gè)圖中匹配數(shù)個(gè)圖中匹配數(shù)n匹配數(shù)匹配數(shù) 依次為依次為3, 3, 4. 匹配 設(shè)M為G中一個(gè)匹配n vi與vj被M匹配: (vi,vj)Mn v為M飽和點(diǎn): M中有邊與v關(guān)聯(lián)n v為M非飽和點(diǎn): M中沒(méi)有邊與v關(guān)聯(lián)n M為完美匹配: G的每個(gè)頂點(diǎn)都是M飽和點(diǎn) n 例 關(guān)于M1, a,b,e,d是飽和點(diǎn) f,c是非飽和點(diǎn) M1不是完美匹配 M2是完美匹配是完美匹配二部圖中的匹配 n定義定義 設(shè)設(shè)G=為二

5、部圖為二部圖, n|V1| |V2|, M是是G中最大匹配中最大匹配, 若若V1中頂點(diǎn)全是中頂點(diǎn)全是M飽和飽和點(diǎn)點(diǎn), 則稱則稱M為為G中中V1到到V2的的完備匹配完備匹配.n 當(dāng)當(dāng)|V1|=|V2|時(shí)時(shí), 完備匹配變成完備匹配變成完美匹配完美匹配.n例：圖中紅邊組成各圖的一個(gè)匹配，(1)(2)(3) 是完備匹配是完備匹配, , 但不是完美匹配但不是完美匹配是最大匹配是最大匹配不是不是完備匹配完備匹配, , 圖中無(wú)完備匹配圖中無(wú)完備匹配是完美匹配是完美匹配Hall定理 nHall定理：定理：設(shè)二部圖設(shè)二部圖G=中，中，|V1| |V2|. G中存在從中存在從V1到到V2的的完備匹配完備匹配當(dāng)且僅

6、當(dāng)當(dāng)且僅當(dāng)V1中任意中任意k個(gè)頂點(diǎn)至少與個(gè)頂點(diǎn)至少與V2中的中的k個(gè)頂點(diǎn)個(gè)頂點(diǎn)相鄰相鄰(k=1,2,|V1|)n 由Hall定理不難證明, 下圖(2)沒(méi)有完備匹配. (1)(2)(3)相異性條件相異性條件二部圖完備匹配判定的充分條件 n定理定理 設(shè)二部圖設(shè)二部圖G=中中, 若若t 0, 使得使得nV1中每個(gè)頂點(diǎn)中每個(gè)頂點(diǎn)至少至少關(guān)聯(lián)關(guān)聯(lián) t 條邊，條邊，nV2中每個(gè)頂點(diǎn)中每個(gè)頂點(diǎn)至多至多關(guān)聯(lián)關(guān)聯(lián) t 條邊，條邊，則則G中存在中存在V1到到V2的完備匹配。的完備匹配。 (1)(2)(3)完備匹配的條件完備匹配的條件 V1中中k個(gè)頂點(diǎn)個(gè)頂點(diǎn)至少至少關(guān)聯(lián)關(guān)聯(lián) kt 條邊，這條邊，這 kt 條邊條邊至

7、少至少關(guān)聯(lián)關(guān)聯(lián) V2中中k個(gè)頂點(diǎn)，個(gè)頂點(diǎn)， 即即V1中任意中任意k個(gè)頂點(diǎn)至少鄰接個(gè)頂點(diǎn)至少鄰接V2中的中的k個(gè)頂點(diǎn)個(gè)頂點(diǎn). t 條件條件二部圖的應(yīng)用實(shí)例1 n 某課題組要從a, b, c, d, e 這5人中派3人分別到上海、廣州、香港去開(kāi)會(huì)。已知：a只想去上海，只想去上海，b只想去廣州，只想去廣州，c, d, e都表示想去廣州或香港都表示想去廣州或香港. 問(wèn)該課題組在滿足個(gè)人要求的條件下，共有幾種派遣方案？ 解：解： 令G=, 其中 V1=s, g, x, V2=a, b, c, d, e, E=(u,v) | u V1, v V2, v想去想去u,其中其中s, g, x分別表示上海、廣州和香港分別表示上海、廣州和香港. G 滿足滿足相異性條件相異性條件，因而可給，因而可給 出派遣方案，出派遣方案， 相當(dāng)于求相當(dāng)于求完備匹配數(shù)完備匹配數(shù)， 共有共有9種派遣方案種派遣方案二部圖的應(yīng)用實(shí)例2n 證明：在88的國(guó)際象棋棋盤的一條主對(duì)角線上移去兩端的方格后，所得棋盤不能用12的長(zhǎng)方形不重疊地填滿。n 證：作二部圖G=如下： V1=v | v 位于白格內(nèi)位于白格內(nèi), V2=v | v 位于黑格位于黑格內(nèi)內(nèi), E=(u,v)|