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

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

2、單圖, 且且V1中每個(gè)中每個(gè)頂點(diǎn)均與頂點(diǎn)均與V2中每個(gè)頂點(diǎn)都相鄰中每個(gè)頂點(diǎn)都相鄰, 則稱(chēng)則稱(chēng)G為為完全二部圖完全二部圖, 記為記為Kr,s, 其中其中r=|V1|, s=|V2|. K23K334二部圖的判別法二部圖的判別法 定理定理 無(wú)向圖無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)是二部圖當(dāng)且僅當(dāng)G中無(wú)奇圈中無(wú)奇圈 例例 下述各圖都是二部圖下述各圖都是二部圖 5二部圖的判別定理定理定理8.1 無(wú)向圖無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)是二部圖當(dāng)且僅當(dāng)G中無(wú)奇長(zhǎng)度中無(wú)奇長(zhǎng)度的回路的回路證證 必要性必要性. 設(shè)設(shè)G=是二部圖是二部圖, 每條邊只能從每條邊只能從V1到到V2, 或從或從V2到到V1, 故任何回路必為偶長(zhǎng)度故

3、任何回路必為偶長(zhǎng)度.充分性充分性. 不妨設(shè)不妨設(shè)G至少有一條邊且連通至少有一條邊且連通. 取任一頂點(diǎn)取任一頂點(diǎn)u, 令令 V1=v | v V d(v,u)為偶數(shù)為偶數(shù), V2=v | v V d(v,u)為為奇數(shù)奇數(shù)則則V1 V2=V, V1 V2=. 先證先證V1中任意兩點(diǎn)不相鄰中任意兩點(diǎn)不相鄰. 假設(shè)假設(shè)存在存在s,t V1, e=(s,t) E. 設(shè)設(shè) 1, 2分別是分別是u到到s,t的短程線的短程線, 則則 1 e 2是一條回路是一條回路, 其長(zhǎng)度為奇數(shù)其長(zhǎng)度為奇數(shù), 與假設(shè)矛盾與假設(shè)矛盾. 同理同理可可證證V2中任意兩點(diǎn)不相鄰中任意兩點(diǎn)不相鄰. 6實(shí)例非二部圖非二部圖非二部圖非二部

4、圖7匹配匹配 設(shè)設(shè)G=,匹配匹配(邊獨(dú)立集邊獨(dú)立集): 任任2條邊均不相鄰的邊子集條邊均不相鄰的邊子集極大匹配極大匹配: 添加任一條邊后都不再是匹配的匹配添加任一條邊后都不再是匹配的匹配最大匹配最大匹配: 邊數(shù)最多的匹配邊數(shù)最多的匹配匹配數(shù)匹配數(shù): 最大匹配中的邊數(shù)最大匹配中的邊數(shù), 記為記為 1 例例 下述下述3個(gè)圖的匹配數(shù)個(gè)圖的匹配數(shù) 依次為依次為3, 3, 4. 8匹配匹配 (續(xù)續(xù))設(shè)設(shè)M為為G中一個(gè)匹配中一個(gè)匹配vi與與vj被被M匹配匹配: (vi,vj) Mv為為M飽和點(diǎn)飽和點(diǎn): M中有邊與中有邊與v關(guān)聯(lián)關(guān)聯(lián)v為為M非飽和點(diǎn)非飽和點(diǎn): M中沒(méi)有邊與中沒(méi)有邊與v關(guān)聯(lián)關(guān)聯(lián)M為完美匹配為完

5、美匹配: G的每個(gè)頂點(diǎn)都是的每個(gè)頂點(diǎn)都是M飽和點(diǎn)飽和點(diǎn) 例例 關(guān)于關(guān)于M1, a,b,e,d是飽和點(diǎn)是飽和點(diǎn) f,c是非飽和點(diǎn)是非飽和點(diǎn) M1不是完美匹配不是完美匹配 M2是完美匹配是完美匹配M1M29二部圖中的匹配二部圖中的匹配 定義定義 設(shè)設(shè)G=為二部圖為二部圖, |V1| |V2|, M是是G中最中最大匹配大匹配, 若若V1中頂點(diǎn)全是中頂點(diǎn)全是M飽和點(diǎn)飽和點(diǎn), 則稱(chēng)則稱(chēng)M為為G中中V1到到V2的的完備匹配完備匹配. 當(dāng)當(dāng)|V1|=|V2|時(shí)時(shí), 完備匹配變成完美完備匹配變成完美匹配匹配.(1)(2)(3)例例 圖中紅邊組成各圖的一個(gè)匹配，圖中紅邊組成各圖的一個(gè)匹配，(1)為完備的為完備的

6、, 但不是完但不是完美的美的; (2)不是完備的不是完備的, 其實(shí)其實(shí)(2)中無(wú)完備匹配中無(wú)完備匹配; (3) 是完美的是完美的.10Hall定理定理 定理定理(Hall定理定理) 設(shè)二部圖設(shè)二部圖G=中，中，|V1| |V2|. G中存中存在從在從V1到到V2的完備匹配當(dāng)且僅當(dāng)?shù)耐陚淦ヅ洚?dāng)且僅當(dāng)V1中任意中任意k 個(gè)頂點(diǎn)至少與個(gè)頂點(diǎn)至少與V2中的中的k個(gè)頂點(diǎn)相鄰個(gè)頂點(diǎn)相鄰(k=1,2,|V1|).由由Hall定理不難證明定理不難證明, 上一頁(yè)圖上一頁(yè)圖(2)沒(méi)有完備匹配沒(méi)有完備匹配. 定理定理 設(shè)二部圖設(shè)二部圖G=中中, 如果存在如果存在t 1, 使得使得V1中每個(gè)中每個(gè)頂點(diǎn)至少關(guān)聯(lián)頂點(diǎn)至少

7、關(guān)聯(lián) t 條邊條邊, 而而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊，則條邊，則G中存在中存在V1到到V2的完備匹配的完備匹配. Hall定理中的條件稱(chēng)為定理中的條件稱(chēng)為“相異性條件相異性條件”, 第二個(gè)定理中的條第二個(gè)定理中的條件件稱(chēng)為稱(chēng)為 t 條件條件. 滿(mǎn)足滿(mǎn)足 t 條件的二部圖一定滿(mǎn)足相異性條件條件的二部圖一定滿(mǎn)足相異性條件.11實(shí)例例例1 某中學(xué)有某中學(xué)有3個(gè)課外活動(dòng)小組個(gè)課外活動(dòng)小組:數(shù)學(xué)組數(shù)學(xué)組, 計(jì)算機(jī)組和生物計(jì)算機(jī)組和生物組組. 有趙有趙,錢(qián)錢(qián),孫孫,李李,周周5名學(xué)生名學(xué)生, 問(wèn)分別在下述問(wèn)分別在下述3種情況下種情況下, 能能否選出否選出3人各任一個(gè)組的組長(zhǎng)人各任一個(gè)組

8、的組長(zhǎng)?(1) 趙趙, 錢(qián)為數(shù)學(xué)組成員錢(qián)為數(shù)學(xué)組成員, 趙趙,孫孫,李為計(jì)算機(jī)組成員李為計(jì)算機(jī)組成員, 孫孫,李李,周為生物組成員周為生物組成員.(2) 趙為數(shù)學(xué)組成員趙為數(shù)學(xué)組成員, 錢(qián)錢(qián),孫孫,李為計(jì)算機(jī)組成員李為計(jì)算機(jī)組成員, 錢(qián)錢(qián),孫孫,李李,周周為生物組成員為生物組成員.(3) 趙為數(shù)學(xué)組和計(jì)算機(jī)組成員趙為數(shù)學(xué)組和計(jì)算機(jī)組成員, 錢(qián)錢(qián),孫孫,李李,周為生物組成員周為生物組成員.12實(shí)例(續(xù))解解(1),(2)有多種方案有多種方案, (3) 不可能不可能(1)數(shù)數(shù)計(jì)計(jì)生生趙趙 錢(qián)錢(qián) 孫孫 李李 周周(2)數(shù)數(shù)計(jì)計(jì)生生趙趙 錢(qián)錢(qián) 孫孫 李李 周周(3)數(shù)數(shù)計(jì)計(jì)生生趙趙 錢(qián)錢(qián) 孫孫 李李

9、周周13一個(gè)應(yīng)用實(shí)例一個(gè)應(yīng)用實(shí)例 例例 某課題組要從某課題組要從a, b, c, d, e 5人中派人中派3人分別到上海、廣州、人分別到上海、廣州、香港去開(kāi)會(huì)香港去開(kāi)會(huì). 已知已知a只想去上海，只想去上海，b只想去廣州，只想去廣州，c, d, e都都 表示想去廣州或香港表示想去廣州或香港. 問(wèn)該課題組在滿(mǎn)足個(gè)人要求的條件問(wèn)該課題組在滿(mǎ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分別表示上海、廣州和香港分別表示上海

10、、廣州和香港. G如圖所示如圖所示. G 滿(mǎn)足相異性條件，因而可給滿(mǎn)足相異性條件，因而可給出派遣方案，共有出派遣方案，共有9種派遣方案種派遣方案(請(qǐng)給出這請(qǐng)給出這9種方案種方案). 148.2 歐拉圖歐拉圖歐拉通路歐拉通路歐拉回路歐拉回路歐拉圖歐拉圖半歐拉圖半歐拉圖 15哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題 歐拉圖是能一筆畫(huà)出的邊不重復(fù)的回路歐拉圖是能一筆畫(huà)出的邊不重復(fù)的回路. . 16歐拉圖歐拉圖 歐拉通路歐拉通路: 圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的通路圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的通路. 歐拉回路歐拉回路: 圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的回路圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條

11、邊一次的回路.歐拉圖歐拉圖: 有歐拉回路的圖有歐拉回路的圖.半歐拉圖半歐拉圖: 有歐拉通路而無(wú)歐拉回路的圖有歐拉通路而無(wú)歐拉回路的圖.幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：上述定義對(duì)無(wú)向圖和有向圖都適用上述定義對(duì)無(wú)向圖和有向圖都適用.規(guī)定平凡圖為歐拉圖規(guī)定平凡圖為歐拉圖.歐拉通路是簡(jiǎn)單通路歐拉通路是簡(jiǎn)單通路, 歐拉回路是簡(jiǎn)單回路歐拉回路是簡(jiǎn)單回路.環(huán)不影響圖的歐拉性環(huán)不影響圖的歐拉性. 17歐拉圖歐拉圖( (續(xù)續(xù)) )例例 圖中圖中, (1), (4)為歐拉圖為歐拉圖; (2), (5)為半歐拉圖為半歐拉圖; (3)，(6)既不既不 是歐拉圖是歐拉圖, 也不是半歐拉圖也不是半歐拉圖. 在在(3), (6)中各至

12、少加幾條邊才能成為歐拉圖中各至少加幾條邊才能成為歐拉圖?18歐拉圖的判別法歐拉圖的判別法 定理定理 無(wú)向圖無(wú)向圖G為歐拉圖當(dāng)且僅當(dāng)為歐拉圖當(dāng)且僅當(dāng)G連通且無(wú)奇度頂點(diǎn)連通且無(wú)奇度頂點(diǎn). 無(wú)向圖無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn)連通且恰有兩個(gè)奇度頂點(diǎn). 定理定理 有向圖有向圖D是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)D連通且每個(gè)頂點(diǎn)的入度都連通且每個(gè)頂點(diǎn)的入度都等于出度等于出度. 有向圖有向圖D具有歐拉通路當(dāng)且僅當(dāng)具有歐拉通路當(dāng)且僅當(dāng)D連通且恰有兩個(gè)奇度頂連通且恰有兩個(gè)奇度頂點(diǎn)點(diǎn), 其中一個(gè)入度比出度大其中一個(gè)入度比出度大1, 另一個(gè)出度比入度大另一個(gè)出度比入度大1, 其

13、余其余頂點(diǎn)的入度等于出度頂點(diǎn)的入度等于出度.19實(shí)例實(shí)例例例1 哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題例例2 下面兩個(gè)圖都是歐拉圖下面兩個(gè)圖都是歐拉圖. 從從A點(diǎn)出發(fā)點(diǎn)出發(fā), 如何一次成功地走出一條歐拉回路來(lái)？如何一次成功地走出一條歐拉回路來(lái)？ 20實(shí)例無(wú)歐拉通路無(wú)歐拉通路歐拉圖歐拉圖歐拉圖歐拉圖有歐拉通路有歐拉通路非歐拉圖非歐拉圖有歐拉通路有歐拉通路非歐拉圖非歐拉圖無(wú)歐拉通路無(wú)歐拉通路21實(shí)例歐拉圖歐拉圖無(wú)歐拉通路無(wú)歐拉通路無(wú)歐拉通路無(wú)歐拉通路有歐拉通路有歐拉通路無(wú)歐拉回路無(wú)歐拉回路無(wú)歐拉通路無(wú)歐拉通路有歐拉通路有歐拉通路無(wú)歐拉回路無(wú)歐拉回路228.3 哈密頓圖哈密頓圖 哈密頓通路哈密頓通路哈密頓

14、回路哈密頓回路哈密頓圖哈密頓圖半哈密頓圖半哈密頓圖 23哈密頓周游世界問(wèn)題哈密頓周游世界問(wèn)題 24哈密頓回路與哈密頓通路哈密頓通路哈密頓通路: : 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路. .哈密頓回路哈密頓回路: : 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路. .哈密頓圖哈密頓圖: : 具有哈密頓回路的圖具有哈密頓回路的圖. .半哈密頓圖半哈密頓圖: : 具有哈密頓通路而無(wú)哈密頓回路的圖具有哈密頓通路而無(wú)哈密頓回路的圖. .說(shuō)明：說(shuō)明：哈密頓通路是哈密頓通路是初級(jí)通路初級(jí)通路哈密頓回路是哈密頓回路是初級(jí)回路初級(jí)回路有哈密頓通路不一定有

15、哈密頓回路有哈密頓通路不一定有哈密頓回路環(huán)與平行邊不影響圖的哈密頓性環(huán)與平行邊不影響圖的哈密頓性25哈密頓圖的必要條件定理定理8.6 若無(wú)向圖若無(wú)向圖G=是哈密頓圖是哈密頓圖, 則對(duì)于則對(duì)于V的任意的任意非空真子集非空真子集V1均有均有 p(G V1) |V1|.證證 設(shè)設(shè)C為為G中一條哈密頓回路中一條哈密頓回路, 有有p(C V1) |V1|. 又因?yàn)橛忠驗(yàn)镃 G, 故故 p(G V1) p(C V1) |V1|. 例如例如 當(dāng)當(dāng)rs時(shí)時(shí), Kr,s不是哈密頓圖不是哈密頓圖推論推論 有割點(diǎn)的圖不是哈密頓圖有割點(diǎn)的圖不是哈密頓圖26實(shí)例例例2 證明下述各圖不是哈密頓圖證明下述各圖不是哈密頓圖:

16、(a)(b)(c)(c) 中存在哈密頓通路中存在哈密頓通路27實(shí)例例例3 證明右圖不是哈密頓圖證明右圖不是哈密頓圖證證 假設(shè)存在一條哈密頓回路假設(shè)存在一條哈密頓回路, a,f,g是是2度頂點(diǎn)度頂點(diǎn), 邊邊(a,c), (f,c)和和(g,c)必在這條哈密頓回路上必在這條哈密頓回路上,從而點(diǎn)從而點(diǎn)c出現(xiàn)出現(xiàn)3次次, 矛盾矛盾.abcde fg此外此外, 該圖滿(mǎn)足定理該圖滿(mǎn)足定理6.10的條件的條件, 這表明此條件是必要、這表明此條件是必要、而不充分的而不充分的.又又, 該圖有哈密頓通路該圖有哈密頓通路.28存在哈密頓回路(通路)的充分條件定理定理8.7 設(shè)設(shè)G是是n(n 3)階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)

17、單圖, 若任意兩個(gè)不相鄰若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于的頂點(diǎn)的度數(shù)之和大于等于n 1, 則則G中存在哈密頓通路中存在哈密頓通路;若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n, 則則G中中存在哈密頓回路存在哈密頓回路, 即即G為哈密頓圖為哈密頓圖.推論推論 設(shè)設(shè)G是是n(n 3)階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖, 若若(G) n/2, 則則G是哈是哈密頓圖密頓圖當(dāng)當(dāng)n 3時(shí)時(shí), Kn是哈密頓圖是哈密頓圖; 當(dāng)當(dāng)r=s 2時(shí)時(shí), Kr,s是哈密頓圖是哈密頓圖.定理定理8.8 設(shè)設(shè)D是是n(n 2)階有向圖階有向圖, 若略去所有邊的方向后若略去所有邊的方向后所得無(wú)向圖中含子圖所得無(wú)向圖中含子圖Kn, 則則D中有哈密頓通路中有哈密頓通路.29應(yīng)用例例4 有有7個(gè)人個(gè)人, A會(huì)講英語(yǔ)會(huì)講英語(yǔ), B會(huì)講英語(yǔ)和漢語(yǔ)會(huì)講英語(yǔ)和漢語(yǔ), C會(huì)講英語(yǔ)、會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)意大利語(yǔ)和俄語(yǔ)