第八章一些特殊的圖內(nèi)容導(dǎo)讀:

二部圖歐拉圖哈密頓圖平面圖難點(diǎn):各種圖的判別定理2023/9/171

ABCD2023/9/172(1)(2)設(shè)無向圖G=<V,E>有兩個(gè)V的子集V1,V2,它們具有滿足：V1∪V2=VV1∩V2=

圖G中的每一邊e均具有e=(vi,vj

)其中：vi∈V1,

vj∈V2則稱G是一個(gè)二部圖，2023/9/173定義8.1若一個(gè)圖G的結(jié)點(diǎn)集V能劃分為兩個(gè)子集V1和V2，使得G的每一條邊{vi,vj}滿足vi∈V1,vj∈V2,則稱G是一個(gè)二部圖，V1和V2稱為G的互補(bǔ)結(jié)點(diǎn)子集。此時(shí)可將G記成G=<V1,V2,E>

若V1中任一結(jié)點(diǎn)與V2中每一結(jié)點(diǎn)均有邊相連接,則稱二部圖為完全二部圖。若|V1|=n,|V2|=m則記完全二部圖G為Kn,m。(1)(2)K2,3K3,32023/9/174(1)(2)例8.1

判斷下列圖是否是二部圖？v1v3v5v2v4v6v1v4v8v5v2v3v6v7v1v2v3v4v5(3)在圖(1)中,V1={v1,v3,v5},V2={v2,v4,v6},是一個(gè)完全二部圖。在圖(2)中,V1={v1,v4,v8,v5},V2={v2,v3,v7,v6},是一個(gè)二部圖。在圖(3)中,對于其中的頂點(diǎn)無法將它們分到兩個(gè)不同的子集V1和V2,使其邊能滿足二部圖的定義,所以它不是二部圖。二部圖是不是一定是連通圖?2023/9/175(4)(5)定理8.1一個(gè)無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇數(shù)長度的回路。下圖所示前3個(gè)圖中,均無奇數(shù)長度的回路,所以它們都是二部圖,其中圖(2)所示為K2,3,圖(3)所示為K3,3,它們分別與圖(4)和(5)同構(gòu)。(1)(2)(3)2023/9/176(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖(1)中，{e1},{e1,e7},{e5},{e4,e6}等都是圖中的匹配。在圖(2)中找出匹配。定義8.2

設(shè)G=<V,E>為無向圖,E*E,若E*中任意兩條邊均不相鄰,則子集E*稱為G中的匹配(或邊獨(dú)立集),并把E*中的邊所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)稱為在E*下是匹配的。2023/9/177(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖(1)中,{e5},{e1,e7},{e4,e6}{e3,e7},{e2,e6}是極大匹配，后4個(gè)是最大匹配，匹配數(shù)

1=2。若在E*中再加入任何一條邊就都不是匹配了,則稱E*為極大匹配。邊數(shù)最多的極大匹配稱為最大匹配，最大匹配中的元素(邊)的個(gè)數(shù)稱為G的匹配數(shù)，記為1(G),簡記為1。2023/9/178(2)e1e2e3e4e5e6e7在圖(2)中,{e2,e5},{e3,e6},{e1,e7,e4}都是極大匹配,其中{e1,e7,e4}是最大匹配。2023/9/179(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖(1)中不存在完美匹配。在圖(2)中,{e1,e7,e4}是最大匹配，同時(shí)也是完美匹配。今后常用M表示匹配，設(shè)M為G中一個(gè)匹配，vV(G),若存在M中的邊與v關(guān)聯(lián)，則稱v為M飽和點(diǎn)，否則v為M非飽和點(diǎn)，若G中每個(gè)頂點(diǎn)都是飽和點(diǎn)，則稱M為G中完美匹配。2023/9/1710定義8.3

設(shè)G=<V1,V2,E>為二部圖,M為G中一個(gè)最大匹配,

若|M|=min{|V1|,|V2|},則稱M為G中的一個(gè)完備匹配,此時(shí)若|V1|≤|V2|,則稱M為V1到V2的一個(gè)完備匹配。如果|V1|=|V2|,這時(shí)M為G中的完美匹配。G1G2G3在上圖中,{e1,e2}為G1中的最大匹配,G1中不存在完備匹配,更無完美匹配。G2中{e1,e2,e3}為完備匹配,但G2中無完美匹配。G3中{e1,e2,e3}為完備匹配,同時(shí)也是完美匹配。e1e2e1e2e3e1e2e32023/9/1711例8.2我們班級成立了3個(gè)運(yùn)動隊(duì):籃球隊(duì)、排球隊(duì)和足球隊(duì)。今有張、王、李、趙、陳5位同學(xué)，若已知張、王為籃球隊(duì)員；張、李、趙為排球隊(duì)員；李、趙、陳為足球隊(duì)員，問能否從這5人中選出3名不兼職的隊(duì)長？解:構(gòu)造二部圖G=<V1,V2,E>其中V1=

籃球隊(duì),排球隊(duì),足球隊(duì),V2=

張,王,李,趙,陳

圖中的邊分別表示這5位同學(xué)是相應(yīng)球隊(duì)的隊(duì)員,圖中存在V1到V2的匹配,因此題目要求可以滿足。如可選張為籃球隊(duì)長,李為排球隊(duì)長,陳為足球隊(duì)長?；@排足張王李趙陳V1V22023/9/1712籃排足張王李趙陳V1V2籃排足張王李趙陳V1V2籃排足張王李趙陳V1V2籃排足張王李趙陳V1V2剩下的匹配同學(xué)們自己找2023/9/1713幾個(gè)問題1“一筆畫”問題2“街道清掃車”設(shè)某封閉式小區(qū)的路網(wǎng)結(jié)構(gòu)如圖所示，請證明能否設(shè)計(jì)出一條路線使得清潔車從小區(qū)大門出發(fā)清掃每條道路恰好一次，且在清掃完最后一條道路后正好返回小區(qū)大門處。3七橋問題小區(qū)大門ABCD8.2歐拉圖2023/9/1714ABCD在以下4個(gè)圖中,不能一筆畫出圖①,②,而能一筆畫出圖③,④且在④中筆又能回到出發(fā)點(diǎn)。①②③④在③中存在關(guān)聯(lián)所有頂點(diǎn)的簡單通路,在④中存在關(guān)聯(lián)所有頂點(diǎn)的簡單回路2023/9/1715定義8.4通過圖(無向圖或有向圖)中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路。通過圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。規(guī)定：平凡圖是歐拉圖。2023/9/1716ABCDEe1e2e3e4例8.4

左下圖既是歐拉回路，也是歐拉圖

而右下圖則是歐拉通路2023/9/1717推論無向圖G是歐拉圖

G是連通圖，且G中沒有奇度頂點(diǎn)。

無向圖G是半歐拉圖

G是連通圖，且G中恰有兩個(gè)奇度頂點(diǎn)。定理8.4無向圖G具有歐拉通路

G是連通圖，且G中有零個(gè)或兩個(gè)奇度頂點(diǎn)。

若無奇度頂點(diǎn)，則通路為歐拉回路；若有兩個(gè)奇度頂點(diǎn)，則它們是每條歐拉通路的端點(diǎn)。2023/9/1718例8.5考察下圖是否為歐拉圖或存在歐拉通路？∵存在兩個(gè)奇度頂點(diǎn)∴根據(jù)定理8.4推論知不是歐拉圖.存在一條歐拉通路2023/9/1719定理8.5有向圖D具有歐拉通路

D

是連通的,且除了兩個(gè)頂點(diǎn)外,其余頂點(diǎn)的入度均等于出度。在這兩個(gè)特殊的頂點(diǎn)中,一個(gè)頂點(diǎn)的入度比出度大1,另一個(gè)頂點(diǎn)的入度比出度小1。推論一個(gè)有向圖D是歐拉圖

D是連通的，且所有頂點(diǎn)的入度等于出度。特別提醒：歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可以重復(fù).筆不離開紙，不重復(fù)地走完所有的邊，回到原處.就是所謂的一筆畫.

2023/9/1720v0v1v2e10e’12e21e00e01e20e22e12e’01例8.7考察下圖是歐拉通路或歐拉回路嗎？三個(gè)頂點(diǎn)的度出度與入度相同是歐拉回路！∵沿著邊

e00,e01,e12,e22,e21,e10,e’01,e’12,e20

回到出發(fā)點(diǎn)2023/9/1721幾個(gè)問題在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)最優(yōu)的路線，使運(yùn)鈔車過每個(gè)提款機(jī)一次就能運(yùn)送完錢鈔？貨郎擔(dān)問題 旅行商人問題

(TravelingSalesmanProblem,TSP)

優(yōu)化算法——近似解

演化算法8.3哈密頓圖2023/9/1722幾個(gè)問題1.在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)最優(yōu)的路線，使運(yùn)鈔車過每個(gè)提款機(jī)一次就能運(yùn)送完錢鈔？貨郎擔(dān)問題旅行商人問題(TSP)2.考慮在七天內(nèi)安排七門課程的考試，要求同一位教師所任教的兩門課程考試不安排在接連的兩天里，如果教師所擔(dān)任的課程都不多于四門，則是否存在滿足上述要求的考試安排方案？ 時(shí)間表問題3.國際象棋的跳馬是否可以遍歷其棋盤，即從任一格出發(fā)跳到每一格僅一次并最后回到出發(fā)的棋盤格子？4.在一個(gè)至少有5人出席的圓桌會議上（會議需要舉行多次），為達(dá)到充分交流的目的，會議主持者希望每次會議每人兩側(cè)的人均與前次不同，這是否可行？請應(yīng)用圖論知識進(jìn)行論證。5.周游世界問題2023/9/1723哈密爾頓圖問題

1859年愛爾蘭數(shù)學(xué)家威廉·哈密爾頓（SirWilliamHamilton）發(fā)明了一個(gè)小游戲玩具：一個(gè)木刻的正十二面體，每面系正五角形，三面交于一角，共有20個(gè)角，每角標(biāo)有世界上一個(gè)重要城市。哈密爾頓提出一個(gè)問題：要求沿正十二面體的邊尋找一條路通過20個(gè)城市，而每個(gè)城市只通過一次，最后返回原地。哈密爾頓將此問題稱為周游世界問題。游戲)求解 抽象為圖論問題

哈密爾頓給出了肯定回答，該問題的解是存在的哈密爾頓回路(圈)哈密爾頓圖運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都可以化為哈密爾頓圖問題

WilliamRowanHamilton(1805-1865)2023/9/1724定義8.5

經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)一次且僅一次的通路稱為哈密頓通路。經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖.具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖.注:平凡圖是哈密頓圖。8.3哈密頓圖2023/9/1725例8.10指出下列各圖是否哈密頓圖,有無哈密頓通路,回路？解(1)容易判斷,存在哈密頓回路,故是哈密頓圖.(2)只有哈密頓通路,無哈密頓回路,故不是哈密頓圖.(3)無哈密頓通路，顯然不是哈密頓圖.(1)(2)(3)2023/9/1726定理8.6——必要條件設(shè)無向圖G=<V,E>是哈密頓圖,對于任意V1

V且V1≠,均有p(G-V1)≤|V1|,其中p(G-V1)為G中刪除V1(刪除V1中各頂點(diǎn)及關(guān)聯(lián)的邊)后所得圖的連通分支數(shù)。證:設(shè)C為G中任意一條哈密頓回路。①若V1中的頂點(diǎn)在C上彼此相鄰，則p(C-V1)=1≤|V1|②設(shè)V1中的頂點(diǎn)在C上存在r(2≤r≤|V1|)個(gè)互不相鄰，則p(C-V1)=r≤|V1|

一般說來,V1中的頂點(diǎn)在C上既有相鄰的,又有不相鄰的,因而總有p(C-V1)≤|V1|，而C是G的生成子圖,∴p(G-V1)≤p(C-V1)≤|V1|2023/9/1727e1e2e3e4e5e6v1v2v3v4V1={v1,v4}或V1={v2,v3}

v5若V1中的頂點(diǎn)在C上彼此相鄰，則P(C-V1)=1≤|V1|2023/9/1728e1e2e3e4e5e6e7V1={v1,v2,v3}或V1={v1,v4,v3}

v1v2v3v4v5設(shè)V1中的頂點(diǎn)在C上存在r(2≤r≤|V1|)個(gè)互不相鄰，則P(C-V1)=r≤|V1|

2023/9/1729例8.13利用定理8.6可判斷某些圖不是哈密頓圖設(shè)下圖①為G1,取

V1={v},則P(G1-V1)=2>|V1|=1

G1-V1為圖②所示,由定理8.6可知G1不是哈密頓圖v①②2023/9/1730定理8.7

——充分條件設(shè)G是n(n≥3)階無向簡單圖，若對G中任意不相鄰的頂點(diǎn)vi,vj的度數(shù)之和大于等于n-1，即d(vi)+d(vj)≥n-1則G中存在哈密頓通路.推論

設(shè)G為n(n≥3)階無向簡單圖，若對于G中任意兩個(gè)不相鄰的頂點(diǎn)vi,vj，均有

d(vi)+d(vj)≥n則G中存在哈密頓回路，從而G為哈密頓圖。2023/9/1731e1e2e3e4e5e6d(vi)+d(vj)≥n-1存在哈密頓通路d(vi)+d(vj)≥n存在哈密頓回路2023/9/1732(2)(3)再如下圖G任意兩個(gè)不相鄰的頂點(diǎn)vi,vjd(vi)+d(vj)≥n-1則G中存在哈密頓通路.d(vi)+d(vj)≥n則G中存在哈密頓回路，從而G為哈密頓圖。abdc(1)(1)和(2)2023/9/1733定理8.8在n(n≥2)階有向圖D=<V,E>中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子圖Kn,則有向圖D中存在哈密頓通路.推論

n(n≥3)階有向完全圖G為哈密頓圖。2023/9/1734例8.15已知有關(guān)人員a,b,c,d,e,f,g的有關(guān)信息a：說英語；

b：說英語或西班牙語；c；說英語，意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.試問：上述7人中是否任意兩人都能交談？(可借助其余5人中組成的譯員鏈幫助) 2023/9/1735abcdefg解設(shè)7個(gè)人為7個(gè)結(jié)點(diǎn),將兩個(gè)懂同一語言的人之間連一條邊(即他們能直接交談),這樣就得到一個(gè)簡單圖G,問題就轉(zhuǎn)化為G是否連通.如圖所示,因?yàn)镚的任意兩個(gè)結(jié)點(diǎn)是連通的,所以G是連通圖.因此,上述7個(gè)人中任意兩個(gè)人能交談. a：說英語；b：說英語或西班牙語；C:說英語,意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.2023/9/1736abcdefg如果題目改為：試問這7個(gè)人應(yīng)如何安排座位,才能使每個(gè)人都能與他身邊的人交談？解：用結(jié)點(diǎn)表示人，用邊表示連接的兩個(gè)人能將同一種語言，夠造出哈密頓圖如右上圖所示。a：說英語；b：說英語或西班牙語；c；說英語，意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.英英西日法德意2023/9/1737對于平面圖,先舉一例,設(shè)有一個(gè)電路它有六個(gè)元件，三個(gè)分成一組，一個(gè)元件組的每個(gè)元件都用導(dǎo)線與另一組的每個(gè)元件相接，是否有這樣的接法使得導(dǎo)線互不交叉？這個(gè)問題可用左下圖表示,它的最少交叉點(diǎn)是一個(gè)，用右下圖表示§8.4.平面圖2023/9/1738定義8.6

一個(gè)圖G能畫在平面上，除頂點(diǎn)之外，再沒有邊與邊相交.則稱G為平面圖。畫出的沒有邊交叉的圖稱為G的一個(gè)平面嵌入或G的一個(gè)平面.在下圖中(2)是(1)(K4)的平面嵌入,所以(1)是平面圖,單獨(dú)看(2)也是平面圖,對于(3)(K5)無論怎樣畫法,也去不掉交叉邊,所以不是平面圖。(1)(2)(3)(4)2023/9/1739例8.16右下圖是左下圖的平面嵌入,所以左下圖是平面圖,單獨(dú)看右下圖也是平面圖。2023/9/1740定義8.7

設(shè)G是一個(gè)連通的平面圖,G的邊將G所在的平面劃分成若干個(gè)區(qū)域,每個(gè)區(qū)域稱為G的一個(gè)面。其中面積無限的區(qū)域稱為無限面或外部面,常記為R0,面積有限的區(qū)域稱為有限面或內(nèi)部面。包圍每個(gè)面的所有邊所構(gòu)成的回路稱為該面的邊界,邊界的長度稱為該面的次數(shù),R次數(shù)記為deg(R)對于非連通的平面圖G可以類似地定義它的面、邊界及次數(shù)。2023/9/1741v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2(1)(2)在下圖中,圖(1)所示為連通的平面圖,共有3個(gè)面R0,R1,R2。R1的邊界為初級回路v1

v3

v4

v1,deg(R1)=3。R2的邊界為初級回路v1

v2

v3

v1,deg(R2)=3。R0無限面,它的邊界為復(fù)雜回路v1

v4

v5v6v5

v4v3

v2v1,deg(R0)=8。圖(2)所示為非連通的平面圖，有兩個(gè)連通分支，deg(R1)=3，deg(R2)=4，R0的邊界由兩個(gè)初級回路v1

v2

v3v1和v4

v5v6

v7v4圍成，deg(R0)=7。2023/9/1742v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2(1)(2)定理8.