離散數(shù)學(xué)幾種特殊的圖

離散數(shù)學(xué)幾種特殊的圖第1頁(yè)/共35頁(yè)2哥尼斯堡七橋問(wèn)題哥尼斯堡城（現(xiàn)在俄羅斯）在18世紀(jì)屬東普魯士，它位于普雷格爾（Pregel）河畔，河中有兩個(gè)島，通過(guò)七座橋彼此相聯(lián)，如下圖：

。。。。ABCD第2頁(yè)/共35頁(yè)3內(nèi)容提要

8.1二部圖

8.2歐拉圖與哈密爾頓圖

8.3平面圖

第3頁(yè)/共35頁(yè)48.1二部圖

引例：今有4個(gè)工人a1,a2,a3,a4,4項(xiàng)任務(wù)b1,b2,b3,b4。已知工人a1熟悉任務(wù)b1,b2,b3,a2熟悉b2,b3,a3只熟悉b4,a4熟悉b3和b4。問(wèn)如何分配工人，才能使每人都有任務(wù)，且每項(xiàng)任務(wù)都有人來(lái)完成？其實(shí)，只要以

V={a1,a2,a3,a4,b1,b2,b3,b4}為頂點(diǎn)集，若ai熟悉bj,就在ai和bj之間連邊，得邊集E,構(gòu)成無(wú)向圖G=<V,E>,如下圖所示。第4頁(yè)/共35頁(yè)58.1二部圖由圖顯而易見(jiàn)，分配a1去完成b1,a2去完成B2,a3去完成b4，a4去完成B3就能滿足要求。在此圖中，a1,a2,a3,a4彼此不相鄰，b1,b2,b3,b4也彼此不相鄰。像這樣的圖，稱它為二部圖。第5頁(yè)/共35頁(yè)68.1二部圖定義8.1.1

若能將無(wú)向圖的頂點(diǎn)集V分成兩個(gè)子集V1和V2(V1V2=),使得G中任何一條邊的兩個(gè)端點(diǎn)都一個(gè)屬于V1,另一個(gè)屬于V2,則稱G為二部圖（或稱偶圖、雙圖、二分圖），V1,V2稱為互補(bǔ)頂點(diǎn)子集.

若G是二部圖，也可將G記為G=<V1,V2,E>。又若V1中任一頂點(diǎn)與V2中任一頂點(diǎn)均有且僅有一條邊相關(guān)聯(lián)，則稱二部圖G為完全二部圖。若|V1|=r,|V2|=s,則記完全二部圖為Kr,s第6頁(yè)/共35頁(yè)78.1二部圖

注:在完全二部圖Kr,s中，它的頂點(diǎn)數(shù)n=r+s，它的邊數(shù)m=rs.定理8.1.1一個(gè)無(wú)向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無(wú)奇數(shù)長(zhǎng)度的回路。第7頁(yè)/共35頁(yè)8

如圖所示各圖都是二部圖，其中，(1)，(2)，(3)為K6的子圖，(3)為完全二部圖K3,3，常將K3,3畫成與其同構(gòu)的(5)的形式，K3,3是下文中經(jīng)常遇到的圖。(4)是K5的子圖，它是完全二部圖K2,3，K2,3常畫成(6)的形式。

注意，n階零圖為二部圖。

第8頁(yè)/共35頁(yè)98.2歐拉圖與哈密爾頓圖引例：哥尼斯堡七橋問(wèn)題

如何不重復(fù)地走完七橋后回到起點(diǎn)？

。。。。ABCD第9頁(yè)/共35頁(yè)108.2歐拉圖與哈密爾頓圖一、歐拉圖定義8.2.1

給定無(wú)孤立結(jié)點(diǎn)圖G=<V,E>，若存在一條通路，經(jīng)過(guò)圖中每條邊一次且僅一次，該通路稱作歐拉通路；若G中歐拉通路又是回路，則稱它為G中的歐拉回路；具有歐拉回路的圖稱為歐拉圖。注意：只有歐拉通路無(wú)歐拉回路的圖不是歐拉圖。第10頁(yè)/共35頁(yè)118.2歐拉圖與哈密爾頓圖(a)無(wú)歐拉通路(b)無(wú)歐拉回路(c)是歐拉圖第11頁(yè)/共35頁(yè)128.2歐拉圖與哈密爾頓圖定理8.2.1

無(wú)向圖G具有一條歐拉通路，當(dāng)且僅當(dāng)G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。證明必要性設(shè)G具有歐拉通路，即有點(diǎn)邊序列v0e1v1e2v2…eiviei+1…ekvk,其中結(jié)點(diǎn)可能重復(fù)出現(xiàn)，但邊不重復(fù)，因?yàn)闅W拉通路經(jīng)過(guò)所有圖G的結(jié)點(diǎn)，故圖G是連通的。對(duì)任意一個(gè)不是端點(diǎn)（始點(diǎn)和終點(diǎn)）的結(jié)點(diǎn)vi,在歐拉通路中每當(dāng)vi出現(xiàn)一次，必關(guān)聯(lián)兩條邊，故vi雖可重復(fù)出現(xiàn)，但deg(vi)必是偶數(shù)。對(duì)于端點(diǎn)，若v0=vk,則d(v0)為偶數(shù)，即G中無(wú)奇數(shù)度結(jié)點(diǎn)；若端點(diǎn)v0與vk不同，則d(v0)為奇數(shù)，d(vk)為奇數(shù)，G中就有兩個(gè)奇數(shù)度結(jié)點(diǎn)。第12頁(yè)/共35頁(yè)138.2歐拉圖與哈密爾頓圖充分性若圖G連通，有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)，我們構(gòu)造一條歐拉通路如下：

(1)若有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則從其中的一個(gè)結(jié)點(diǎn)考試構(gòu)造一條跡，即從v0出發(fā)經(jīng)關(guān)聯(lián)邊e1“進(jìn)入”v1,若deg(v1)為偶數(shù)，則可由v1再經(jīng)關(guān)聯(lián)邊e2進(jìn)入v2,如此進(jìn)行下去，每邊僅取一次。由于G是連通的，故必可到達(dá)另一奇數(shù)度結(jié)點(diǎn)停下，得到一條跡L:v0e1v1e2v2…eiviei+1…ekvk.若G中沒(méi)有奇數(shù)度結(jié)點(diǎn)則從任一結(jié)點(diǎn)v0出發(fā)，用上述方法必可回到結(jié)點(diǎn)v0,得到上述一條閉跡L1.第13頁(yè)/共35頁(yè)148.2歐拉圖與哈密爾頓圖(2)若L1通過(guò)了G的所有邊，則L1就是歐拉通路。(3)若G中去掉L1后得到子圖G’,則G’中每個(gè)結(jié)點(diǎn)度數(shù)為偶數(shù)，因?yàn)樵瓉?lái)的圖是連通的，故L1與G’至少有一個(gè)結(jié)點(diǎn)vi重合，在G’中由vi出發(fā)重復(fù)(1)的方法，得到閉跡L2.(4)當(dāng)L1與L2組合在一起，如果恰是G,即得歐拉通路，否則重復(fù)(3)可得到閉跡L3,依此類推直到得到一條經(jīng)過(guò)圖G中所有邊的歐拉通路。第14頁(yè)/共35頁(yè)158.2歐拉圖與哈密爾頓圖

由于有了歐拉回路和歐拉通路的判別準(zhǔn)則，因此哥尼斯堡七橋問(wèn)題立即有了確切的否定答案，因?yàn)閺纳蠄D中可以看到deg(A)=5,deg(B)=deg(C)=deg(D)=3,故歐拉回路必不存在。

。。。。ABCD第15頁(yè)/共35頁(yè)168.2歐拉圖與哈密爾頓圖歐拉通路和歐拉回路的概念，可以推廣到有向圖中去。定義8.2.2

給定有向圖G,通過(guò)圖中每邊一次且僅一次的一條單向通路(回路),稱作單向歐拉通路(回路)。定理8.2.2

有向圖G具有一條單向歐拉回路，當(dāng)且僅當(dāng)是連通的，且每個(gè)結(jié)點(diǎn)入度等于出度。一個(gè)有向圖G具有單向歐拉通路，當(dāng)且僅當(dāng)它是連通的，而且除兩個(gè)結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的入度等于出度，但這兩個(gè)結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的入度比出度小1。第16頁(yè)/共35頁(yè)178.2歐拉圖與哈密爾頓圖二、哈密爾頓圖1859年愛(ài)爾蘭數(shù)學(xué)家威廉.哈密頓首先提出在正十二面體上的一個(gè)數(shù)學(xué)游戲，即能否在如下所示的圖中找到一條基本(初級(jí))回路(或路徑)，使它經(jīng)過(guò)每個(gè)頂點(diǎn)恰好一次。第17頁(yè)/共35頁(yè)188.2歐拉圖與哈密爾頓圖

由于他將每個(gè)頂點(diǎn)看作一個(gè)城市，將兩個(gè)頂點(diǎn)之間的邊看作交通線，于是他提出的問(wèn)題稱為“周游世界問(wèn)題”。對(duì)于任何一個(gè)連通圖，都可以提出這樣的問(wèn)題，即在圖中是否存在經(jīng)過(guò)所有頂點(diǎn)一次且僅一次的回路或通路。將這樣的初級(jí)通路、回路分別稱為哈密爾頓通路、回路。第18頁(yè)/共35頁(yè)198.2歐拉圖與哈密爾頓圖定義8.2.3

給定圖G,若存在一條通路經(jīng)過(guò)圖中的每個(gè)結(jié)點(diǎn)恰好一次，這條通路稱作哈密爾頓路。若存在一條回路，經(jīng)過(guò)圖中的每個(gè)結(jié)點(diǎn)恰好一次，這條回路稱作哈密爾頓回路。具有哈密爾頓回路的圖稱作哈密爾頓圖。與歐拉圖的情況不同，直到目前，人們還沒(méi)有找到哈密爾頓圖的簡(jiǎn)單的充要條件，尋找充要條件是圖論中的一個(gè)難題。目前人們只找到一些判斷存在性的充分條件和一些必要條件，下面以無(wú)向圖為例加以說(shuō)明。第19頁(yè)/共35頁(yè)208.2歐拉圖與哈密爾頓圖定理8.2.3

設(shè)無(wú)向圖G=<V,E>為哈密爾頓圖，V1是V的任意真子集，則其中，p(G-V1)為從G中刪除V1后所得圖的連通分支數(shù)。定理中給出的條件是必要的。因而對(duì)一個(gè)圖來(lái)說(shuō)，如果不滿足這個(gè)必要條件，它一定不是哈密爾頓圖。但是，滿足這個(gè)條件的圖不一定是哈密爾頓圖。推論：有割點(diǎn)的圖一定不是哈密爾頓圖。第20頁(yè)/共35頁(yè)218.2歐拉圖與哈密爾頓圖下面給出一些充分條件。定理8.2.4

設(shè)G是n(n3)階無(wú)向簡(jiǎn)單圖，若對(duì)于G中每一對(duì)不相鄰的頂點(diǎn)u,v,均有

deg(u)+deg(v)n-1則G中存在哈密爾頓通路。又若

deg(u)+deg(v)n則G中存在哈密爾頓回路，即G為哈密爾頓圖。推論：設(shè)G是n(n3)階無(wú)向簡(jiǎn)單圖，若G是哈密爾頓圖。第21頁(yè)/共35頁(yè)228.2歐拉圖與哈密爾頓圖第22頁(yè)/共35頁(yè)238.2歐拉圖與哈密爾頓圖關(guān)于有向圖中的哈密爾頓通路與回路有下面的結(jié)論。定理8.2.5

在n(n2)階有向圖D=<V,E>中，如果略去所有有向邊的方向，所得無(wú)向圖中含生成子圖kn,則D中存在哈密爾頓通路。推論

n(n3)階有向完全圖都是哈密爾頓圖。第23頁(yè)/共35頁(yè)248.2歐拉圖與哈密爾頓圖例：今有a,b,c,d,e,f,g7個(gè)任，已知下列事實(shí)：

a會(huì)講英語(yǔ)；

b會(huì)講英語(yǔ)和漢語(yǔ)；

c會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)；

d會(huì)講日語(yǔ)和漢語(yǔ)；

e會(huì)講德語(yǔ)和意大利語(yǔ)；

f會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ)；

g會(huì)講法語(yǔ)和德語(yǔ)。問(wèn)能否將這7個(gè)人安排就坐圓桌旁，使得每個(gè)人都能與兩邊的人交談？第24頁(yè)/共35頁(yè)258.2歐拉圖與哈密爾頓圖解：做無(wú)向圖G=<V,E>,V={a,b,c,d,e,f,g},E={(u,v)|u,vV且uv且u與v有共同語(yǔ)言}，根據(jù)已知條件得G如下圖所示：第25頁(yè)/共35頁(yè)268.2歐拉圖與哈密爾頓圖在圖中，u與v相鄰當(dāng)且僅當(dāng)它們有共同語(yǔ)言。問(wèn)題就變成了圖中是否存在哈密爾頓回路(也即G為哈密爾頓圖)。不難看出C=acegfdba為G中的一條哈密爾頓回路，因而可以按C中頂點(diǎn)順序安排座次，這樣，每個(gè)人都與兩邊的人有共同語(yǔ)言，因而能交談。第26頁(yè)/共35頁(yè)278.3平面圖在圖的理論探討和實(shí)際應(yīng)用中，平面圖都具有重要的意義。比如在現(xiàn)實(shí)生活中，常常要畫一些圖形，希望邊與邊之間盡量減少相交的情況，例如印刷線路板上的布線，交通道的設(shè)計(jì)等。定義8.3.1

設(shè)G=<V,E>是一個(gè)無(wú)向圖，如果能夠把G的所有結(jié)點(diǎn)和邊畫在平面上，且使得任何兩邊除了端點(diǎn)外沒(méi)有其它的交點(diǎn)，就稱G是一個(gè)平面圖。畫出的沒(méi)有邊交叉出現(xiàn)的圖稱為G的一個(gè)平面嵌入或平面表示。無(wú)平面嵌入的圖為非平面圖。第27頁(yè)/共35頁(yè)288.3平面圖(a)(b)第28頁(yè)/共35頁(yè)298.3平面圖(c)(d)第29頁(yè)/共35頁(yè)308.3平面圖定義8.3.2

設(shè)G是一個(gè)平面圖，G的邊將所在的平面劃分成若干個(gè)區(qū)域，每個(gè)區(qū)域稱為G的一個(gè)面。其中面積無(wú)限的區(qū)域稱為無(wú)限面或外部面，面積有限的區(qū)域稱為內(nèi)部面或有限面。包圍每個(gè)面的所有邊構(gòu)成的回路稱為該面的邊界，邊界的長(zhǎng)度稱為該面的次數(shù)。面Ri的次數(shù)記作deg(Ri),人們常把外部面記成R0.第30頁(yè)/共35頁(yè)318.3平面圖第31頁(yè)/共35頁(yè)328.3平面圖定理8.3.1

在一個(gè)平面圖G中，所有面的次數(shù)之和為邊數(shù)的2倍，即其中，r為G的面數(shù)，m為邊數(shù)。關(guān)于平面圖的平面嵌入，還應(yīng)指出兩點(diǎn)：(1)同一個(gè)平面圖G，可以有不同形狀的平面嵌入，但它們都是與G同構(gòu)的；(2)平面圖G的外部面，可以通過(guò)變換由G的任何面充當(dāng)。第32頁(yè)/共35頁(yè)338.3平面圖在上圖中，(b)(c)都是(a)的平面嵌入，它們的形狀不同，但都與(a)同構(gòu)。(b)中的有限面R22在(c)中變成了無(wú)限面R0,