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

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

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

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

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

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

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

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

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

與結(jié)點v關(guān)聯(lián)的環(huán)對v的度數(shù)的貢獻要計算兩次15孤立點：度數(shù)為零的頂點懸掛點：度數(shù)為1的頂點懸掛邊：與懸掛點關(guān)聯(lián)的邊K度點：度數(shù)為k的頂點16【定理】（握手定理）任一圖中，頂點的度數(shù)的總和等于邊數(shù)的二倍，即【推論】任一圖中，奇度數(shù)頂點的個數(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的頂點有6個，余者度數(shù)均小于3，問G至少有幾個頂點？解：由握手定理∑deg(v)=2m=24，度數(shù)為3的頂點有6個占去18度，還有6度由其余頂點占有;而由題意，其余頂點的度數(shù)可為0，1，2;當均為2時所用頂點數(shù)最少，所以應有3個頂點占有此6度，即G中至少有9個頂點。21

【例】

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

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

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

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

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

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

G2。33直觀理解:

G1

G2是指其中一個圖僅經(jīng)過下列兩種變換可以變?yōu)榱硪粋€圖:(a)挪動結(jié)點的位置；(b)伸縮邊的長短。兩個圖同構(gòu)的必要條件:（1）結(jié)點數(shù)目相同；（2）邊數(shù)相同；（3）度數(shù)相同的結(jié)點數(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注意：頂點數(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é)點6鄰接，而G’中d與兩個度數(shù)為1的結(jié)點e、f鄰接，矛盾。39

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

40六、補圖

【定義】

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

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

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

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

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

(accessible)

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

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

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

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

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

62【例】下圖中，圖(a)是強連通圖，圖(b)是單向連通圖，圖(c)是弱連通圖。abcdabcdabcd63第3節(jié)圖的表示64【定義】設(shè)無向圖G的點集為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，因為每條邊恰有兩個端點（若是簡單圖則每列恰有兩個1）。（2），因而全為0的行所對應的頂點是孤立頂點。67*4、有向無環(huán)圖的關(guān)聯(lián)矩陣

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

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

n×n

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

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

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

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

為從結(jié)點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的可達矩陣，其中rij給出了從vi到vj的所有長度為1~n的通路數(shù)目之和。若rij＝0則表示vi到vj不可達。§3圖的可達矩陣83例84說明:容易從圖的可達矩陣得出圖的連通性質(zhì)：1）對無向圖的可達矩陣若rij＝rji>0(i,j=1~n;i≠j),則該圖為連通圖。2）對有向圖的可達矩陣若rij與rji中只有一個大于零(i,j=1~n;i≠j),則該圖為單向連通圖（弱連通圖）。若rij與rji都大于零(i,j=1~n;i≠j),則該圖為雙向連通圖（強連通圖）。85判定算法為：isConnect(A，n)//A為圖的鄰接矩陣，n為圖中點的個數(shù){R=0；//初始矩陣Rfori=1ton{A=MatrixMulti(A,A)//完成矩陣相乘 R=R+A；//進行矩陣相加，計算可達性矩陣}fori=1tonforj=1ton{if(rij=0andi≠j)returnfalse;}returntrue;}86第4節(jié)一些特殊的圖87§1二部圖【定義】無向圖G=〈V，E〉的頂點集V能分成兩個子集V1和V2，滿足（1）V=V1∪V2，V1∩V2=Φ；（2）任給e=（u，v）∈E，均有u∈V1，v∈V2。則稱G為二部圖?！径x】設(shè)G=(V,E)是二部圖，如果V1中每個頂點都與V2中所有頂點鄰接，則稱G為完全二部圖，并記為Km,n，其中m=|V1|，n=|V2|。Km,n的邊數(shù)是多少？88上圖中的三個圖均是二部圖，其中圖（b）是完全二部圖K3，3，圖（c）是K2，4。Km,n的邊數(shù)是多少？89定理一個無向圖是二部圖當且僅當圖中無奇數(shù)長度的回路。90有些圖雖然表面上不是上面的樣式，但經(jīng)過改畫就能成為上面的樣式，仍可判定它是一個二部圖，如上圖中（a）可改畫成圖（b），圖（c）可改畫成圖（d）。91（補）二部圖的應用某公司招聘了3名大學畢業(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é)點的度數(shù)都是偶數(shù)（這樣的頂點稱為偶度結(jié)點）。

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

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

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

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

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

W

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

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

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

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

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

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

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

V,有deg(v)

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

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

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

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

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

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

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