離散數(shù)學(xué)基礎(chǔ)第六章圖論

第六章圖《離散數(shù)學(xué)基礎(chǔ)》——謝勝利1煤氣管道的鋪設(shè)問題。現(xiàn)為城市的各小區(qū)之間鋪設(shè)煤氣管道(如下圖所示)，對n個小區(qū)只需鋪設(shè)n-1條管線，由于地理環(huán)境不同等因素使各條管線所需投資不同，如何使投資成本最低？

圖論問題2第1節(jié)圖的基本概念36.1圖的起源一、哥尼斯堡七橋問題

18世紀(jì)的東普魯士有個哥尼斯堡城，在橫貫全城的普雷格爾河兩岸和兩個島之間架設(shè)了7座橋，它們把河的兩岸和兩個島連接起來。從河岸或小島出發(fā)，七座橋每座橋恰好通過一次，再回到原地，是否可能？6.1圖的基本概念4

數(shù)學(xué)大師歐拉對七橋問題給出否定回答，并給出嚴(yán)格的證明(Euler圖)。1736年，歐拉對七橋問題的抽象和論證思想，開創(chuàng)了圖論的研究，這一年可以看成是圖論的元年。5二、Hamilton環(huán)球旅行游戲1895年，Hamilton設(shè)計一個“環(huán)球旅行”游戲：

在一個正12面體的20個頂點(diǎn)上各標(biāo)志一個城市，如果從一城市出發(fā)，沿正12面體的棱行走，每個城市恰好經(jīng)過一次，再回到出發(fā)點(diǎn)，則算旅行成功。6

對于該游戲的抽象得到圖論中一個很重要的概念：Hamilton圖。7一、圖的概念

定義5.1.1圖G(graph)主要由2部分組成:(1)結(jié)點(diǎn)集合V,其中的元素稱為結(jié)點(diǎn)或頂點(diǎn)(vertex或node).(2)邊集合E,其中的元素稱為邊(edge).通常將圖G記為G=(V,E).§1無向圖和有向圖81、圖繪制的幾點(diǎn)說明:(a)結(jié)點(diǎn)或頂點(diǎn)，常用一個實(shí)心點(diǎn)或空心點(diǎn)表示，但在實(shí)際應(yīng)用中還可以用諸如方形、圓形、菱形等符號。(b)邊的表示：無向邊，例：e3=（v3,v4）=（v4,v3）有向邊(弧)，例：e8=<v2,v3>起點(diǎn)終點(diǎn)e3v3v4e8v2v39有向圖無向圖2、圖的基本術(shù)語有向圖：圖中各邊都是有向邊無向圖：圖中各邊都是無向邊混合圖：圖中既有有向邊又有無向邊10頂點(diǎn)與邊的關(guān)聯(lián)：若從結(jié)點(diǎn)u到結(jié)點(diǎn)v有邊l，則稱邊l與結(jié)點(diǎn)u和v相關(guān)聯(lián)(incident)

。頂點(diǎn)與頂點(diǎn)的鄰接：若從結(jié)點(diǎn)u到結(jié)點(diǎn)v有邊，則結(jié)點(diǎn)u和v互為鄰接頂點(diǎn)。無向圖邊與邊的鄰接：有公共端點(diǎn)的邊互為鄰接邊無向圖有向圖11有限圖：圖中僅有有限個頂點(diǎn)。（無限圖：圖中有無限個頂點(diǎn)。）N階圖：具有n個頂點(diǎn)的有限圖。零圖：只有頂點(diǎn)而沒有邊的圖平行邊：兩頂點(diǎn)之間有多條邊（若為有向圖則方向也相同）。邊的重數(shù)：兩頂點(diǎn)間平行邊的條數(shù)。多重圖：含有平行邊的多重圖。自環(huán)（自回路）：兩個端點(diǎn)重合的邊簡單圖：不含平行邊且不含自環(huán)的圖。1213權(quán)重圖（賦權(quán)圖）：設(shè)G=(V,E)是任意圖，若G的每一條邊上都賦予一個非負(fù)實(shí)數(shù)，則稱G是權(quán)重圖（邊賦權(quán)圖）。每條邊上所賦的非負(fù)實(shí)數(shù)稱為這條邊上的權(quán)，它可以理解為該邊上的流量或通過該邊的時間，還可以理解為該邊的長度。14二、圖中頂點(diǎn)的度數(shù)1、無向圖中頂點(diǎn)的度數(shù)【定義】在圖（無向圖或有向圖）中，若頂點(diǎn)a和b是邊e的兩個端點(diǎn)，則稱頂點(diǎn)a和b是鄰接的，并稱邊e關(guān)聯(lián)于頂點(diǎn)a和b。【定義】設(shè)圖G是無向圖，v是圖G中的頂點(diǎn)，與v關(guān)聯(lián)的邊的條數(shù)稱為頂點(diǎn)v的度數(shù)，記作deg(v)。

與結(jié)點(diǎn)v關(guān)聯(lián)的環(huán)對v的度數(shù)的貢獻(xiàn)要計算兩次15孤立點(diǎn)：度數(shù)為零的頂點(diǎn)懸掛點(diǎn)：度數(shù)為1的頂點(diǎn)懸掛邊：與懸掛點(diǎn)關(guān)聯(lián)的邊K度點(diǎn)：度數(shù)為k的頂點(diǎn)16【定理】（握手定理）任一圖中，頂點(diǎn)的度數(shù)的總和等于邊數(shù)的二倍，即【推論】任一圖中，奇度數(shù)頂點(diǎn)的個數(shù)必為偶數(shù)。17由定理及其推論容易知道：在任何一次聚會上，所有人握手次數(shù)之和必為偶數(shù)并且握了奇數(shù)次手的人數(shù)必為偶數(shù)。(平行邊及環(huán)的解釋?)18【例】下列各組數(shù)中，哪些可以構(gòu)成無向圖的度數(shù)列：（1）1，1，1，2，2（2）2，2，2，2，3（3）2，3，3，3，3（4）2，2，2，2，219【例】求解下列各題:(1)圖G的度數(shù)列為2，2，3，5，6，則邊數(shù)m為多少?解：由握手定理：2m=∑deg(v)=2+2+3+5+6=18，知m=9。20(2)圖G有12條邊，度數(shù)為3的頂點(diǎn)有6個，余者度數(shù)均小于3，問G至少有幾個頂點(diǎn)？解：由握手定理∑deg(v)=2m=24，度數(shù)為3的頂點(diǎn)有6個占去18度，還有6度由其余頂點(diǎn)占有;而由題意，其余頂點(diǎn)的度數(shù)可為0，1，2;當(dāng)均為2時所用頂點(diǎn)數(shù)最少，所以應(yīng)有3個頂點(diǎn)占有此6度，即G中至少有9個頂點(diǎn)。21

【例】

證明:在n（n≥2）個人的團(tuán)體中，必有兩個人有相同個數(shù)的朋友。

解：以頂點(diǎn)代表人，二人如果是朋友，則在代表他們的頂點(diǎn)間連上一條邊，這樣可得簡單無向圖G，每個人的朋友數(shù)即圖中代表它的頂點(diǎn)的度數(shù)，于是問題轉(zhuǎn)化為：

n階簡單無向圖G中必有兩個頂點(diǎn)的度數(shù)相同。22（2）有向圖中頂點(diǎn)的度數(shù)【定義】設(shè)圖G是有向圖，v是G的頂點(diǎn)，以v為始點(diǎn)的有向邊的條數(shù)稱為v的出度，稱為deg+(v),以v為終點(diǎn)的有向邊的條數(shù)稱為v的入度，稱為deg-(v)。例：deg+(a)=2deg-(a)=1deg+(b)=0deg-(b)=2deg+(c)=1deg-(c)=2deg+(d)=2deg-(d)=2deg+(e)=2deg-(e)=023【定理】設(shè)圖G是有向圖，G中含有n個頂點(diǎn)和m條邊，則圖中各頂點(diǎn)的的出度之和與各頂點(diǎn)的入度之和相等，且等于圖的邊數(shù)。24三、特殊圖【定義】設(shè)圖G為無向簡單圖，如果圖G中各個頂點(diǎn)的度數(shù)都為k，則稱G為k度正則圖，記為k-正則圖25三、特殊圖【定義】在n階無向簡單圖中，如果任意兩個不同的頂點(diǎn)之間都有一條邊關(guān)聯(lián)，則稱此無向簡單圖為無向完全圖，記作Kn。無向完全圖Kn的邊數(shù)是多少？

【定理】在n階無向完全圖Kn中，共有n(n-1)/2條邊。26【定義】在n階有向圖中，如果任意兩個不同的頂點(diǎn)之間都有兩條方向相反的有向邊關(guān)聯(lián)，且每一個頂點(diǎn)都有自回路，則稱此有向圖為有向完全圖。有向完全圖各頂點(diǎn)的入度與出度是多少？三、特殊圖

27四、子圖【定義】在圖G中刪去一些邊或頂點(diǎn)后所得的圖稱為圖G的子圖。刪邊：刪去圖中某一條邊，但仍保留這條邊的兩個端點(diǎn)。刪點(diǎn)：刪去圖中某一點(diǎn)以及與這個點(diǎn)關(guān)聯(lián)的所有邊。28刪邊刪點(diǎn)29【定義】由圖G中刪去一些邊后所得到的子圖稱為圖G的生成子圖?！径x】在圖G中僅刪去一個頂點(diǎn)后所得的子圖稱為圖G的主子圖。30子圖示例:31五、圖的同構(gòu)由于在畫圖的圖形時，頂點(diǎn)的位置和邊的幾何形狀是無關(guān)緊要的，因此表面上完全不同的圖形可能表示的是同一個圖。32定義為了判斷不同的圖形是否反映同一個圖形的性質(zhì)，我們給出圖的同構(gòu)的概念。設(shè)有兩個圖G1=(V1,E1)，G2=(V2,E2)，如果存在著雙射：V1→V2，使得(u,v)∈E1當(dāng)且僅當(dāng)((u),(v))∈E2

且邊的重數(shù)相同，則稱圖G1與G2同構(gòu)，記作G1

G2。33直觀理解:

G1

G2是指其中一個圖僅經(jīng)過下列兩種變換可以變?yōu)榱硪粋€圖:(a)挪動結(jié)點(diǎn)的位置；(b)伸縮邊的長短。兩個圖同構(gòu)的必要條件:（1）結(jié)點(diǎn)數(shù)目相同；（2）邊數(shù)相同；（3）度數(shù)相同的結(jié)點(diǎn)數(shù)相同。34例：35例：36【示例】下圖中，G1G2，其中

f：V1→V2，f（vi）=ui（i=1，2，…，6）。

G3

G4，其中

f：V1→V2，f（v1）=u3，f（v2）=u1，f（v3）=u237注意：頂點(diǎn)數(shù)相同、邊數(shù)相同、度數(shù)列相同為二圖同構(gòu)的必要條件而非充分條件38【例】證明下圖中，G與G’不同構(gòu)。125634GabefcdG’分析

證明兩個圖不同構(gòu)，通常用反證法。證明

假設(shè)G≌G’，雙射函數(shù)為。由定義，v與(v)的度數(shù)一定相同，因此有(3)=d。G中3與一個度數(shù)為1的結(jié)點(diǎn)6鄰接，而G’中d與兩個度數(shù)為1的結(jié)點(diǎn)e、f鄰接，矛盾。39

在圖的集合上定義二元關(guān)系R：對于圖G1、G2，G1RG2當(dāng)且僅當(dāng)G1和G2同構(gòu)，稱R為圖的同構(gòu)關(guān)系。容易證明，圖的同構(gòu)關(guān)系是等價關(guān)系。

40六、補(bǔ)圖

【定義】

G為n階簡單圖，由G的所有頂點(diǎn)和能使G成為完全圖的添加邊所構(gòu)成的圖稱為G的相對于完全圖的補(bǔ)圖，簡稱G的補(bǔ)圖，記作。

41【例】下圖中是G相對于K5的補(bǔ)圖。42對于補(bǔ)圖,顯然有以下結(jié)論(3)n階完全圖與n階零圖互為補(bǔ)圖43第2節(jié)圖的連通性44一、通路與回路

右圖是中國鐵路交通圖的一部分，旅客乘火車旅行，相當(dāng)于從一個結(jié)點(diǎn)出發(fā)，沿著一些邊連續(xù)移動到另一個結(jié)點(diǎn)，這就引出了通路的概念。成都昆明重慶廣州長沙武漢上海蘭州西安沈陽北京天津鄭州廈門高雄臺北45一、通路定義在任意一個圖G=(V,E)中，稱G中結(jié)點(diǎn)與邊交替出現(xiàn)的序列L：為從v0到vn的一條通路或路徑。ei的起點(diǎn)ei的終點(diǎn)通路的起點(diǎn)通路的終點(diǎn)46通路的長度：一條路中所包含的邊數(shù)。對于權(quán)重圖，通路的長度為通路中各邊的權(quán)重之和。47路的簡記：1)結(jié)點(diǎn)序列2)邊序列48

【例】一個人帶著一只狼、一只羊和一捆草要渡河，由于船太小，人做擺渡者一次只能運(yùn)送一個“乘客”，很顯然，如果人不在，狼要吃羊，羊要吃草，問人怎樣才能把它們安全地渡過河去？49解：這是通路問題的一個典型實(shí)例。用f表示人，w表示狼，s表示羊，h表示草。集合{f，w，s，h}中能安全在一起的子集有：{f，w，s，h}，{f，w，s}，{f，s，h}，{f，w，h}，{f，w}，{f，s}，{f，h}，{w，h}，{f}，{w}，{s}，{h}。50原岸對岸{f，w，s，h}{}{f，w，s}{h}{f，s，h}{w}{f，w，h}{s}{f，s}{w，h}原岸對岸{}{f，w，s，h}{h}{f，w，s}{w}{f，s，h}{s}{f，w，h}{w，h}{f，s}初始狀態(tài)結(jié)束狀態(tài)渡河過程中所有可能的安全狀態(tài)：可以使用二元組表示安全狀態(tài)：第一元素表示留在原岸的子集，第二元素表示留在對岸的子集。51用頂點(diǎn)表示渡河過程中的狀態(tài)，將可以通過一次渡河進(jìn)行轉(zhuǎn)換的狀態(tài)利用一條有向邊鏈接。容易看出，一條路徑就是一種渡河方案。52二、回路定義1）起點(diǎn)與終點(diǎn)相同的通路(長度1)稱為回路(circuit)。2）邊不重復(fù)的回路稱為簡單回路。3）除起點(diǎn)重復(fù)一次外,別的結(jié)點(diǎn)均不重復(fù)的簡單回路稱為基本回路或環(huán)(cycle)。53v0到v0的回路：簡單回路，也是基本回路簡單回路，非基本回路54定理在一個n階圖中，若從頂點(diǎn)u到頂點(diǎn)v（u≠v）存在通路，則從u到v存在長度小于等于n-1的基本通路。

在一個n階圖中，若從頂點(diǎn)u到自身存在回路，則從u到自身存在長度小于等于n的基本回路。55三、圖的連通性由于結(jié)點(diǎn)v到v總存在一條長度為0的路,因此規(guī)定：任意結(jié)點(diǎn)v可達(dá)v自身。定義5.1.8若從圖的結(jié)點(diǎn)u到v存在一條路,則稱u到v是可達(dá)的

(accessible)

。56定義若無向圖G中任意兩點(diǎn)均可達(dá)，則稱G是連通圖，否則稱G是非連通圖或不連通圖。特別地，單獨(dú)一個結(jié)點(diǎn)是連通圖。定義如果無向圖是非連通圖，則圖能分解為k個不相交的連通子圖，稱連通子圖為此非連通圖的連通分支。57【例】下圖所示：圖G1是連通圖；圖G2是一個非連通圖。58

【例】在一次國際會議中，由七人組成的小組{a,b,c,d,e,f,g}中：a會英語、阿拉伯語；b會英語、西班牙語；c會漢語、俄語；d會日語、西班牙語；e會德語、漢語和法語；f會日語、俄語；g會英語、法語和德語。問：他們中間任何二人是否均可對話（必要時可通過別人翻譯）？5960

【定義】設(shè)圖G是無向連通圖，如果圖G中存在一個頂點(diǎn)v，使得刪去頂點(diǎn)v后，圖G成為不連通圖，則稱v為割點(diǎn)。

【定義】設(shè)圖G是無向連通圖，如果圖G中存在一條邊u，使得刪去邊u后，圖G成為不連通圖，則稱v為割邊或橋。61

【定義】在簡單有向圖G中，若任二頂點(diǎn)間均相互可達(dá)，則稱G為強(qiáng)連通圖；若任二頂點(diǎn)間至少從一個頂點(diǎn)到另一個頂點(diǎn)是可達(dá)的，則稱G是單向連通圖；若在忽略G中各邊的方向時G是無向連通圖，則稱G是弱連通圖。

62【例】下圖中，圖(a)是強(qiáng)連通圖，圖(b)是單向連通圖，圖(c)是弱連通圖。abcdabcdabcd63第3節(jié)圖的表示64【定義】設(shè)無向圖G的點(diǎn)集為V，邊集為E，且V={v1，v2，…，vn}，E={e1,e2,…,em},令則稱(mij)

n×m

為G的關(guān)聯(lián)矩陣，記作M(G)§1圖的關(guān)聯(lián)矩陣65【例】求下圖G的關(guān)聯(lián)矩陣。66無向圖的關(guān)聯(lián)矩陣的特性：（1），即M(G)每列元素之和為2，因為每條邊恰有兩個端點(diǎn)（若是簡單圖則每列恰有兩個1）。（2），因而全為0的行所對應(yīng)的頂點(diǎn)是孤立頂點(diǎn)。67*4、有向無環(huán)圖的關(guān)聯(lián)矩陣

【定義】設(shè)G=〈V,E〉是有向無環(huán)圖，

V={v1，v2，…，vn}，E={e1，e2，…，em}，令vi是ej的起點(diǎn)vi與ej不關(guān)聯(lián)vi是ej的終點(diǎn)則稱(mij)

n×n

為G的關(guān)聯(lián)矩陣，記作M(G)。6869M(G)的特性：

（1）（一條邊關(guān)聯(lián)兩個點(diǎn)：一個起點(diǎn)，一個終點(diǎn)），從而有。（2）每一行中1的數(shù)目是該點(diǎn)的出度，-1的數(shù)目是該點(diǎn)的入度。（3）二列相同，當(dāng)且僅當(dāng)對應(yīng)的邊是平行邊（同向）。（4）全為0的行對應(yīng)孤立頂點(diǎn)。70

注:無向圖也有相應(yīng)的鄰接矩陣，一般只考慮簡單圖，無向圖的鄰接矩陣是對稱的，其性質(zhì)基本與有向圖鄰接矩陣的性質(zhì)相同。71定義設(shè)圖G=(V,E)，V={v1,v2,…,vn}，則稱矩陣為圖G的鄰接矩陣，其中aij是vi鄰接到vj的邊數(shù),i,j=1,2,…,n?！?圖的鄰接矩陣

72無向圖中自環(huán)對應(yīng)主對角線上元素是1還是2？73由鄰接矩陣很容易地看出：一個矩陣元素全為0則其對應(yīng)的圖為零圖。一矩陣的元素除對角線元素為0外，全為1則其對應(yīng)的圖為完全圖。對于無向圖，其鄰接矩陣關(guān)于主對角線對稱。一個圖與其鄰接矩陣是一一對應(yīng)的。對權(quán)重圖，aij可取該邊的權(quán)重。74從一個圖G的鄰接矩陣A(G)容易得出每個結(jié)點(diǎn)的度數(shù)：1）有向圖：752）無向圖：76練習(xí)現(xiàn)有如下所示圖：(1)寫出該圖的關(guān)聯(lián)矩陣和鄰接矩陣。(2)求各個頂點(diǎn)的度。(3)圖中是否存在平行邊？如果存在，請指出。77定理設(shè)A是圖G的鄰接矩陣,則Al中(i,j)位置元素aij(l)

為從結(jié)點(diǎn)vi到vj長度為l(l

1)的路的數(shù)目。78例：在圖G中，求出：（1）從v2到v4長度為1,2,3,4的通路各有多少條？（2）長度為3的路共有多少條？其中有多少條是回路？解：鄰接矩陣798081（1）從v2到v4長度為1,2,3,4的通路分別有1,0,0,4條。（2）由于A3中所有元素之和為20,所以長度為3的路共有20條。又由于對角線上元素之和為12，故其中有12條是回路。82定義設(shè)圖G=(V,E)，V={v1,v2,…,vn}，則稱矩陣為圖G的可達(dá)矩陣，其中rij給出了從vi到vj的所有長度為1~n的通路數(shù)目之和。若rij＝0則表示vi到vj不可達(dá)?！?圖的可達(dá)矩陣83例84說明:容易從圖的可達(dá)矩陣得出圖的連通性質(zhì)：1）對無向圖的可達(dá)矩陣若rij＝rji>0(i,j=1~n;i≠j),則該圖為連通圖。2）對有向圖的可達(dá)矩陣若rij與rji中只有一個大于零(i,j=1~n;i≠j),則該圖為單向連通圖（弱連通圖）。若rij與rji都大于零(i,j=1~n;i≠j),則該圖為雙向連通圖（強(qiáng)連通圖）。85判定算法為：isConnect(A，n)//A為圖的鄰接矩陣，n為圖中點(diǎn)的個數(shù){R=0；//初始矩陣Rfori=1ton{A=MatrixMulti(A,A)//完成矩陣相乘 R=R+A；//進(jìn)行矩陣相加，計算可達(dá)性矩陣}fori=1tonforj=1ton{if(rij=0andi≠j)returnfalse;}returntrue;}86第4節(jié)一些特殊的圖87§1二部圖【定義】無向圖G=〈V，E〉的頂點(diǎn)集V能分成兩個子集V1和V2，滿足（1）V=V1∪V2，V1∩V2=Φ；（2）任給e=（u，v）∈E，均有u∈V1，v∈V2。則稱G為二部圖。【定義】設(shè)G=(V,E)是二部圖，如果V1中每個頂點(diǎn)都與V2中所有頂點(diǎn)鄰接，則稱G為完全二部圖，并記為Km,n，其中m=|V1|，n=|V2|。Km,n的邊數(shù)是多少？88上圖中的三個圖均是二部圖，其中圖（b）是完全二部圖K3，3，圖（c）是K2，4。Km,n的邊數(shù)是多少？89定理一個無向圖是二部圖當(dāng)且僅當(dāng)圖中無奇數(shù)長度的回路。90有些圖雖然表面上不是上面的樣式，但經(jīng)過改畫就能成為上面的樣式，仍可判定它是一個二部圖，如上圖中（a）可改畫成圖（b），圖（c）可改畫成圖（d）。91（補(bǔ)）二部圖的應(yīng)用某公司招聘了3名大學(xué)畢業(yè)生，公司有5個部門需要人。不考慮單向的意愿，畢業(yè)生意愿去這個部門，這個部門也同意接收這名畢業(yè)生如表所示。部門1部門2部門3部門4部門5畢業(yè)生A***畢業(yè)生B***畢業(yè)生C***有什么分配方案使得在每個部門最多可接收一個畢業(yè)生的前提下畢業(yè)生都滿意！92定義設(shè)G=(V,E)是任意圖,則G中經(jīng)過所有邊一次且僅一次的通路稱為歐拉通路;G中經(jīng)過所有邊一次且僅一次的回路稱為歐拉回路;存在歐拉回路的圖稱為歐拉圖或簡稱為E圖.

一、歐拉圖的有關(guān)概念§2歐拉圖93定理連通無向圖G是歐拉圖的充要條件是G的每個結(jié)點(diǎn)的度數(shù)都是偶數(shù)（這樣的頂點(diǎn)稱為偶度結(jié)點(diǎn)）。

二、歐拉定理定理有向圖G是歐拉圖的充要條件是G的每個結(jié)點(diǎn)的入度等于其出度。94由于在七橋問題的圖中，有４個點(diǎn)是奇度頂點(diǎn)，故不存在歐拉回路，七橋問題無解。95圖中存在歐拉回路:96定理設(shè)G是連通無向圖,則G中存在歐拉通路的充要條件是G的度數(shù)為奇數(shù)的結(jié)點(diǎn)個數(shù)為0或為2。根據(jù)該定理知,“七橋問題”甚至不存在歐拉軌跡。97圖中存在歐拉通路，但不存在歐拉回路。98“一筆畫問題”：所謂一個圖能一筆畫出是指從圖的某結(jié)點(diǎn)出發(fā)，線可以相交但不能重合，不起筆就可以將圖畫完。如果該圖為歐拉圖，則能夠一筆畫完該圖，并且筆又回到出發(fā)點(diǎn)；如果該圖只存在歐拉通路，則能夠一筆畫完該圖，但筆回不到出發(fā)點(diǎn)；如果該圖中不存在歐拉通路，則不能一筆畫完該圖。99【例】圖中的三個圖能否一筆畫？為什么？v1v2v3v4v5(b)v1v2v3v4(c)v1v2v3v4v5(a)解

因為圖(a)和(b)中分別有0個和2個奇度數(shù)結(jié)點(diǎn)，所以它們分別是歐拉圖和存在歐拉通路，因此能夠一筆畫，并且在(a)中筆能回到出發(fā)點(diǎn)，而(b)中筆不能回到出發(fā)點(diǎn)。圖c中有4個度數(shù)為3的結(jié)點(diǎn)，所以不存在歐拉通路，因此不能一筆畫。100螞蟻比賽問題：

【例】甲、乙兩只螞蟻分別位于圖的結(jié)點(diǎn)A、B處，并設(shè)圖中的邊長度相等。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過圖中所有邊最后到達(dá)結(jié)點(diǎn)C處。如果它們的速度相同，問誰先到達(dá)目的地？A(甲)B(乙)C解

圖中僅有兩個度數(shù)為奇數(shù)的結(jié)點(diǎn)B、C，因而存在從B到C的歐拉通路，螞蟻乙走到C只要走一條歐拉通路，邊數(shù)為9條，而螞蟻甲要想走完所有的邊到達(dá)C，至少要先走一條邊到達(dá)B，再走一條歐拉通路，因而它至少要走10條邊才能到達(dá)C，所以乙必勝。101

例下圖是一幢房子的平面圖形，前門進(jìn)入一個客廳，由客廳通向4個房間。如果要求每扇門只能進(jìn)出一次，現(xiàn)在你由前門進(jìn)去，能否通過所有的門走遍所有的房間和客廳，然后從后門走出。奇度頂點(diǎn)奇度頂點(diǎn)奇度頂點(diǎn)奇度頂點(diǎn)不存在歐拉通路，所以，此題無解。102定義5.5.1設(shè)G=(V,E)是任意圖,則G中經(jīng)過所有結(jié)點(diǎn)一次且僅一次的通路稱為漢密爾頓通路;G中經(jīng)過所有結(jié)點(diǎn)一次且僅一次(除起點(diǎn)重復(fù)一次外)的回路稱為漢密爾頓回路;存在漢密爾頓回路的圖稱為漢密爾頓圖。一、漢密爾頓圖的有關(guān)概念§3漢密爾頓圖103由漢密爾頓回路可得到漢密爾頓路徑,但反過來一般不成立。如(a)存在漢密爾頓路徑bcade,但不存在漢密爾頓回路。(b)存在漢密爾頓回路v1v5v4v3v2v1,它是漢密爾頓圖。104例：漢密爾頓回路問題。它是1859年漢密爾頓首先提出的一個關(guān)于12面體的數(shù)學(xué)游戲：能否在下圖中找到一個回路，使它含有圖中所有頂點(diǎn)一次且僅一次？這個問題也被稱作周游世界問題。105盡管漢密爾頓回路與歐拉回路問題在形式上極為相似，但是到目前為止還不知道一個圖為漢密爾頓圖的充要條件，尋找該充要條件仍是圖論中尚未解決的主要問題之一。下面先給出一個簡單而有用的必要條件。106定理設(shè)圖G＝（V,E）是漢密爾頓無向圖，則對于任意

W

V,均有w(G-W)|W|成立，其中w(G-W)是圖G－W的連通分支數(shù)。

二、漢密爾頓圖的必要條件107上述定理在應(yīng)用中它本身用處不大，但它的逆否命題卻非常有用。我們經(jīng)常利用其逆否命題來判斷某些圖不是漢密爾頓圖，即：若存在V的某個非空子集W使得w(G-W)＞|W|，則G不是漢密爾頓圖。

108例如：考慮下圖中的(a)刪去的頂點(diǎn)刪去的頂點(diǎn)3個連通分支所以(a)不是漢密爾頓圖109判斷圖(a),(b)是不是漢密爾頓圖:v3v1v2v4v5v6v7v2v4v1v5v3(a)(b)刪去的頂點(diǎn)刪去的頂點(diǎn)刪去的頂點(diǎn)110定理設(shè)G=(V,E)是n(n

3)階簡單無向圖,若對于任意的不相鄰結(jié)點(diǎn)u,v

V,有deg(u)＋deg(v)≥n則G是漢密爾頓圖。

三、漢密爾頓圖的充分條件111注意，上述定理給出的是漢密爾頓圖的充分條件，而不是必要條件。例如,在六邊形中，任兩個不相鄰的結(jié)點(diǎn)的度數(shù)之和都是4＜6，但六邊形是漢密頓圖。112推論設(shè)G=(V,E)是n(n

3)階簡單無向圖,若對于任意結(jié)點(diǎn)v

V,有deg(v)

n/2,則G是漢密爾頓圖。113定理設(shè)G=(V,E)是n(n

3)階簡單無向圖,若對于任意的不相鄰結(jié)點(diǎn)u,v

V,有deg(u)＋deg(v)≥n-1則在G中存在漢密爾頓路徑。

114【例】某地有5個風(fēng)景點(diǎn)，若每個風(fēng)景點(diǎn)均有2條道路與其他點(diǎn)相通。問游人可否經(jīng)過每個風(fēng)景點(diǎn)恰好一次而游完這5處？解

將5個風(fēng)景點(diǎn)看成是有5個頂點(diǎn)的無向圖(n=5)，兩風(fēng)景點(diǎn)間的道路看成是無向圖的邊。因為每處均有兩條道路與其他頂點(diǎn)相通，故每個頂點(diǎn)的度數(shù)均為2，從而任意兩個不同頂點(diǎn)的度數(shù)之和等于4，正好為總頂點(diǎn)數(shù)n減1。故此圖中存在一條漢密頓路徑，因此游人可以經(jīng)過每個風(fēng)景點(diǎn)恰好一次而游完這5處。115小結(jié)：歐拉通路與歐拉回路判別準(zhǔn)則

對無向連通圖，只需通過對圖中各結(jié)點(diǎn)度數(shù)的計算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖；對有向連通圖，只需通過對圖中各結(jié)點(diǎn)出度與入度的計算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖。116第5節(jié)最短路徑117在權(quán)重圖中，從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)的通路上所有邊上的權(quán)之和稱為該通路的“權(quán)”。在實(shí)際應(yīng)用中，經(jīng)常需要得出從一個結(jié)點(diǎn)到別的結(jié)點(diǎn)權(quán)最小的一條路徑（通路），稱為最短路徑?！?Dijkstra算法118例：（Dijkstra算法原理）結(jié)點(diǎn)v1到v6的最短路徑？思路：依次求出距v1最近的結(jié)點(diǎn)（直至到達(dá)所求結(jié)點(diǎn)）及其最短路徑。119步驟：到結(jié)點(diǎn)v1最近的結(jié)點(diǎn)是v4，最短路徑是2。到結(jié)點(diǎn)v1第二近的結(jié)點(diǎn)是v2，最短路徑是4（只需在與v1及v4鄰接的結(jié)點(diǎn)中搜索）。到結(jié)點(diǎn)v1第三近的結(jié)點(diǎn)是v5，最短路徑是5（只需在與v1、v4及v2鄰接的結(jié)點(diǎn)中搜索）。到結(jié)點(diǎn)v1第四近的結(jié)點(diǎn)是v6，最短路徑是6（只需在與v1、v4、v2及v5鄰接的結(jié)點(diǎn)中搜索）。120Dijkstra算法：設(shè)G=(V,E)是n階權(quán)重圖，V={v1,v2,…,vn},用wij表示結(jié)點(diǎn)vi到vj的邊上的權(quán)，若vi到vj無邊，則令wij=+。

目標(biāo):求結(jié)點(diǎn)v1到其他任意結(jié)點(diǎn)的最短路徑。121基本思想：設(shè)置一個集合S（也可以看作紅點(diǎn)集）存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源點(diǎn)v，對vi∈V-S（也可以看作藍(lán)點(diǎn)集）