第6章-一些特殊的圖

第6章一些特殊的圖內(nèi)容導讀:

二部圖歐拉圖哈密頓圖平面圖難點:各種圖的判別定理2023/9/28離散數(shù)學1

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

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

)其中：vi∈V1,

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

若V1中任一結(jié)點與V2中每一結(jié)點均有邊相連接,則稱二部圖為完全二部圖。若|V1|=n,|V2|=m則記完全二部圖G為Kn,m。(1)(2)K2,3K3,32023/9/28離散數(shù)學4(1)(2)例6.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/9/28離散數(shù)學5(4)(5)定理6.1一個無向圖G=<V,E>是二部圖當且僅當G中無奇數(shù)長度的回路。下圖所示前3個圖中,均無奇數(shù)長度的回路,所以它們都是二部圖,其中圖(2)所示為K2,3,圖(3)所示為K3,3,它們分別與圖(4)和(5)同構。(1)(2)(3)2023/9/28離散數(shù)學6(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖(1)中，{e1},{e1,e7},{e5},{e4,e6}等都是圖中的匹配。在圖(2)中找出匹配。定義6.2

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

1=2。若在E*中再加入任何一條邊就都不是匹配了,則稱E*為極大匹配。邊數(shù)最多的極大匹配稱為最大匹配，最大匹配中的元素(邊)的個數(shù)稱為G的匹配數(shù)，記為1(G),簡記為1。2023/9/28離散數(shù)學8(2)e1e2e3e4e5e6e7在圖(2)中,{e2,e5},{e3,e6},{e1,e7,e4}都是極大匹配,其中{e1,e7,e4}是最大匹配。2023/9/28離散數(shù)學9(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖(1)中不存在完美匹配。在圖(2)中,{e1,e7,e4}是最大匹配，同時也是完美匹配。今后常用M表示匹配，設M為G中一個匹配，vV(G),若存在M中的邊與v關聯(lián)，則稱v為M飽和點，否則v為M非飽和點，若G中每個頂點都是飽和點，則稱M為G中完美匹配。2023/9/28離散數(shù)學10v1v2v3v4v5v6v7v8v9v1v2v3v4v5v6v7v8(2)(1)在圖(1)中的一個最大匹配是M={(v1,v2),(v3,v9),(v5,v6),(v7,v8)}在圖(2)中的一個完美匹配是M={(v1,v2),(v3,v4),(v5,v6),(v7,v8)}2023/9/28離散數(shù)學11定義6.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/9/28離散數(shù)學12例6.2我們班級成立了3個運動隊:籃球隊、排球隊和足球隊。今有張、王、李、趙、陳5位同學，若已知張、王為籃球隊員；張、李、趙為排球隊員；李、趙、陳為足球隊員，問能否從這5人中選出3名不兼職的隊長？解:構造二部圖G=<V1,V2,E>其中V1=

籃球隊,排球隊,足球隊,V2=

張,王,李,趙,陳

圖中的邊分別表示這5位同學是相應球隊的隊員,圖中存在V1到V2的匹配,因此題目要求可以滿足。如可選張為籃球隊長,李為排球隊長,陳為足球隊長?；@排足張王李趙陳V1V22023/9/28離散數(shù)學13例6.3今有3人甲、乙、丙和3項工作a,b,c,已知甲能勝任3項工作a,b,c,乙能勝任2項工作a,b,丙能勝任2項工作b,c。能否給出2種不同的方案，使每個人各去完成一項他能勝任的工作？解:構造二部圖G=<V1,V2,E>其中V1=

甲,乙,丙,V2=

a,b,c

若V1中某人能勝任V2中某項工作，則用邊連接這兩個結(jié)點，得到右圖。顯然(甲,a),(乙,b),(丙,c)和(甲,c),(乙,a),(丙,b)是符合題目要求的2種不同的方案請同學們考慮:還有第3種方案嗎？甲乙丙abcV1V22023/9/28離散數(shù)學14幾個問題1“一筆畫”問題2“街道清掃車”設某封閉式小區(qū)的路網(wǎng)結(jié)構如圖所示，請證明能否設計出一條路線使得清潔車從小區(qū)大門出發(fā)清掃每條道路恰好一次，且在清掃完最后一條道路后正好返回小區(qū)大門處。3七橋問題小區(qū)大門ABCD6.2歐拉圖2023/9/28離散數(shù)學15ABCD在以下4個圖中,不能一筆畫出圖①,②,而能一筆畫出圖③,④且在④中筆又能回到出發(fā)點。①②③④在③中存在關聯(lián)所有頂點的簡單通路,在④中存在關聯(lián)所有頂點的簡單回路2023/9/28離散數(shù)學16定義6.4通過圖(無向圖或有向圖)中所有邊一次且僅一次行遍所有頂點的通路稱為歐拉通路。通過圖中所有邊一次且僅一次行遍所有頂點的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。規(guī)定：平凡圖是歐拉圖。2023/9/28離散數(shù)學17ABCDEe1e2e3e4例6.4

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

而右下圖則是歐拉通路2023/9/28離散數(shù)學18推論無向圖G是歐拉圖

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

無向圖G是半歐拉圖

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

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

若無奇度頂點，則通路為歐拉回路；若有兩個奇度頂點，則它們是每條歐拉通路的端點。2023/9/28離散數(shù)學19例6.5考察下圖是否為歐拉圖或存在歐拉通路？∵存在兩個奇度頂點∴根據(jù)定理6.4推論知不是歐拉圖.存在一條歐拉通路2023/9/28離散數(shù)學20v4

v5

E

G4

Av2

v3

B

C

v1

D（a）(b)

圖6－1例6.6求下列圖是否為歐拉圖或存在歐拉通路？v1v2v3v4v5???????????EBFADC(1)(2)解:在圖(1)中,d(v1)=d(v2)=d(v3)＝3有兩個以上的結(jié)點的度為3.根據(jù)定理6.4知:圖(1)中不存在歐拉通路，當然不存在歐拉回路,所以不是歐拉圖.不能一筆畫出.

在圖(2)中,d(A)=2,d(B)=d(C)=d(D)=4 d(E)=d(G)=3只有兩個奇數(shù)度的結(jié)點,有歐拉通路,根據(jù)定理6.4推論知不是歐拉圖.存在一條歐拉通路,如EDBEFCABCDF2023/9/28離散數(shù)學21定理6.5有向圖D具有歐拉通路

D

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

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

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

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

回到出發(fā)點2023/9/28離散數(shù)學231234e1e2e3e4e5e1e2e3e4e5e1e2e3e4e5e6e3e1e2e4e2e1e3e4e5e2e1e3e456例6.6：判斷各圖是否存在歐拉通路或歐拉回路2023/9/28離散數(shù)學24v1v2v3v4e1e2e3e4e4e5e6e7例6.9

判定下圖中，是否有歐拉回路？若有請把歐拉回路寫出來.

在圖中，D是連通的，且所有頂點的出度等于入度。根據(jù)定理6.5推論知：D是歐拉圖，所以存在歐拉回路，一個歐拉回路為v1e1

v2e2

v3e5

v1e4

v3e3

v4

e6v2e7

v4e4v12023/9/28離散數(shù)學25幾個問題在一個大城市，有很多取款機，那么，如何制定出一個最優(yōu)的路線，使運鈔車過每個提款機一次就能運送完錢鈔？貨郎擔問題 旅行商人問題

(TravelingSalesmanProblem,TSP)

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

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

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

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

WilliamRowanHamilton(1805-1865)2023/9/28離散數(shù)學28定義6.5

經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。經(jīng)過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖.具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖.注:平凡圖是哈密頓圖。6.3哈密頓圖2023/9/28離散數(shù)學29例6.10指出下列各圖是否哈密頓圖,有無哈密頓通路,回路？解(1)容易判斷,存在哈密頓回路,故是哈密頓圖.(2)只有哈密頓通路,無哈密頓回路,故不是哈密頓圖.(3)無哈密頓通路，顯然不是哈密頓圖.(1)(2)(3)2023/9/28離散數(shù)學30例6.11：判斷各圖是否是哈密頓圖。1234e1e2e3e4e5e1e2e3e4e5e1e2e3e4e5e6e3e1e2e4e2e1e3e4e5e2e1e3e4562023/9/28離散數(shù)學31例6.12畫出具有下列條件的有5個結(jié)點的無向圖(1)

不是哈密頓圖，也不是歐拉圖；(2)有哈密頓回路，沒有歐拉回路；(3)沒有哈密頓回路，有歐拉回路；(4)是哈密頓圖，也是歐拉圖.解作圖如圖(4)(不唯一).(1)(2)(3)(4)2023/9/28離散數(shù)學32例6.12畫出具有下列條件的有5個結(jié)點的無向圖(1)

不是哈密頓圖，也不是歐拉圖；(2)有哈密頓回路，沒有歐拉回路；(3)沒有哈密頓回路，有歐拉回路；(4)是哈密頓圖，也是歐拉圖.解作圖如圖(4)(不唯一).(1)(2)(3)(4)2023/9/28離散數(shù)學33定理6.6——必要條件設無向圖G=<V,E>是哈密頓圖,對于任意V1

V且V1≠,均有p(G-V1)≤|V1|,其中p(G-V1)為G中刪除V1(刪除V1中各頂點及關聯(lián)的邊)后所得圖的連通分支數(shù)。證:設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/9/28離散數(shù)學34e1e2e3e4e5e6v1v2v3v4V1={v1,v4}或V1={v2,v3}

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

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

2023/9/28離散數(shù)學36例6.13利用定理6.6可判斷某些圖不是哈密頓圖設下圖①為G1,取

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

G1-V1為圖②所示,由定理6.6可知G1不是哈密頓圖v①②2023/9/28離散數(shù)學37例6.13利用定理6.6可判斷某些圖不是哈密頓圖設下圖①為G2,在G2中取

V2={a,b,c,d,e,f,g},則G2-V2為圖②所示,P(G2-V2)=9>|V2|=7

由定理6.6可知G2不是哈密頓圖①②abcdefg2023/9/28離散數(shù)學38定理6.7

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

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

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

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

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

一個圖G能畫在平面上，除頂點之外，再沒有邊與邊相交.則稱G為平面圖。畫出的沒有邊交叉的圖稱為G的一個平面嵌入或G的一個平面.在下圖中(2)是(1)(K4