07879離散數(shù)學(xué)-屈婉玲(圖論)8.1-3

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

2、簡(jiǎn)單圖, 且且V1中每個(gè)頂點(diǎn)均與中每個(gè)頂點(diǎn)均與V2中每個(gè)頂點(diǎn)都相中每個(gè)頂點(diǎn)都相鄰鄰, 則稱則稱G為為完全二部圖完全二部圖, 記為記為Kr,s, 其中其中r=|V1|, s=|V2|. 注意注意: n 階零圖為二部圖階零圖為二部圖. 4二部圖的判別法二部圖的判別法 定理定理 無(wú)向圖無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)是二部圖當(dāng)且僅當(dāng)G中無(wú)奇圈中無(wú)奇圈 例例 下述各圖都是二部圖下述各圖都是二部圖 5匹配匹配 設(shè)設(shè)G=,匹配匹配(邊獨(dú)立集邊獨(dú)立集): 任任2條邊均不相鄰的邊子集條邊均不相鄰的邊子集極大匹配極大匹配: 添加任一條邊后都不再是匹配的匹配添加任一條邊后都不再是匹配的匹配最大匹配最大匹配: 邊數(shù)最多的

3、匹配邊數(shù)最多的匹配匹配數(shù)匹配數(shù): 最大匹配中的邊數(shù)最大匹配中的邊數(shù), 記為記為 1 例例 3個(gè)圖的匹配數(shù)個(gè)圖的匹配數(shù) 依次為依次為3, 3, 4. 6匹配匹配 (續(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為完美匹配為完美匹配: 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是完美匹配是完美匹配M1M27二部圖中的匹配二部圖中

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

5、|. 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)至少關(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定理中的條件稱為定理中的條件稱為“相異性條件相異性條件”, 第二個(gè)定理中的條第二個(gè)定

6、理中的條件件稱為稱為 t 條件條件. 滿足滿足 t 條件的二部圖一定滿足相異性條件條件的二部圖一定滿足相異性條件.9一個(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)該課題組在滿足個(gè)人要求的條件下，問(wèn)該課題組在滿足個(gè)人要求的條件下，共有幾種派遣方案？共有幾種派遣方案？ 解解 令令G=, 其中其中V1=s, g, x, V2=a, b, c, d, e, E=(u,

7、v) | u V1, v V2, v想去想去u,其中其中s, g, x分別表示上海、廣州和香港分別表示上海、廣州和香港. G如圖所示如圖所示. G 滿足相異性條件，因而可給滿足相異性條件，因而可給出派遣方案，共有出派遣方案，共有9種派遣方案種派遣方案(請(qǐng)給出這請(qǐng)給出這9種方案種方案). 108.2 歐拉圖歐拉圖歐拉通路歐拉通路歐拉回路歐拉回路歐拉圖歐拉圖半歐拉圖半歐拉圖 11哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題 歐拉圖是能一筆畫(huà)出的邊不重復(fù)的回路歐拉圖是能一筆畫(huà)出的邊不重復(fù)的回路. . 12歐拉圖歐拉圖 歐拉通路歐拉通路: 圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的通路圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊

8、一次的通路. 歐拉回路歐拉回路: 圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的回路圖中行遍所有頂點(diǎn)且恰好經(jīng)過(guò)每條邊一次的回路.歐拉圖歐拉圖: 有歐拉回路的圖有歐拉回路的圖.半歐拉圖半歐拉圖: 有歐拉通路而無(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)不影響圖的歐拉性. 13歐拉圖歐拉圖( (續(xù)續(xù)) )例例 圖中圖中, (1), (4)為歐拉圖為歐拉圖; (2), (5)為半歐拉圖為半歐拉圖

9、; (3)，(6)既不既不 是歐拉圖是歐拉圖, 也不是半歐拉圖也不是半歐拉圖. 在在(3), (6)中各至少加幾條邊才能成為歐拉圖中各至少加幾條邊才能成為歐拉圖?14歐拉圖的判別法歐拉圖的判別法 定理定理 無(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è)奇度頂連通且恰有兩

10、個(gè)奇度頂點(diǎn)點(diǎn), 其中一個(gè)入度比出度大其中一個(gè)入度比出度大1, 另一個(gè)出度比入度大另一個(gè)出度比入度大1, 其余其余頂點(diǎn)的入度等于出度頂點(diǎn)的入度等于出度.15實(shí)例實(shí)例例例1 哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題例例2 下面兩個(gè)圖都是歐拉圖下面兩個(gè)圖都是歐拉圖. 從從A點(diǎn)出發(fā)點(diǎn)出發(fā), 如何一次成功地走出一條歐拉回路來(lái)？如何一次成功地走出一條歐拉回路來(lái)？ 168.3 哈密頓圖哈密頓圖 哈密頓通路哈密頓通路哈密頓回路哈密頓回路哈密頓圖哈密頓圖半哈密頓圖半哈密頓圖 17哈密頓周游世界問(wèn)題哈密頓周游世界問(wèn)題 18哈密頓圖的定義哈密頓圖的定義哈密頓通路哈密頓通路: : 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路經(jīng)過(guò)圖中所

11、有頂點(diǎn)一次且僅一次的通路. .哈密頓回路哈密頓回路: : 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路. .哈密頓圖哈密頓圖: : 具有哈密頓回路的圖具有哈密頓回路的圖. .半哈密頓圖半哈密頓圖: : 具有哈密頓通路而無(wú)哈密頓回路的圖具有哈密頓通路而無(wú)哈密頓回路的圖. . 幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：平凡圖是哈密頓圖平凡圖是哈密頓圖. .哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路. .環(huán)與平行邊不影響圖的哈密頓性環(huán)與平行邊不影響圖的哈密頓性. .19實(shí)例實(shí)例例例 圖中圖中, (1), (2)是哈密頓圖是哈密頓圖; (3) 是半哈密頓圖是

12、半哈密頓圖.(4)既不是哈密頓圖既不是哈密頓圖, 也不是半哈密頓圖，為什么？也不是半哈密頓圖，為什么？ 20無(wú)向哈密頓圖的一個(gè)必要條件無(wú)向哈密頓圖的一個(gè)必要條件 定理定理 設(shè)無(wú)向圖設(shè)無(wú)向圖G=是哈密頓圖是哈密頓圖, 則對(duì)于任意則對(duì)于任意V1 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|. 幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明定理中的條件是哈密頓圖的必要條件定理中的條件是哈密頓圖的必要條件, 但不是充分條件但不是充分條件.可利用該定理判斷某些圖不是哈密頓圖可

13、利用該定理判斷某些圖不是哈密頓圖. 由定理可知由定理可知, Kr,s當(dāng)當(dāng)s r+1時(shí)不是哈密頓圖時(shí)不是哈密頓圖. 當(dāng)當(dāng)r 2時(shí)時(shí), Kr,r是哈密頓圖是哈密頓圖, 而而Kr,r+1是半哈密頓圖是半哈密頓圖. 21實(shí)例實(shí)例例例 設(shè)設(shè)G為為n階無(wú)向連通簡(jiǎn)單圖階無(wú)向連通簡(jiǎn)單圖, 若若G中有割點(diǎn)或橋中有割點(diǎn)或橋, 則則G不是哈密頓圖不是哈密頓圖.證證 (1) 設(shè)設(shè)v為割點(diǎn)為割點(diǎn), 則則p(G v) 2|v|=1. 根據(jù)定理根據(jù)定理, G不是哈密頓圖不是哈密頓圖. (2) 若若G是是K2(K2有橋有橋), 它顯然不是哈密頓圖它顯然不是哈密頓圖. 除除K2外外, 其他的有橋連通圖均有割點(diǎn)其他的有橋連通圖均

14、有割點(diǎn). 由由(1), 得證得證G不是不是哈密頓圖哈密頓圖.22無(wú)向哈密頓圖的一個(gè)充分條件無(wú)向哈密頓圖的一個(gè)充分條件 定理定理 設(shè)設(shè)G是是n階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖, 若任意兩個(gè)不相鄰的頂點(diǎn)若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于的度數(shù)之和大于等于n 1, 則則G中存在哈密頓通路中存在哈密頓通路. 當(dāng)當(dāng)n 3時(shí)時(shí), 若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于于等于n, 則則G中存在哈密頓回路中存在哈密頓回路, 從而從而G為哈密頓為哈密頓圖圖. 23哈密頓通路哈密頓通路(回路回路)的存在性的存在性(續(xù)續(xù))定理中的條件是存在哈密頓通路定理中的條件是存在哈密頓通路(回

15、路回路)的充分條的充分條件件, 但不是必要條件但不是必要條件.例如例如, 設(shè)設(shè)G為長(zhǎng)度為為長(zhǎng)度為n 1(n 4)的路徑的路徑, 它不滿足定理它不滿足定理中哈密頓通路的條件中哈密頓通路的條件, 但它顯然存在哈密頓通路但它顯然存在哈密頓通路.設(shè)設(shè)G是長(zhǎng)為是長(zhǎng)為n的圈的圈, 它不滿足定理中哈密頓回路的條它不滿足定理中哈密頓回路的條件件, 但它顯然是哈密頓圖但它顯然是哈密頓圖.由定理由定理, 當(dāng)當(dāng)n 3時(shí)時(shí), Kn均為哈密頓圖均為哈密頓圖.判斷某圖是否為哈密頓圖至今還是一個(gè)難題判斷某圖是否為哈密頓圖至今還是一個(gè)難題 24判斷是否是哈密頓圖判斷是否是哈密頓圖的可行方法的可行方法n觀察出一條哈密頓回路觀察

16、出一條哈密頓回路 例如例如 右圖右圖(周游世界問(wèn)題周游世界問(wèn)題)中紅中紅邊給出一條哈密頓回路邊給出一條哈密頓回路, 故它故它是哈密頓圖是哈密頓圖.注意注意, 此圖不滿足定理的條件此圖不滿足定理的條件. n滿足充分條件滿足充分條件例如例如 當(dāng)當(dāng)n 3時(shí)時(shí), Kn中任何兩個(gè)不同的頂點(diǎn)中任何兩個(gè)不同的頂點(diǎn) u,v, 均均有有d(u)+d(v) = 2(n 1) n, 所以所以Kn為哈密頓圖為哈密頓圖. 25判斷是否是哈判斷是否是哈 密頓圖密頓圖的可行方法的可行方法(續(xù)續(xù))例例 1/4國(guó)際象棋盤(pán)國(guó)際象棋盤(pán)(4 4方格方格)上的上的跳馬問(wèn)題跳馬問(wèn)題: 馬是否能恰好經(jīng)過(guò)馬是否能恰好經(jīng)過(guò)每一個(gè)方格一次后回到

17、原處每一個(gè)方格一次后回到原處?解解 每個(gè)方格看作一個(gè)頂點(diǎn)每個(gè)方格看作一個(gè)頂點(diǎn), 2個(gè)個(gè)頂點(diǎn)之間有邊當(dāng)且僅當(dāng)馬可以從一個(gè)方格跳到另一個(gè)方格頂點(diǎn)之間有邊當(dāng)且僅當(dāng)馬可以從一個(gè)方格跳到另一個(gè)方格, 得到得到16階圖階圖G, 如左圖紅邊所示如左圖紅邊所示. 取取V1=a, b, c, d, 則則p(G V1) = 6 |V1|, 見(jiàn)右圖見(jiàn)右圖. 由定理由定理, 圖中無(wú)哈密頓回路圖中無(wú)哈密頓回路, 故問(wèn)題無(wú)解故問(wèn)題無(wú)解.在國(guó)際象棋盤(pán)在國(guó)際象棋盤(pán)(8 8)上上, 跳馬問(wèn)題是否有解跳馬問(wèn)題是否有解? 不滿足必要條件不滿足必要條件26應(yīng)用實(shí)例應(yīng)用實(shí)例例例 某次國(guó)際會(huì)議某次國(guó)際會(huì)議8人參加，已知每人至少與其余人參加，已知每人至少與其余7人中人中的的4人有共同語(yǔ)言，問(wèn)服務(wù)員能否將他們安排在同一張人有共同語(yǔ)言，問(wèn)服務(wù)員能否將他們安排在同一張圓桌就座，使得每個(gè)人都能與兩邊的人交談？圓桌就座，使得每個(gè)人都能與兩邊的人交談？解解 圖是描述事物之間關(guān)系的最好的手段之一圖是描述事物之間關(guān)系的最好的手段之一.