圖論圖論圖論是用圖的方法研究客觀世界的一門(mén)科學(xué).用“結(jié)點(diǎn)”表示事物,用“邊”表示事物之間聯(lián)系,而由結(jié)點(diǎn)與邊所構(gòu)成的圖表示所研究的客觀對(duì)象.圖論研究圖的邏輯結(jié)構(gòu)與性質(zhì)，是研究圖的抽象性質(zhì)的一種數(shù)學(xué).圖論圖論在語(yǔ)言學(xué)、邏輯學(xué)、物理學(xué)、化學(xué)、電氣工程、計(jì)算機(jī)網(wǎng)絡(luò)、計(jì)算機(jī)科學(xué)及數(shù)學(xué)的其他分支中有廣泛應(yīng)用.在計(jì)算機(jī)科學(xué)中，圖論在形式語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)及數(shù)據(jù)庫(kù)研究中均有很重要的應(yīng)用.本篇結(jié)構(gòu)第八章介紹圖論一般原理第九章介紹一些常用的圖如平面圖、兩步圖以及樹(shù)等第八章圖論原理本章主要介紹圖論的基本原理，包括圖論中的基本概念、基本方法以及圖論的矩陣計(jì)算等內(nèi)容.8.1.1圖起源：歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過(guò)。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問(wèn)題有很強(qiáng)的實(shí)際背景。

LeonhardEuler，(1707—1783)，瑞士數(shù)學(xué)家、力學(xué)家、天文學(xué)家、物理學(xué)家，圖論的創(chuàng)始人，變分法的奠基人，復(fù)變函數(shù)論的先驅(qū)者，理論流體力學(xué)的創(chuàng)始人。8.1.1圖著名的柯尼斯堡七橋問(wèn)題。在柯尼斯堡的普萊格爾河上有七座橋?qū)⒑又械膷u及島與河岸聯(lián)結(jié)起來(lái)，如下圖所示，A、B、C，D表示陸地。問(wèn)題是要從這四塊陸地中任何一塊開(kāi)始，通過(guò)每一座橋正好一次，再回到起點(diǎn)。8.1.1圖歐拉在1736年解決了這個(gè)問(wèn)題，他用抽象分析法將這個(gè)問(wèn)題化為第一個(gè)圖論問(wèn)題：即把每一塊陸地用一個(gè)點(diǎn)來(lái)代替，將每一座橋用聯(lián)接相應(yīng)的兩個(gè)點(diǎn)的一條線來(lái)代替，從而相當(dāng)于得到一個(gè)「圖」。歐拉證明了這個(gè)問(wèn)題沒(méi)有解，并且推廣了這個(gè)問(wèn)題，給出了對(duì)於一個(gè)給定的圖可以某種方式走遍的判定法則。這項(xiàng)工作使歐拉成為圖論〔及拓?fù)鋵W(xué)〕的創(chuàng)始人。8.1.2圖的基本概念定義8.1

圖G是由非空結(jié)點(diǎn)集合V={v1,v2,…,vn}以及邊集合E={l1,l2,…,lm}所組成,其中每條邊可用一個(gè)節(jié)點(diǎn)對(duì)表示,亦即li=(vi1,vi2),i=1,2,…,m

這樣一個(gè)圖G可用G=<V,E>表示8.1.2圖的基本概念例8.1有4個(gè)城市:v1,v2,v3,v4,其中v1與v2間;v1與v4間;v2與v3間有直達(dá)長(zhǎng)話線路相連,將此試試用圖的方式表示解:

圖中的結(jié)點(diǎn)集為:V={v1,v2,v3,v4}

邊集為E={l1,l2,l3} l1={v1,v2},l2={v1,v4},l3={v2,v3},-------無(wú)序結(jié)點(diǎn)對(duì) 這個(gè)圖可以用G=<V,E>表示

8.1.2圖的基本概念例8.2有4個(gè)程序p1,p2,p3,p4,它們間有一些調(diào)用關(guān)系：p1調(diào)用p2；p2能調(diào)用p3；p1能調(diào)用p4,試將此事實(shí)用圖的方式表示.解： 圖中的結(jié)點(diǎn)集為:V={p1,p2,p3,p4}

邊集為E={c1,c2,c3} c1={p1,p2},c2={p2,p3},c3={p1,p4},-----有序結(jié)點(diǎn)對(duì) 這個(gè)圖可以用G=<V,E>表示8.1.2圖的基本概念一般，用帶有箭頭的邊表示有序結(jié)點(diǎn)對(duì)，而用不帶箭頭的邊表示無(wú)序結(jié)點(diǎn)對(duì).8.1.2圖的基本概念有序結(jié)點(diǎn)對(duì)所對(duì)應(yīng)的邊稱(chēng)為有向邊，無(wú)序結(jié)點(diǎn)對(duì)所對(duì)應(yīng)的邊稱(chēng)為無(wú)向邊有向圖：圖中的所有邊均為有向邊無(wú)向圖：圖中的所有邊均為無(wú)向邊8.1.2圖的基本概念有向邊lk={vi,vj}中,vi稱(chēng)為lk的起點(diǎn),vj稱(chēng)為lk的終點(diǎn)不管lk是有向還是無(wú)向,均稱(chēng)lk與vi和vj相關(guān)聯(lián),而vi和vj稱(chēng)為鄰接的.若干條邊關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn),則這些邊稱(chēng)為鄰接的.8.1.2圖的基本概念一條邊若與兩個(gè)相同的結(jié)點(diǎn)相關(guān)聯(lián),則稱(chēng)為環(huán),即lk={vi,vi}不與任何結(jié)點(diǎn)相鄰的結(jié)點(diǎn)稱(chēng)為孤立點(diǎn)8.1.2圖的基本概念圖G=<V,E>與G’=<V’,E’>間如果有V’?V,E?E’,則稱(chēng)G’是G的子圖.如果有V’?V,E?E’,則稱(chēng)G’是G的真子圖.如果有V’=V,E?E’,則稱(chēng)G’是G的生成子圖.8.1.2圖的基本概念(n,m)圖:一個(gè)具有n個(gè)結(jié)點(diǎn)、m條邊所組成的圖零圖:由一些孤立點(diǎn)組成的圖,即(n,0)圖平凡圖:由一個(gè)孤立結(jié)點(diǎn)組成的圖,即(1,0)圖完全圖:一個(gè)(n,m)圖G如果其n個(gè)結(jié)點(diǎn)(n≥2)中的每一個(gè)均與其中n-1個(gè)結(jié)點(diǎn)鄰接,可記為Kn.m=n(n-1)/28.1.2圖的基本概念8.1.2圖的基本概念補(bǔ)圖： 設(shè)有一圖G=(V,E),對(duì)圖G’=(V,E’),如果有 是完全圖且E∩E’=?

則稱(chēng)G’是G的補(bǔ)圖.一個(gè)圖與其補(bǔ)圖是互補(bǔ)的一個(gè)圖的補(bǔ)圖的補(bǔ)圖還是自己8.1.3圖的同構(gòu)定義8.2

設(shè)有圖G=<V,E>與G’=<V’,E’>,如果它們的結(jié)點(diǎn)間存在一一對(duì)應(yīng)關(guān)系,而且這種對(duì)應(yīng)關(guān)系也反映在表示邊的結(jié)點(diǎn)對(duì)中(如果是有向邊,則對(duì)應(yīng)的結(jié)點(diǎn)對(duì)還保持相同的順序),則稱(chēng)此兩圖是同構(gòu)的.8.1.3圖的同構(gòu)(a)(b)同構(gòu)，(c)(d)同構(gòu)8.1.4圖中結(jié)點(diǎn)的次數(shù)定義8.3在有向圖中,以結(jié)點(diǎn)v為起點(diǎn)的邊的條數(shù)稱(chēng)為v的引出次數(shù),記以deg(v);以v為終點(diǎn)的邊的條數(shù)叫v的引入次數(shù),記以deg(v);v的引入次數(shù)與引出次數(shù)之和稱(chēng)為v的次數(shù)或全次數(shù),記為deg(v).在無(wú)向圖中,結(jié)點(diǎn)v的次數(shù)或全次數(shù)是與v相關(guān)聯(lián)的邊的條數(shù),也用deg(v)表示.任一圖的所有結(jié)點(diǎn)的次數(shù)之和必為偶數(shù),且必為圖中邊數(shù)的兩倍,因?yàn)槊織l邊必與兩個(gè)結(jié)點(diǎn)相關(guān)聯(lián).8.1.4圖中結(jié)點(diǎn)的次數(shù)題(8.1)設(shè)V={u,v,w,x,y},畫(huà)出圖G=<V,E>：

1)E={(u,v),(u,x),(v,w),(v,y)(x,y)} 2)E={(u,v),(v,w),(w,x),(w,y)(x,y)}

再求每個(gè)結(jié)點(diǎn)的次數(shù).解：

1) 2)

1)中結(jié)點(diǎn)：deg(u)=2,deg(v)=3,deg(w)=1,deg(x)=2,deg(y)=2. 2)中結(jié)點(diǎn)：deg(u)=1,deg(v)=2,deg(w)=3,deg(x)=2,deg(y)=2.uwvxyuwvxy8.1.4圖中結(jié)點(diǎn)的次數(shù)定理8.1圖G=<V,E>是一個(gè)(n,m)圖,其中V={v1,v2,…,vn},此時(shí)有d次正則圖：所有結(jié)點(diǎn)均有相同次數(shù)d的圖.8.1.4圖中結(jié)點(diǎn)的次數(shù)例：任何圖G中必有偶數(shù)個(gè)() A.引入次數(shù)為奇數(shù)的結(jié)點(diǎn)

B.引出次數(shù)為奇數(shù)的結(jié)點(diǎn)

C.次數(shù)為偶數(shù)的結(jié)點(diǎn)

D.次數(shù)為奇數(shù)的結(jié)點(diǎn)解： 引入次數(shù)與引出次數(shù)均指有向圖,這里是所有圖 因?yàn)閳D中結(jié)點(diǎn)次數(shù)的總和為偶數(shù),因此次數(shù)為奇數(shù)的結(jié)點(diǎn)數(shù)目為偶數(shù).所以選D.8.1.5多重圖與帶權(quán)圖多重圖：一個(gè)結(jié)點(diǎn)對(duì)可對(duì)應(yīng)若干條邊,這種邊稱(chēng)為多重邊方向相反的兩條邊可看成是由不同的結(jié)點(diǎn)對(duì)對(duì)應(yīng)的.簡(jiǎn)單圖：不包含多重邊的圖8.1.5多重圖與帶權(quán)圖例：三個(gè)點(diǎn)可構(gòu)成多少個(gè)不同構(gòu)的簡(jiǎn)單無(wú)向圖？解：

1)有點(diǎn)無(wú)邊

2)有一條邊

3)有兩條邊

4)有三條邊 所以一共有4個(gè).8.1.4圖中結(jié)點(diǎn)的次數(shù)有權(quán)圖：在一個(gè)圖中的旁側(cè)可以附加一些數(shù)字來(lái)刻畫(huà)此邊的某些數(shù)量特征(如兩地距離,車(chē)流量限制),稱(chēng)為邊的權(quán),此邊叫有權(quán)邊,具有有權(quán)邊的圖稱(chēng)為有權(quán)圖.無(wú)權(quán)圖：不具有有權(quán)邊的圖.8.2.1通路與回路設(shè)有向圖G=<V,E>,考慮G中邊的序列(vi1,vi2),(vi2,vi3),…,(vik-1,vik),可簡(jiǎn)寫(xiě)為(vi1,vi2,vi3,…,vik)此序列中可以允許多次出現(xiàn)相同的結(jié)點(diǎn)與邊,在此序列中除vi1和vik外,中間每個(gè)結(jié)點(diǎn)均與其前、后結(jié)點(diǎn)相連接,這種邊的序列稱(chēng)為圖的通路,而vi1和vik分別叫通路的起始結(jié)點(diǎn)與終止結(jié)點(diǎn),通路中邊的數(shù)目稱(chēng)為通路的長(zhǎng)度.有向圖中各邊全不同的通路稱(chēng)為簡(jiǎn)單通路,各點(diǎn)全不同的稱(chēng)為基本通路.一條基本通路一定是簡(jiǎn)單通路,但一條簡(jiǎn)單通路則不一定是基本通路.8.2.1通路與回路例：圖中開(kāi)始于結(jié)點(diǎn)1結(jié)束于結(jié)點(diǎn)3的通路有：

P1:(1,2,3) P2:(1,4,3) P3:(1,2,4,3) P4:(1,2,4,1,2,3) P5:(1,2,4,1,4,3) P6:(1,1,1,2,3)P1,P2,P3均是基本通路P5是簡(jiǎn)單回路但不是基本通路8.2.1通路與回路圖中的一條通路如果其起始結(jié)點(diǎn)與終止結(jié)點(diǎn)相同,則稱(chēng)此通路為回路.回路是一種特殊的通路.圖中各邊全不同的回路稱(chēng)為簡(jiǎn)單回路,各點(diǎn)全不同的稱(chēng)為基本回路.任一通路如果刪去所有回路，則必得基本回路;任一回路中刪去其中間的所有其余回路,必得基本回路. C1:(1,1) C2:(1,2,1) C2:(1,2,1) C4:(1,2,3,1)

均是基本回路. C5:(1,2,3,2,1)

是簡(jiǎn)單回路但不是基本回路.8.2.1通路與回路定理8.2

一個(gè)有向(n,m)圖中任何基本通路長(zhǎng)度均小于或等于n-1,而任何基本回路長(zhǎng)度均小于或等于n.資源分配圖：是一個(gè)有向圖，表示時(shí)刻t時(shí)系統(tǒng)中資源分配狀態(tài).當(dāng)進(jìn)程Pk占有資源Ri而又深情資源Rj時(shí)，則從結(jié)點(diǎn)Ri到Ri用一條有向邊相連.8.2.1通路與回路例8.3R={R1,R2,R3,R4}P={P1,P2,P3,P4}

其資源分配狀況是：

P1占有資源R4且申請(qǐng)資源R1; P2占有資源R1且申請(qǐng)資源R2及R3; P3占有資源R2且申請(qǐng)資源R3; P4占有資源R3且申請(qǐng)資源R1及R4.解： 其資源分配圖：8.2.1通路與回路例8.4用有向圖刻畫(huà)過(guò)程間的調(diào)用關(guān)系，來(lái)判斷某過(guò)程是否是遞歸的.

一個(gè)過(guò)程集合P={P1,P2,P3,P4,P5}

調(diào)用關(guān)系：

P1調(diào)用P2；

P2調(diào)用P4；

P3調(diào)用P1；

P4調(diào)用P5；

P5調(diào)用P2；某過(guò)程是遞歸的充分必要條件是包括此過(guò)程在內(nèi)的結(jié)點(diǎn)構(gòu)成一個(gè)回路.(P2,P4,P5,

P2)構(gòu)成一條回路,故過(guò)程P2,P4和P5是遞歸的8.2.1通路與回路定義8.4從一有向圖的結(jié)點(diǎn)vi到另一vj如果存在一條通路,則稱(chēng)從vi到vj是可達(dá)的.vi到vj是可達(dá)的不一定表示它們間只有一條通路,也可能有若干條通路,它們間最短的通路,這種通路稱(chēng)為短程線,而短程線的長(zhǎng)度則稱(chēng)從vi到vj間的距離,可用d(vi,vj)表示.8.2.1通路與回路在無(wú)向圖中一條邊lk對(duì)應(yīng)于無(wú)序結(jié)點(diǎn)對(duì)(vi,vj),而此無(wú)序結(jié)點(diǎn)對(duì)(vi,vj)可以看成兩個(gè)有序結(jié)點(diǎn)對(duì)(vi,vj)和(vj,vi).即可用方向相反的兩條有向邊取代一條無(wú)向邊,這樣,一個(gè)無(wú)向圖就轉(zhuǎn)換為有向圖了.8.2.2連通性定義8.5

一個(gè)無(wú)向圖G,如果它的任何兩結(jié)點(diǎn)間均是可達(dá)的,則稱(chēng)圖G為連通圖;否則,稱(chēng)為非連通圖.定義8.6

一個(gè)有向圖,如果忽略其邊的方向后得到的無(wú)向圖是連通的,則稱(chēng)此有向圖為連通圖;否則,稱(chēng)為非連通圖.8.2.2連通性定義8.7

一個(gè)有向連通圖G如果其任何兩結(jié)點(diǎn)間均是互相可達(dá)的,則稱(chēng)圖G是強(qiáng)連通的;

如果其任何兩結(jié)點(diǎn)間至少存在一向是可達(dá)的,則稱(chēng)圖G是單向連通的;

如果忽略邊的方向后其無(wú)向圖是連通的,則稱(chēng)圖G是弱連通的.8.2.2連通性無(wú)向圖中的連通性是一種等價(jià)關(guān)系其等價(jià)類(lèi)是V的一個(gè)劃分8.2.2連通性例：簡(jiǎn)單圖G有n個(gè)結(jié)點(diǎn),e條邊,設(shè)e>(n-1)(n-2)/2,證明G是連通的證明:(反證法)

假設(shè)G=<V,E>不連通,設(shè)G可分成兩個(gè)不相連通的連通分支(子圖)G1和G2,并設(shè)G1和G2分別有n1,n2個(gè)結(jié)點(diǎn),顯然n1+n2=n.因?yàn)閚i≥1,所以ni≤n-1(i=1,2).

與已知相矛盾,因此G是連通的.例：

(1)圖的次數(shù)序列為2,2,3,3,4,則邊數(shù)是多少？ 解:2m=2+2+3+3+4=14,m=7. (2)3,3,2,3;5,2,3,14能成為圖的次數(shù)序列嗎？為什么？ 解:不能.因?yàn)檫@兩個(gè)序列中有奇數(shù)個(gè)結(jié)點(diǎn)是次數(shù)奇數(shù). (3)圖G有12條邊,次數(shù)為3的結(jié)點(diǎn)有6個(gè),其余結(jié)點(diǎn)次數(shù)均小于3,問(wèn)圖中至少有幾個(gè)結(jié)點(diǎn)？ 解:次數(shù)為3的結(jié)點(diǎn)有6個(gè)占去18次數(shù)，還有6個(gè)次數(shù)由其余結(jié)點(diǎn)占有，其余結(jié)點(diǎn)的度數(shù)可為，當(dāng)均為2時(shí)所用結(jié)點(diǎn)數(shù)最少，所以應(yīng)由3個(gè)結(jié)點(diǎn)占有這6度，即圖中至少有9個(gè)結(jié)點(diǎn)。8.3歐拉圖定義8.8

圖G的一個(gè)回路,若它通過(guò)G中的每條邊一次,這樣的回路稱(chēng)為歐拉回路,具有這種回路的圖叫歐拉圖.定理8.3

無(wú)向連通圖G是歐拉圖的充分必要條件是G的每個(gè)結(jié)點(diǎn)均具有偶次數(shù),即無(wú)奇數(shù)次數(shù)的結(jié)點(diǎn).8.3歐拉圖定義8.9

通過(guò)圖G中每條邊一次的通路(非回路)稱(chēng)為歐拉通路.具有這種通路的圖叫歐拉半圖.定理8.4無(wú)向連通圖G中結(jié)點(diǎn)vi與vj間存在歐拉通路的充分必要條件是vi與vj的次數(shù)均為奇數(shù)而其他結(jié)點(diǎn)的次數(shù)為偶數(shù).8.3歐拉圖例8.5圖中deg(v1)=deg(v3)=3,deg(v2)=deg(v4)=2,故v1和v3間存在一條歐拉通路,從圖中可以知道這條通路是

C:(v1,v2,v3,v1,v4,v3)

但是這個(gè)圖中不存在歐拉回路.8.3歐拉圖例8.6郵遞員從郵局v1出發(fā)沿郵路投遞信件，其郵路圖如圖所示,試問(wèn)是否存在一條投遞路線使郵遞員從郵局出發(fā)通過(guò)所有路線而不重復(fù)且最后回到郵局.8.3歐拉圖解：此問(wèn)題就是驗(yàn)證該圖是否為歐拉圖.

經(jīng)檢驗(yàn)圖中每個(gè)結(jié)點(diǎn)均為偶次數(shù),由定理8.3可知這樣的一條投遞線路是存在的.

我們可以找出這樣一條線路：

C:(v1,v5,v11,v7,v12,v8,v10,v6,v9,v11,v12,v10,v9,v5,v2,v6,v4,v8,v3,v7,v1)

該線路不是唯一的.例8.7灑水車(chē)從A點(diǎn)出發(fā)執(zhí)行灑水任務(wù),城市街道圖形如圖所示,試問(wèn)是否存在一條灑水路線使灑水車(chē)從A點(diǎn)出發(fā)通過(guò)所有街道且不重復(fù)而最后回到車(chē)庫(kù)B.8.3歐拉圖例8.8判斷圖中4個(gè)圖形是否可以一筆連續(xù)畫(huà)成而使圖中沒(méi)有一部分被重復(fù).圖(a)(c)(d)是歐拉通路,圖(b)是歐拉回路.8.3歐拉圖例：構(gòu)造一個(gè)歐拉圖,其結(jié)點(diǎn)數(shù)v和邊數(shù)e分別滿(mǎn)足下述條件: 1)v,e的奇偶性一樣

2)v,e的奇偶性相反 如果不可能,說(shuō)明原因.

解：構(gòu)造歐拉圖與v,e的奇偶性沒(méi)什么必然關(guān)系.8.3歐拉圖例：設(shè)圖G是一個(gè)具有k個(gè)奇次結(jié)點(diǎn)的圖,問(wèn)最少加幾條邊到G中,而使所得的圖有一條歐拉回路？解： 添加一條邊能使兩個(gè)結(jié)點(diǎn)的次數(shù)改變奇偶性 歐拉回路要使圖中所有的結(jié)點(diǎn)次數(shù)均是偶數(shù) 所以對(duì)于k個(gè)奇次結(jié)點(diǎn),要將它們變?yōu)榕即谓Y(jié)點(diǎn),至少添加k/2條邊才能使它們都變成偶數(shù).8.3歐拉圖例:

下圖表示的是一個(gè)展覽館的平面圖。館里各相鄰房間之間都有門(mén)（共16扇）。一個(gè)參觀者來(lái)到展覽館門(mén)外，他想在參觀過(guò)程中，把館里所有的門(mén)都不重復(fù)地穿行一遍后出來(lái)，這個(gè)想法能否實(shí)現(xiàn)？解:首先建立該問(wèn)題的圖論模型。將展覽館的5個(gè)房間和館外場(chǎng)地用6個(gè)結(jié)點(diǎn)表示，兩個(gè)端點(diǎn)之間的邊表示它們所在位置之間有一扇門(mén)(a)ABCDEF(b)BACDEF圖中有4個(gè)奇點(diǎn)圖中有4個(gè)奇點(diǎn)A,B,D,F,

圖(b)不是歐拉圖,即參觀者的想法不能實(shí)現(xiàn)。

8.4漢密爾頓圖愛(ài)爾蘭數(shù)學(xué)家漢密爾頓（WilliamHamilton）爵士1859年提出了一個(gè)“周游世界”的游戲。這個(gè)游戲把一個(gè)正十二面體的二十個(gè)頂點(diǎn)看成地球上的二十個(gè)城市。棱線看成是連接城市的航路（航空、航海線或陸路交通線），要求游戲者沿棱線走，尋找一條經(jīng)過(guò)所有結(jié)點(diǎn)（即城市）一次且僅一次的回路.8.4漢密爾頓圖定義8.10

若圖G的一個(gè)回路通過(guò)G中的每個(gè)點(diǎn)一次,這樣的回路稱(chēng)為漢密爾頓圖.定義8.11

通過(guò)圖G中每結(jié)點(diǎn)一次的通路(非回路)稱(chēng)為漢密爾頓通路.定理8.5(必要條件)

設(shè)無(wú)向圖G=<V,E>是漢密爾頓圖,??V1?V,則P(G-V1)≤|V1|,其中P(G-V1)是從G中刪去V1(包括V1中相應(yīng)結(jié)點(diǎn)及其關(guān)聯(lián)的邊)后所得到的圖的連通分支數(shù).8.4漢密爾頓圖漢密爾頓圖的必要條件可用來(lái)判定某些圖不是漢密爾頓圖。例:解：圖中共有9個(gè)結(jié)點(diǎn),如果取結(jié)點(diǎn)集V1={3個(gè)白點(diǎn)}，即|V1|=3.

而這時(shí)P(G-V1)=4.這說(shuō)明該圖不是漢密爾頓圖。 但要注意若一個(gè)圖滿(mǎn)足該必要條件也不能保證這個(gè)圖一定是漢密爾頓圖,如圖c。o。o。o。(a)(b)(c)8.4漢密爾頓圖定理8.6(充分條件)

設(shè)G=<V,E>為無(wú)向簡(jiǎn)單圖,|V|≥3,如果G中每對(duì)結(jié)點(diǎn)次數(shù)之和≥|V|,則G必為漢密爾頓圖.滿(mǎn)足這個(gè)條件的圖一定是漢密爾頓圖。但不是所有的漢密爾頓圖都滿(mǎn)足這些條件.定理

(充分條件)

設(shè)G=<V,E>為無(wú)向簡(jiǎn)單圖,|V|≥3,如果G中每對(duì)結(jié)點(diǎn)次數(shù)之和大于等于|V|-1,則G存在一條漢密爾頓通路.8.4漢密爾頓圖例：考慮在七天內(nèi)安排七門(mén)課程的考試,使得同一位教師所任的兩門(mén)課程考試不排在連接的兩天中,試證明如果沒(méi)有教師擔(dān)任多于四門(mén)課程,則符合上述要求的考試安排總是可能的.解： 設(shè)G為具有七個(gè)結(jié)點(diǎn)的圖,每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一門(mén)課程考試,如果這兩個(gè)結(jié)點(diǎn)對(duì)應(yīng)的課程考試是由不同的老師擔(dān)任的,那么這兩個(gè)結(jié)點(diǎn)之間有一條邊.

因?yàn)槊總€(gè)教師所任課程數(shù)不超過(guò)四,故每個(gè)節(jié)點(diǎn)的次數(shù)至少是3,任兩個(gè)結(jié)點(diǎn)的次數(shù)之和至少是6,故G總是包含一條漢密爾頓通路,它對(duì)應(yīng)于一個(gè)七門(mén)考試課目的一個(gè)適當(dāng)?shù)陌才?8.4漢密爾頓圖例：某次會(huì)議有20人參加,其中每人都至少有10個(gè)朋友,這20人圍一圓桌入席,要想使每個(gè)人相鄰的兩位都是朋友是否可能？根據(jù)是什么？解： 可用結(jié)點(diǎn)代表人,根據(jù)題意,兩人是朋友對(duì),相應(yīng)結(jié)點(diǎn)間連一條邊,則得到一個(gè)無(wú)向圖G=<V,E>,可轉(zhuǎn)化為求漢密爾頓回路問(wèn)題.

由于每人至少10個(gè)朋友,故對(duì)任意結(jié)點(diǎn)u,v∈V,有deg(u)≥10,deg(v)≥10

所以deg(u)+deg(v)≥20.根據(jù)漢密爾頓回路的充分條件定理,可知G為漢密爾頓圖,G中存在漢密爾頓回路,按此回路各點(diǎn)位置入席即為所求.8.4漢密爾頓圖推銷(xiāo)員問(wèn)題：設(shè)有某推銷(xiāo)員為推銷(xiāo)商品需要跑遍各大城市且不重復(fù),而最后返回原地,需要找到一條總距離為最短的路線.可以用結(jié)點(diǎn)表示城市,城市間的交通路線用邊表示,而城市間的交通線路距離可用附加于邊的權(quán)表示.而該問(wèn)題的目的即找一條權(quán)的總和為最短的漢密爾頓回路.8.5圖的矩陣表示法圖的矩陣表示法的優(yōu)點(diǎn)表示簡(jiǎn)單,可以表示較為復(fù)雜的圖將圖的問(wèn)題變成計(jì)算問(wèn)題，方便借助計(jì)算機(jī)進(jìn)行計(jì)算.8.5.1有向圖的鄰接矩陣設(shè)有一有向圖G=<V,E>,其中

V={v1,v2,…,vn} E={e1,e2,…,em}

假設(shè)各結(jié)點(diǎn)按一定順序排列 這時(shí)構(gòu)成一矩陣: A=(aij)n×n

其中:

此矩陣稱(chēng)為圖G的鄰接矩陣.8.5.1有向圖的鄰接矩陣?yán)河袌D如下，請(qǐng)寫(xiě)出它的鄰接矩陣解：v1v2v3v48.5.1有向圖的鄰接矩陣設(shè)有圖G=<V,E>,其鄰接矩陣為可由鄰接矩陣很容易地辨認(rèn)其對(duì)應(yīng)的圖的一些特性來(lái).環(huán)：矩陣對(duì)角線元素有1零圖：矩陣元素全為0完全圖：除對(duì)角線元素為0外,其余全為18.5.1有向圖的鄰接矩陣圖G中結(jié)點(diǎn)vi的引出次數(shù)結(jié)點(diǎn)vi的引入次數(shù)其全次數(shù)C=Al,此時(shí)cij表示從vi到vj長(zhǎng)度為l的通路數(shù)目,如cij=0,則表示長(zhǎng)度為l的通路沒(méi)有,而cii給出了從vi出發(fā)的長(zhǎng)度為l的回路數(shù)目.8.5.2可達(dá)性矩陣Rn=(rij)n×n Rn=A+A2+A3+…+An

若rij=0,表示從vi到vj是不可達(dá)的 若rij≠0,表示從vi到vj是可達(dá)的可達(dá)性矩陣(通路矩陣) P

=(pij)n×n rij=0時(shí),令pij=0 rij≠0時(shí),令pij=1一個(gè)圖G的可達(dá)性矩陣給出了圖中各結(jié)點(diǎn)間是否可達(dá)以及圖中是否有回路.8.5.2可達(dá)性矩陣可達(dá)性矩陣的簡(jiǎn)單算法P=A(+)A(2)(+)A(3)(+)…(+)A(n)

A(i)表示在布爾矩陣運(yùn)算意義下A的i次冪

(+)表示在布爾矩陣運(yùn)算意義下加法運(yùn)算8.5.3無(wú)向圖的矩陣表示法將無(wú)