2023/7/9離散數學1第八章一些特殊的圖內容導讀:

二部圖歐拉圖哈密頓圖平面圖難點:各種圖的判別定理2023/7/9離散數學2

ABCD2023/7/9離散數學3(1)(2)設無向圖G=<V,E>有兩個V的子集V1,V2,它們具有滿足：V1∪V2=VV1∩V2=圖G中的每一邊e均具有e=(vi,vj

)其中：vi∈V1,

vj∈V2則稱G是一個二部圖，2023/7/9離散數學4定義8.1若一個圖G的結點集V能劃分為兩個子集V1和V2，使得G的每一條邊{vi,vj}滿足vi∈V1,vj∈V2,則稱G是一個二部圖，V1和V2稱為G的互補結點子集。此時可將G記成G=<V1,V2,E>

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

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

設G=<V,E>為無向圖,E*E,若E*中任意兩條邊均不相鄰,則子集E*稱為G中的匹配(或邊獨立集),并把E*中的邊所關聯的兩個結點稱為在E*下是匹配的。2023/7/9離散數學8(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖(1)中,{e5},{e1,e7},{e4,e6}{e3,e7},{e2,e6}是極大匹配，后4個是最大匹配，匹配數1=2。若在E*中再加入任何一條邊就都不是匹配了,則稱E*為極大匹配。邊數最多的極大匹配稱為最大匹配，最大匹配中的元素(邊)的個數稱為G的匹配數，記為1(G),簡記為1。2023/7/9離散數學9(2)e1e2e3e4e5e6e7在圖(2)中,{e2,e5},{e3,e6},{e1,e7,e4}都是極大匹配,其中{e1,e7,e4}是最大匹配。2023/7/9離散數學10(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖(1)中不存在完美匹配。在圖(2)中,{e1,e7,e4}是最大匹配，同時也是完美匹配。今后常用M表示匹配，設M為G中一個匹配，vV(G),若存在M中的邊與v關聯，則稱v為M飽和點，否則v為M非飽和點，若G中每個頂點都是飽和點，則稱M為G中完美匹配。2023/7/9離散數學11定義8.3

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

若|M|=min{|V1|,|V2|},則稱M為G中的一個完備匹配,此時若|V1|≤|V2|,則稱M為V1到V2的一個完備匹配。如果|V1|=|V2|,這時M為G中的完美匹配。G1G2G3在上圖中,{e1,e2}為G1中的最大匹配,G1中不存在完備匹配,更無完美匹配。G2中{e1,e2,e3}為完備匹配,但G2中無完美匹配。G3中{e1,e2,e3}為完備匹配,同時也是完美匹配。e1e2e1e2e3e1e2e32023/7/9離散數學12例8.2我們班級成立了3個運動隊:籃球隊、排球隊和足球隊。今有張、王、李、趙、陳5位同學，若已知張、王為籃球隊員；張、李、趙為排球隊員；李、趙、陳為足球隊員，問能否從這5人中選出3名不兼職的隊長？解:構造二部圖G=<V1,V2,E>其中V1=籃球隊,排球隊,足球隊,V2=張,王,李,趙,陳圖中的邊分別表示這5位同學是相應球隊的隊員,圖中存在V1到V2的匹配,因此題目要求可以滿足。如可選張為籃球隊長,李為排球隊長,陳為足球隊長。籃排足張王李趙陳V1V22023/7/9離散數學13籃排足張王李趙陳V1V2籃排足張王李趙陳V1V2籃排足張王李趙陳V1V2籃排足張王李趙陳V1V2剩下的匹配同學們自己找2023/7/9離散數學14幾個問題1“一筆畫”問題2“街道清掃車”設某封閉式小區的路網結構如圖所示，請證明能否設計出一條路線使得清潔車從小區大門出發清掃每條道路恰好一次，且在清掃完最后一條道路后正好返回小區大門處。3七橋問題小區大門ABCD8.2歐拉圖2023/7/9離散數學15ABCD在以下4個圖中,不能一筆畫出圖①,②,而能一筆畫出圖③,④且在④中筆又能回到出發點。①②③④在③中存在關聯所有頂點的簡單通路,在④中存在關聯所有頂點的簡單回路2023/7/9離散數學16定義8.4通過圖(無向圖或有向圖)中所有邊一次且僅一次行遍所有頂點的通路稱為歐拉通路。通過圖中所有邊一次且僅一次行遍所有頂點的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。規定：平凡圖是歐拉圖。2023/7/9離散數學17ABCDEe1e2e3e4例8.4

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

而右下圖則是歐拉通路2023/7/9離散數學18推論無向圖G是歐拉圖

G是連通圖，且G中沒有奇度頂點。

無向圖G是半歐拉圖

G是連通圖，且G中恰有兩個奇度頂點。定理8.4無向圖G具有歐拉通路

G是連通圖，且G中有零個或兩個奇度頂點。

若無奇度頂點，則通路為歐拉回路；若有兩個奇度頂點，則它們是每條歐拉通路的端點。2023/7/9離散數學19例8.5考察下圖是否為歐拉圖或存在歐拉通路？∵存在兩個奇度頂點∴根據定理8.4推論知不是歐拉圖.存在一條歐拉通路2023/7/9離散數學20定理8.5有向圖D具有歐拉通路D

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

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

2023/7/9離散數學21v0v1v2e10e’12e21e00e01e20e22e12e’01例8.7考察下圖是歐拉通路或歐拉回路嗎？三個頂點的度出度與入度相同是歐拉回路！∵沿著邊

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

回到出發點2023/7/9離散數學22幾個問題在一個大城市，有很多取款機，那么，如何制定出一個最優的路線，使運鈔車過每個提款機一次就能運送完錢鈔？貨郎擔問題 旅行商人問題

(TravelingSalesmanProblem,TSP)

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

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

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

WilliamRowanHamilton(1805-1865)2023/7/9離散數學25定義8.5

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

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

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

v5若V1中的頂點在C上彼此相鄰，則P(C-V1)=1≤|V1|2023/7/9離散數學29e1e2e3e4e5e6e7V1={v1,v2,v3}或V1={v1,v4,v3}

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

2023/7/9離散數學30例8.13利用定理8.6可判斷某些圖不是哈密頓圖設下圖①為G1,取

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

G1-V1為圖②所示,由定理8.6可知G1不是哈密頓圖v①②2023/7/9離散數學31定理8.7

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

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

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

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

b：說英語或西班牙語；

c；說英語，意大利語和俄語；

d：說日語和西班牙語

e：說德語和意大利語；

f：說法語、日語和俄語；

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

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

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

v3

v4

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

v2

v3

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

v4

v5v6v5

v4v3

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

v2

v3v1和v4

v5v6

v7v4圍成，deg(R0)=7。2023/7/9離散數學43v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2(1)(2)定理8.9

在一個平面圖G中,所有面的次數之和＝邊數m的2倍，即

deg(Ri)=2m在如下圖所示：無論是連通的還是非連通的平面圖，各面次數之和均等于邊數的兩倍。i=1r其中r為面數