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

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

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

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

4、的邊子集。添加任一條邊后都不再是匹配的邊子集。n 最大匹配最大匹配: 邊數(shù)最多的匹配。邊數(shù)最多的匹配。n匹配數(shù)匹配數(shù): : 最大匹配中的邊數(shù)最大匹配中的邊數(shù), 記為記為 1 n 例求下面例求下面 3個圖中匹配數(shù)個圖中匹配數(shù)n匹配數(shù)匹配數(shù) 依次為依次為3, 3, 4. 匹配 設(shè)M為G中一個匹配n vi與vj被M匹配: (vi,vj)Mn v為M飽和點(diǎn): M中有邊與v關(guān)聯(lián)n v為M非飽和點(diǎn): M中沒有邊與v關(guān)聯(lián)n M為完美匹配: 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|時時, 完備匹配變成完備匹配變成完美匹配完美匹配.n例：圖中紅邊組成各圖的一個匹配，(1)(2)(3) 是完備匹配是完備匹配, , 但不是完美匹配但不是完美匹配是最大匹配是最大匹配不是不是完備匹配完備匹配, , 圖中無完備匹配圖中無完備匹配是完美匹配是完美匹配Hall定理 nHall定理：定理：設(shè)二部圖設(shè)二部圖G=中，中，|V1| |V2|. G中存在從中存在從V1到到V2的的完備匹配完備匹配當(dāng)且僅

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

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