《離散數(shù)學(xué)》課件-第7章

7.1圖的基本概念

7.2圖的連通性

7.3圖的矩陣表示

7.4歐拉圖與漢密爾頓圖

7.5平面圖

7.6圖的著色

7.7樹

*7.8運輸網(wǎng)絡(luò)第7章圖論7.1.1圖的定義

圖是由一個結(jié)點(或頂點)集合和這個結(jié)點集合中某些結(jié)點對之間的連線所組成的離散結(jié)構(gòu)，其嚴格定義如下：

定義7.1.1

一個圖G可以表示為一個三元組G=〈V(G),E(G),φG〉，其中V(G)是一個非空的結(jié)點(vertice)(或頂點)集合，E(G)是邊(edge)集合，φG是從邊集合到結(jié)點偶對集合上的一個關(guān)系，使得每條邊和兩個結(jié)點相關(guān)聯(lián)。7.1圖的基本概念設(shè)G=〈V(G)，E(G),φG〉是一個圖，e∈E(G)，u,v∈V(G)，若φG(e)=［u,v］，則稱結(jié)點u、v與邊e相關(guān)聯(lián)。若e與u和v的順序無關(guān)，則稱e是圖G的無向邊(undirectededge)，結(jié)點u和v是e的兩個端點(endpoint)；若e與u和v的順序有關(guān)，則稱e是圖G的有向邊(directededge)，其中結(jié)點u稱為e的始點，結(jié)點v稱為e的終點。為了便于區(qū)別，無向邊φG(e)=［u,v］記為φG(e)={u,v}或者e={u,v}，有向邊φG(e)=［u,v］記為φG(e)=〈u,v〉或者e=〈u,v〉。無向邊和有向邊都可以稱為邊。在一個圖G中，每條邊必然與兩個結(jié)點相關(guān)聯(lián)，因此，G=〈V(G),E(G),φG〉通常也簡記為G=〈V,E〉。

為了直觀地觀察一個圖的構(gòu)成，我們通常用小圓圈表示圖的結(jié)點，用兩個結(jié)點間的一條無箭頭連線表示兩個結(jié)點關(guān)聯(lián)的一條無向邊，而用從始點到終點的一條帶箭頭的連線表示兩個結(jié)點關(guān)聯(lián)的一條有向邊，這樣就得到了一個圖的圖形化表示。由于表示結(jié)點的小圓圈和表示邊的線的相對位置一般認為是無關(guān)緊要的，所以一個圖的圖示并不具有唯一性。

例1

圖G1和G2分別如圖7.1.1(a)、(b)所示，分別給出G1和G2的形式定義。

圖7.1.1圖7.1.2給出了多重圖、線圖和簡單圖的示例。

圖7.1.2

定義7.1.2

賦權(quán)圖G是一個四重組〈V,E,f,h〉，其中f是定義在結(jié)點集V到實數(shù)集R上的函數(shù)，h是定義在邊集E到實數(shù)集R上的函數(shù)。

圖7.1.3(a)是一個結(jié)點賦權(quán)圖，而圖7.1.3(b)是一個邊賦權(quán)圖。圖7.1.37.1.2結(jié)點的度數(shù)

定義7.1.3

在圖G=〈V,E〉中，v∈V，與結(jié)點v

關(guān)聯(lián)的邊數(shù)稱為結(jié)點v的度數(shù)(degree)，記為deg(v)，簡記為d(v)。若G是有向圖，則以結(jié)點v為終點的邊數(shù)稱為該結(jié)點的入度，記為deg－(v)，以結(jié)點v為始點的邊數(shù)稱為該結(jié)點的出度，記為deg+(v)。不難得出，deg(v)=deg－(v)+deg+(v)。

定理7.1.1(握手定理)在任何圖G=〈V,E〉中，所有結(jié)點的度數(shù)之和等于邊數(shù)的兩倍，即

證明結(jié)點的度數(shù)是由其關(guān)聯(lián)的邊所確定的。任取一條邊e∈E，e必關(guān)聯(lián)兩個結(jié)點，不妨設(shè)e=［u,v］。邊e給予其關(guān)聯(lián)的結(jié)點u和v各一個度。因此在每個圖中，結(jié)點的度數(shù)總和等于邊數(shù)的兩倍。

證畢推論任何圖中，奇數(shù)度的結(jié)點必為偶數(shù)個。

定理7.1.2

在任何有向圖G=〈V,E〉中，所有結(jié)點的入度之和等于所有結(jié)點的出度之和，即

證明根據(jù)定理7.1.1，有向圖G=〈V,E〉滿足

。因為任取一條邊e=〈u,v〉∈E，e給其始點u帶來一個出度，而給其終點v帶來一個入度，所以圖G中所有結(jié)點的入度和等于出度和

，并且等于圖中的邊數(shù)|E|。

證畢7.1.3特殊圖

圖7.1.4所示的是一個以它的構(gòu)造者彼得森命名的3－正則圖，由于它具有許多奇特的性質(zhì)，因此又被稱做單星妖怪(snarkgraph)。

定義7.1.4

無向簡單圖G=〈V,E〉中，如果任何兩個不同結(jié)點間都恰有一條邊相連，則稱該圖為無向完全圖。n個結(jié)點的無向完全圖(completeundirectedgraph)記為Kn。

無向完全圖K4和K5分別如圖7.1.5(a)、(b)所示。

圖7.1.4圖7.1.5

定義7.1.5

若有向圖G=〈V,E〉滿足E=V×V，則稱G為有向完全圖(completedirectedgraph)，記為Dn。圖7.1.6所示是四個結(jié)點的有向完全圖D4。

不難得到，具有n個結(jié)點的無向完全圖Kn共有n(n－1)/2條邊，具有n個結(jié)點的有向完全圖Dn共有n2條邊。圖7.1.6

定義7.1.6

設(shè)G=〈V,E〉是無向圖，且G是非零圖，若結(jié)點集合V可以劃分成兩個不相交的子集X和Y，使得G中的每一條邊的一個端點在X中而另一個端點在Y中，則稱G為二部圖(bipartitegraph)，記為G=〈X,E,Y〉。

二部圖必?zé)o自回路，但可以有平行邊。

通過對結(jié)點進行A-B標(biāo)號，可以簡單地判定一個圖是否是二部圖。首先給任意一個結(jié)點標(biāo)上A，與標(biāo)記為A的結(jié)點鄰接的結(jié)點標(biāo)上B，再將標(biāo)記為B的結(jié)點鄰接的結(jié)點標(biāo)上A,如此重復(fù)下去，如果這個過程可以完成，使得沒有相鄰的結(jié)點標(biāo)上相同的字母，則該圖是二部圖,否則，它就不是二部圖。

例4

判斷圖7.1.7(a)所示的圖是否是二部圖。

解對圖中的結(jié)點進行A-B標(biāo)號，如圖7.1.7(b)所示，標(biāo)號過程成功結(jié)束，該圖是一個二部圖?？梢詫⑵洚嫵扇鐖D7.1.7(c)所示的結(jié)構(gòu)，這樣可以直觀地看出它是一個二部圖。

設(shè)G=〈X,E,Y〉是一個二部圖，若G是一個簡單圖，并且X中的每個結(jié)點與Y中的每個結(jié)點均鄰接，則稱G為完全二部圖。如果|X|=m,|Y|=n，則在同構(gòu)的意義下，這樣的完全二部圖只有一個，記為Km,n。圖7.1.7完全二部圖K2,4和K3,3分別如圖7.1.8(a)、(b)所示。

對于一個完全二部圖G=〈X,E,Y〉，X中的每一個結(jié)點與Y中的每個結(jié)點間恰有一條邊，因此G中共有|X|·|Y|條邊。圖7.1.87.1.4子圖與補圖

定義7.1.7

設(shè)圖G=〈V,E〉，G′=〈V′,E′〉，若有E′E且V′V，則稱G′為G的子圖(subgraph)。

設(shè)G′是G的子圖，且有V′=V，則稱G′是G的生成子圖(spanningsubgraph)。

設(shè)G′是G的子圖，V′僅由E′中邊相關(guān)聯(lián)的結(jié)點組成，則稱G′為由邊集E′導(dǎo)出的子圖。

設(shè)G′是G的子圖，若對于V′中的任意結(jié)點偶對［u,v］，［u,v］∈E當(dāng)且僅當(dāng)［u,v］∈E′，則稱G′為由結(jié)點集V′導(dǎo)出的子圖。

?

?

定義7.1.8

給定一個圖G，由G中所有的結(jié)點及所有能使G成為完全圖的添加邊組成的圖，稱為G相對于完全圖的補圖，簡稱為G的補圖，記為。

例5

分別給出圖7.1.9(a)和(b)的補圖。

圖7.1.9

解其補圖分別如圖7.1.10(a)、(b)所示。

圖7.1.107.1.5圖的同構(gòu)

定義7.1.9

設(shè)G=〈V,E〉和G′=〈V′,E′〉，如果存在雙射函數(shù)f:V→V′和g:E→E′，對于任何e∈E,e=［vi,vj］當(dāng)且僅當(dāng)g(e)=［f(vi),f(vj)］，則稱G與G′同構(gòu)(isomorphism)，記為G≌G′。

相互同構(gòu)的圖只是畫法不同或結(jié)點與邊的命名不同而已。例如，圖7.1.11就給出了圖7.1.4所示的“單星妖怪”的另一種圖示方式。圖7.1.11由圖同構(gòu)的定義可以看出，兩圖同構(gòu)具備以下必要條件：

(1)結(jié)點數(shù)相等。

(2)邊數(shù)相等。

(3)度數(shù)相同的結(jié)點數(shù)目相等。

例6

證明如圖7.1.12(a)和(b)所示的兩個圖是同構(gòu)的。

圖7.1.12

例7

證明如圖7.1.13(a)和(b)所示的兩個圖不同構(gòu)。

圖7.1.137.2.1路和回路

定義7.2.1

給定圖G=〈V,E〉，設(shè)v0,v1,…,v

n∈V，

e1,e2,…,en∈E，ei是關(guān)聯(lián)于結(jié)點vi－1和vi的邊,則稱點邊交替序列v0e1v1e2…vn－1envn為聯(lián)結(jié)結(jié)點v0到vn的路(walk)，其中，v0稱為路的始點，vn稱為路的終點，

v1,…,vn－1稱為路的內(nèi)點，

v0和vn稱為路的端點。7.2圖的連通性在線圖中，因為不存在多重邊，所以路可僅用結(jié)點序列表示。在有向圖中，結(jié)點數(shù)大于1的路亦可用邊序列表示。

若一條路中經(jīng)過的所有結(jié)點v0,v1,…,vn均不相同，則稱該路為通路(path)。若一條路中經(jīng)過的所有邊e1,e2,…,en均不相同，則稱該路為跡(trail)。始點與終點不同的跡稱為開跡(opentrail)。

定義7.2.2

始點與終點相同的路稱為回路(circuit)。

經(jīng)過的每條邊均不相同的回路稱為閉跡(closedtrail)。除始點與終點外其余結(jié)點均不相同的閉跡稱為圈(cycle)。一個長度為k的圈稱為k圈，根據(jù)k是奇數(shù)或偶數(shù)又可分為奇圈或偶圈，而一條自回路是長度為1的奇圈。注意，在簡單無向圖中，回路vivjvi不是圈。

例1

在圖7.2.1中分別找出一條路、通路、開跡、閉跡和圈。

圖7.2.1

定義7.2.3

一條路中所含的邊數(shù)稱為該路的長度。

定理7.2.1

在一個具有n個結(jié)點的圖中，如果從結(jié)點vi到vj存在一條路，則從結(jié)點vi到結(jié)點vj必存在一條長度小于n的路。

證明先考慮有向圖的情況。設(shè)結(jié)點vi到結(jié)點vj存在一條路P，且P中含有l(wèi)(l≥0)條邊，則該路上必通過l+1個結(jié)點。

(1)若l＜n，則P就是滿足要求的一條路。

(2)若l≥n，則路P通過的結(jié)點數(shù)大于等于n+1。根據(jù)鴿巢原理，必存在結(jié)點vs，它在P中不止一次出現(xiàn)，即該路必有結(jié)點序列vi…vs…vs…vj，如圖7.2.2所示。從路P中去掉從vs到vs之間出現(xiàn)的這些邊，得到從vi到vj的路P′，P′比P的長度短。圖7.2.2

推論1

在一個具有n個結(jié)點的圖中，如果從結(jié)點vi到vj存在一條路，則從結(jié)點vi到結(jié)點vj必存在一條長度小于n的通路。

推論2

在一個具有n個結(jié)點的圖中，如果存在閉跡，則必存在一條長度小于等于n的圈。

定理7.2.2

設(shè)G是一個無向圖，若G中每個結(jié)點的度數(shù)大于等于2，則G中必含有圈。

證明在圖G中找一條最長通路P=v0,v1,…,vp－1,vp。由于P是最長通路，因此結(jié)點vp關(guān)聯(lián)的結(jié)點均在{v0,v1,…,vp}中；否則，可以延長通路P得到長度更長的一條通路。又由于vp的度數(shù)大于2，因此必然存在除通路P中邊{vp－1,

vp}外的另外一條邊e，使得e={vp,vi}，vi∈{v0,v1,…,vp}。所以，vi,vi+1，…,vp－1,vp,vi構(gòu)成一個圈。

證畢

定義7.2.4

給定圖G=〈V,E〉，結(jié)點vi,vj∈V，從vi到vj的最短通路長度稱為結(jié)點vi到vj的距離，記為d(vi,vj)。若不存在從vi到vj的路，則令d(vi,vj)=∞。

結(jié)點間的距離滿足以下性質(zhì)：

(1)d(vi,vj)≥0。

(2)d(vi,vi)=0。

(3)d(vi,vk)+d(vk,vj)≥d(vi,vj)(三角不等式)。

定理7.2.3

設(shè)G=〈V,E〉是無向圖，且|E|＞0，G是二部圖當(dāng)且僅當(dāng)G中不含奇圈。

證明必要性。設(shè)G是二部圖，且G=〈X,E,Y〉。設(shè)C=(v0,v1,v2,…,vk,v0)是G中的任一圈，則v0,v1,v2,…,vk是互不相同的結(jié)點。

C中共有k+1條邊(k≥1)，若C是奇圈，則k為偶數(shù)。不妨設(shè)v0∈X，則有結(jié)點v2,v4,…∈X，v1,v3,…∈Y，顯然v0,vk∈X且(vk,v0)∈E,這與G是二部圖矛盾。充分性。設(shè)G=〈V,E〉是連通圖，否則對G的每個連通分支進行證明。設(shè)G=〈V,E〉不含奇圈，任取v0∈V，定義結(jié)點集X,Y如下：

X={v|d(v0,v)為偶數(shù)},Y={v|d(v0,v)為奇數(shù)}

顯然，V=X∪Y，X∩Y=。下面證明G=〈X,E,Y〉。

假設(shè)存在結(jié)點vi,vj∈Y，vi≠vj，且(vi,vj)∈E。由于G是連通的，并且v0到vi和v0到vj的距離均為奇數(shù)，所以從v0到vi有一條最短通路P，其長度為奇數(shù)，從v0到vj也有一條最短通路Q，其長度為奇數(shù)。

若P和Q除v0外沒有公共結(jié)點，則P、Q、(vi,vj)構(gòu)成一條長度為奇數(shù)的圈，如圖7.2.3所示。這與G中不含奇圈矛盾。

?

圖7.2.3若P和Q除v0外含有公共結(jié)點，設(shè)w為P和Q最后的一個公共結(jié)點，令：

P1表示P中從v0到w的一段，P2表示P中從w到vi的一段,

Q1表示Q中從v0到w的一段，Q2表示Q中從w到vj的一段。

因為P和Q是最短路，所以P1和Q1都是從v0到w的最短路，故長度一定相等。又因為P和Q的長度均為奇數(shù)，推出P2和Q2的奇偶性相同，則P2、Q2、(vi,vj)構(gòu)成一條長度為奇數(shù)的圈，與G中不含奇圈矛盾。從而得到，Y中任意兩個結(jié)點間不存在邊。

同理可證，X中任意兩個結(jié)點間不存在邊。

根據(jù)二部圖的定義有G是二部圖。

證畢7.2.2無向圖的連通性

定義7.2.5

在一個無向圖G=〈V,E〉中，若結(jié)點u和結(jié)點v之間存在一條路，則稱u和v可達，或者稱結(jié)點u和結(jié)點v是連通的(connected)。

不難驗證，一個無向圖G=〈V,E〉中結(jié)點集V上的連通關(guān)系是一個等價關(guān)系，這個等價關(guān)系誘導(dǎo)了V的一個劃分π＝{V1,V2,…,Vm}，使得兩個結(jié)點vi和vj是連通的當(dāng)且僅當(dāng)它們屬于同一個Vk∈π,并且稱由結(jié)點集V1,V2,…,Vm導(dǎo)出的子圖G(V1),G(V2),…,G(Vm)為圖G的連通分支。G的連通分支個數(shù)記為ω(G)。

定義7.2.6

若一個無向圖G=〈V,E〉的任意兩個結(jié)點都是連通的，則稱之為一個連通無向圖。

圖7.2.4(a)所示是一個連通無向圖，它恰有一個連通分支。圖7.2.4(b)所示是一個非連通的無向圖，它有三個連通的分支。圖7.2.4

定義7.2.7

設(shè)無向圖G=〈V,E〉為連通圖，V1

V，若在圖G中刪除了V1的所有結(jié)點后，所得子圖變?yōu)榉沁B通的，而刪除了V1的任何真子集后，所得子圖仍是連通的，則稱V1為G的一個點割集(cutvertices)。若某一個結(jié)點構(gòu)成一個點割集，則稱該結(jié)點為割點(cutvertex)。

若G不是完全圖，則定義κ(G)=min{|V1||V1是G的點割集}為圖G的點連通度。顯然，κ(G)是為產(chǎn)生G的一個不連通子圖需要刪去的結(jié)點的最少數(shù)目。另外規(guī)定:①κ(Kn)=n－1;②若G是不連通無向圖，則κ(G)=0。?

如果圖G的點連通度至少為k，則稱圖G為k連通的。

討論連通度最經(jīng)典的例子是Harary圖Hk,n，其中k為各結(jié)點的度，n為結(jié)點個數(shù)。H3,6和H3,12如圖7.2.5所示。對于Hk,n，若n為偶數(shù)且k=3，可以給出一種構(gòu)造方法,即將n個結(jié)點等間距地排成一個圓圈，分別給結(jié)點編號0，…，n－1，先將每個結(jié)點與左右相鄰2個結(jié)點聯(lián)結(jié)，再將結(jié)點i與結(jié)點j=i+n/2聯(lián)結(jié)，i＜n/2。圖7.2.5

定理7.2.4

連通無向圖G中的一個結(jié)點是割點，當(dāng)且僅當(dāng)存在兩個結(jié)點間的每條路都要通過該結(jié)點。

證明必要性。若結(jié)點w是連通圖G=〈V,E〉的一個割點，設(shè)刪除w得到子圖G-w，則G-w中至少包含兩個連通的分支，不妨設(shè)為G1=〈V1,E1〉和G2=〈V2,E2〉。任取u∈V1,v∈V2，因為G是連通的，任取G中一條連接u和v的路P，假設(shè)P不通過w，這與u和v在G-w中不連通矛盾，所以P必通過w。故u和v之間的任意一條路都要經(jīng)過w。

充分性。若連接圖G中兩個結(jié)點u和v的每一條路都經(jīng)過w，則刪去w得到的子圖G-w中u和v必不連通，故w是圖G的一個割點。

證畢

定義7.2.8

設(shè)無向圖G=〈V,E〉為連通圖，E1

E，若從G中刪除E1中的所有邊后所得子圖是不連通的，而刪除了E1的任一真子集后所得的子圖仍是連通的，則稱E1為G的一個邊割集(cutedges)。若某條邊構(gòu)成邊割集，則稱該邊為割邊(cutedge)或橋(bridge)。

若G是非平凡圖，則稱κ′(G)=min{|E1||E1是G的邊割集}為圖G的邊連通度。顯然，κ′(G)是為產(chǎn)生G的一個不連通子圖需要刪去的邊的最少數(shù)目。另外規(guī)定:①若G是平凡圖，則κ′(G)=0;②若G是不連通無向圖，則κ′(G)=0。

如果圖G的邊連通度至少為k，則稱圖G為k邊連通的。?

定理7.2.5

無向圖G中的一條邊是割邊，當(dāng)且僅當(dāng)它不包含在G的任一圈中。

證明必要性。設(shè)e是G中的一條割邊，假設(shè)e包含在某一圈中，則刪除e后將不影響圖G的連通性，這顯然與e是割邊矛盾。所以e不包含在G的任一圈中。

充分性。設(shè)圖G是連通圖，邊e={u,v}，e不包含在G的任一圈中。令G′=G－e，則在G′中，u和v不連通，否則，u和v之間在G′中存在通路，那么該通路加上邊e將構(gòu)成G的一個圈，與題設(shè)矛盾。因此，從圖G中刪除邊e后，結(jié)點u與v將不連通，得到G′=G－e不連通，故e是G的一條割邊。

證畢7.2.3有向圖的連通性

定義7.2.9

設(shè)G=〈V,E〉是有向圖，u,v∈V，如果存在一條以u為始點且以v為終點的路，則稱從u到v可達。

定義7.2.10

在有向圖G＝〈V,E〉中，若對于任意結(jié)點偶對都是相互可達的，則稱圖G是強連通的。若對于任意結(jié)點偶對，至少有一個結(jié)點到另一個結(jié)點是可達的，則稱圖G是單側(cè)連通的。如果圖G的底圖是連通的，則稱G是弱連通的，也稱G是連通的。

圖7.2.6(a)、(b)、(c)分別是強連通、單側(cè)連通和弱連通有向圖的例子。圖7.2.6

定理7.2.6

一個有向圖是強連通的，當(dāng)且僅當(dāng)圖中存在一條回路，它至少包含圖中每個結(jié)點一次。

證明設(shè)G是一個有向圖。

充分性。如果圖G中存在一條至少包含每個結(jié)點至少一次的回路，則G中任意兩個結(jié)點通過這條回路是相互可達的，故G是強連通的。

必要性。如果有向圖是強連通的，則任意兩個結(jié)點都是相互可達的。假設(shè)圖G中不存在包含每個結(jié)點至少一次的回路。

在圖G中找到一條包含不同結(jié)點最多的回路C，假設(shè)C不包含結(jié)點v。因為G是強連通的，所以有v與C中任一結(jié)點u必然相互可達，即u和v之間可以構(gòu)成一條有向回路C′，那么可由C和C′構(gòu)造出一條除C中結(jié)點外至少還包含結(jié)點v的回路，這與C是包含結(jié)點最多的回路矛盾。

故圖G中存在包含每個結(jié)點至少一次的回路。

證畢

定義7.2.11

在有向圖G=〈V,E〉中，G′是G的子圖，若G′是強連通(單側(cè)連通、弱連通)的，且不存在G的子圖G″G′并且G″也是強連通(單側(cè)連通、弱連通)的，則稱G′為G的強(單側(cè)、弱)分圖。

?

不難驗證，一個有向圖G=〈V,E〉中結(jié)點集V上的“結(jié)點偶對相互可達”關(guān)系是一個等價關(guān)系，這個等價關(guān)系誘導(dǎo)了V的一個劃分π＝{V1,V2,…,Vm}，使得兩個結(jié)點vi和vj是相互可達的當(dāng)且僅當(dāng)它們屬于同一個Vk∈π。由結(jié)點集V1,V2,…,Vm導(dǎo)出的子圖G(V1),G(V2),…,G(Vm)即為圖G的強連通分圖。一個有向圖G=〈V,E〉中的結(jié)點集V上的“結(jié)點偶對間至少有一個結(jié)點到另一個結(jié)點是可達的”關(guān)系僅滿足自反性和對稱性，此關(guān)系誘導(dǎo)了V的一個覆蓋π＝{V1,V2,…,Vm}。由結(jié)點集V1,V2,…,Vm導(dǎo)出的子圖G(V1),G(V2),…,G(Vm)即為圖G的單側(cè)連通分圖。求有向圖G=〈V,E〉中的弱連通分圖等價于求G的底圖中的連通分支。

例4

有向圖G=〈V,E〉如圖7.2.7所示，求G的強分圖、單側(cè)分圖和弱分圖。

圖7.2.7

解

(a)G的強分圖有5個，如圖7.2.8(a)所示。

(b)G的單側(cè)分圖有3個，如圖7.2.8(b)所示。

(c)G的弱分圖就是G。

圖7.2.87.2.4最短路問題

設(shè)G=〈V,E,ω〉是一個邊賦權(quán)簡單圖，ω是從邊集E到正實數(shù)集合上的函數(shù)，邊［u,v］上的權(quán)值記為ω(u,v)。若結(jié)點u到v沒有邊，則指定ω(u,v)=∞。

邊賦權(quán)圖可以用來對很多現(xiàn)實問題進行建模。例如，在鐵路交通網(wǎng)絡(luò)圖中，邊上的權(quán)值可以用來表示兩個城市間鐵路線的長度；在通信線路圖中，邊上的權(quán)值可以表示通信線路的建造費用、使用時間等。

定義7.2.12

設(shè)G=〈V,E,ω〉是一個邊賦權(quán)簡單圖，P是G中的一條路，P中所有邊的權(quán)值之和稱為路P的長度，記為ω(P)。圖G中從結(jié)點u到結(jié)點v的長度最小的路稱為u到v的最短路，u到v的最短路的長度稱為u到v的距離，記為d(u,v)。當(dāng)圖G中邊上的權(quán)均為1時，此距離與7.2.1節(jié)的距離就完全相同。特別地，當(dāng)u到v不可達時，令d(u,v)=∞。d(u,v)的表達式如下：

當(dāng)T=V時算法結(jié)束。算法的具體過程如下：

(1)令T={s}，并對于V-T中的每個結(jié)點v，令l(s,v)=ω(s,v)，p(s,v)=｛s,v｝。

(2)選取滿足的結(jié)點x，并令T=T∪{x}。

(3)若T=V，算法結(jié)束。

(4)對于V-T中的每個結(jié)點v，令

并轉(zhuǎn)至步驟(2)。

定理7.2.7

給定一個邊賦權(quán)簡單圖G=〈V,E,ω〉和源點s∈V，利用對于任意結(jié)點v∈V，利用狄杰斯特拉算法得到s到v的距離d(s,v)。

證明略。

例5

設(shè)邊賦權(quán)圖G=〈V,E,ω〉如圖7.2.9所示，求結(jié)點a到其他結(jié)點的最短路和距離。

圖7.2.9在算法的執(zhí)行過程中可以同時保存已找到的最短路，此過程概括在表7.2.1中。表7.2.17.3.1鄰接矩陣

定義7.3.1

設(shè)G=〈V,E〉是一個線圖，結(jié)點集V={v1,v2,…,vn}，令A(yù)(G)=［aij］n×n,其中：

則稱A(G)為G的鄰接矩陣(adjacencymatrix)。7.3圖的矩陣表示

1.AAT的元素的意義

若有，如圖7.3.2所示，則在G中恰好有bij個結(jié)點，從vi和vj均有邊引出到這些結(jié)點。特別地，當(dāng)i=j時bij表示vi的出度。

圖7.3.2

2.ATA的元素的意義

若有，如圖7.3.3所示，則在G中恰好有bij個結(jié)點，以這些結(jié)點為始點既有邊引入到vi,又有邊引入到vj。特別地，當(dāng)i=j時bij表示vi的入度。

圖7.3.3

3.A(2)=A×A的元素的意義

若有，如圖7.3.4所示，則從vi到vj長度為2的路有bij條。特別地，當(dāng)i=j時vi到自身長度為2的回路有bij條。

圖7.3.4

定理7.3.1

設(shè)G=〈V,E〉為有向線圖，結(jié)點集V={v1,v2,

…,vn}。A=［aij］n×n為G的鄰接矩陣，A(m)=［a(m)ij］n×n，則G中從vi到vj有a(m)ij條長度為m的路。

證明對m進行歸納。

當(dāng)m=1，m=2時，由定義和上面的分析可知，顯然成立。

設(shè)當(dāng)m=t時，t≥2，命題成立。當(dāng)m=t+1時，由

故。根據(jù)鄰接矩陣的定義可知,aik表示結(jié)點vi與vk的長度為1的路的條數(shù)。根據(jù)歸納假設(shè)知，a(t)kj是連接vk與vj的長度為t的路的條數(shù)。因此，aik·a(t)kj表示從結(jié)點vi出發(fā)經(jīng)過vk到達結(jié)點vj的長度為t+1的路的條數(shù)。

對所有的k∈{1,2,…,n}求和得，aij(t+1)就是從結(jié)點vi到結(jié)點vj的所有長度為t+1的路的條數(shù)。故當(dāng)k=t+1時命題也成立。

證畢

例2

有向圖G=〈V,E〉如圖7.3.5所示，用G的鄰接矩陣計算從頂點v3到v1的所有有向通路。

圖7.3.57.3.2可達矩陣

定義7.3.2

設(shè)G=〈V,E〉是一個線圖，V={v1,v2,…,vn}，令P(G)=［pij］n×n，其中

則稱P(G)為圖G的可達矩陣?？蛇_矩陣用于描述一個線圖中從任一結(jié)點到另一結(jié)點之間是否存在路。由于在圖中兩個結(jié)點之間有路，則必存在長度小于等于n－1的通路，另外認為同一個結(jié)點到自身可達，因此，P(G)可以用以下公式計算：

P(G)=［pij］n×n=A(0)∨A(1)∨…∨A(n－1)

其中，A(0)是n×n的單位陣，∨是邏輯加運算。利用鄰接矩陣A和可達矩陣P，可以判斷圖的連通性。

(1)無向線圖G是連通圖，當(dāng)且僅當(dāng)它的可達矩陣P的所有元素均為1。

(2)有向線圖G是強連通圖，當(dāng)且僅當(dāng)它的可達矩陣P的所有元素均為1。

(3)有向線圖G是單向連通圖，當(dāng)且僅當(dāng)P∨PT

的所有元素均為1。

(4)有向線圖G是弱連通圖，當(dāng)且僅當(dāng)以A∨AT

作為鄰接矩陣求得的可達矩陣P′中的所有元素均為1。

利用可達矩陣P，可以求得有向圖的強分圖,步驟如下：

設(shè)G=〈V,E〉，P為圖G的可達矩陣。考察P∨PT

，對于任何i∈={1，2，…,n},設(shè)第i行的非零元素所在的列分別是i1,i2,…,ik列，則結(jié)點集Vi={vi1,vi2,…,vik}導(dǎo)出的子圖G(Vi)是圖G的一個強分圖。

例3

設(shè)有向線圖G=〈V,E〉的鄰接矩陣A如圖7.3.6所示，求G的強分圖。圖7.3.6

例4

設(shè)有向圖D=〈V,E〉如圖7.3.7所示，請回答下列問題：

(a)D中v1到v4長度為3的通路有多少條？

(b)D是哪種類型的連通圖？圖7.3.7*7.3.3求解傳遞閉包的快速算法

定理7.3.2

設(shè)R是集合V上的二元關(guān)系，n∈Z+，對于任意a,b∈V，〈a,b〉∈Rn當(dāng)且僅當(dāng)R的關(guān)系圖G=〈V，E〉中存在從a到b的長度為n的有向路。

證明對n進行歸納。

(1)(歸納基礎(chǔ))根據(jù)關(guān)系圖的定義，從a到b存在一條長為1的路，當(dāng)且僅當(dāng)〈a,b〉∈R。故當(dāng)n=1時命題成立。

(2)(歸納假設(shè))假設(shè)當(dāng)n=k(k≥1)時，命題成立。

(3)(歸納推理)當(dāng)n=k+1時，從a到b存在一條長為k+1的路，當(dāng)且僅當(dāng)存在元素c∈V，使得從a到c存在一條長度為k的路;從c到b存在一條長為1的路，當(dāng)且僅當(dāng)存在元素c∈V，〈a,c〉∈Rk;〈c,b〉∈R，當(dāng)且僅當(dāng)〈a,b〉∈Rk

R=Rk+1。

因此，從a到b存在一條長為k+1的路，當(dāng)且僅當(dāng)〈a,b〉∈=Rk+1。

證畢°

由鄰接矩陣的定義可知，集合V上的二元關(guān)系R的關(guān)系矩陣就是其關(guān)系圖的鄰接矩陣。

設(shè)MR是n元素集合V上的二元關(guān)系R的關(guān)系矩陣，t(R)=R∪R2∪…∪Rn，R的傳遞閉包t(R)的關(guān)系矩陣Mt(R)=MR∨M(2)R∨…∨M(n)R。

例5

已知集合V={a,b,c}，集合V上二元關(guān)系R的關(guān)系圖如圖7.3.8(a)所示，求關(guān)系R的傳遞閉包t(R)的關(guān)系矩陣和關(guān)系圖。

圖7.3.8

定理7.3.3

設(shè)有向圖G=〈V,E〉，V={v1,v2,…,vn}，1≤k≤n，vi,vj∈V，若從vi到vj存在所有內(nèi)點屬于{v1,v2,…,vk}的路，當(dāng)且僅當(dāng)存在從vi到vj的路并且所有內(nèi)點屬于{v1,v2,…,vk－1}，或者存在從vi到vk的路和從vk到vj的路并且兩者所有內(nèi)點均屬于{v1,v2,…,vk－1}。

證明留作練習(xí)。

在定理7.3.3中，從vi到vj并且內(nèi)點屬于{v1,v2,…,vk－1}的路如圖7.3.9(a)所示，從vi到vk并且兩者所有內(nèi)點均屬于{v1,v2,…,vk－1}的路如圖7.3.9(b)所示。圖7.3.9給定MR是n元素集合V上的二元關(guān)系R的關(guān)系矩陣，V={v1,v2,…,vn}，其關(guān)系圖是有向圖G=〈V,E〉，設(shè)1≤k≤n，構(gòu)造矩陣W(k)=［W(k)ij］n×n，其中W(k)ij=1表示存在從vi到vj的路并且內(nèi)點屬于V={v1,v2,…,vk}，則Mt(R)=W(n)。根據(jù)以上知識我們知道，W(k)ij=1當(dāng)且僅當(dāng)存在從vi到vj的路并且所有內(nèi)點屬于{v1,v2,…,vk－1}，或者存在從vi到vk的路和從vk到vj的路并且兩者所有內(nèi)點均屬于{v1,v2,…,vk－1}。所以有：W(k)ij=Wij

(k－1)

∨(Wij

(k－1)

∧Wkj(k－1))。顯然,W(0)=MR。

當(dāng)k=1時，W(1)ij=W(0)ij∨(W(0)i1∧W(0)1j)

當(dāng)k=2時，W(2)ij=W(1)ij∨(W(1)i2∧W(1)2j)

…如此下去，直到求出k=n時，W(n)ij=Wij(n－1)∨(Win(n-1)

∧Wnj(n-1))，就得到傳遞閉包的關(guān)系矩陣Mt(R)=W(n)。

算法的過程描述如下：

(1)置新矩陣W=(MR)n×n。

(2)置k=1。

(3)對i=1,2,…,n，如果W［i,k］=1(i=1,2,…,n)，則對j=1,2,…,n，有

W［i,j］=W［i,j］∨W［k,j］

(4)k=k+1。

(5)如果k≤n，則轉(zhuǎn)步驟(3)，否則停止。7.4.1歐拉圖

18世紀，德國的東普魯士有座著名的哥尼斯堡(Konigsberg)城(現(xiàn)俄羅斯加里寧格勒)，橫貫全城的普雷格爾河的兩條支流將整個城市分為南區(qū)、北區(qū)、東區(qū)和島區(qū)(奈佛夫島)，人們在河的兩岸和兩個島之間架設(shè)了七座橋，把四個城區(qū)連接起來，如圖7.4.1(a)所示。當(dāng)時流傳這樣一個問題：是否有一種走法，從城中某個位置出發(fā)，通過每座橋一次且僅一次，最后回到出發(fā)地。這就是著名的哥尼斯堡七橋問題。7.4歐拉圖與漢密爾頓圖圖7.4.1

定義7.4.1

包含圖中所有邊的開跡稱為該圖中的一條歐拉跡(Euleriantrail)或歐拉路。包含圖中所有邊的閉跡稱為歐拉回路(Euleriancircuit)。含歐拉回路的圖稱為歐拉圖(Euleriangraph)。

以上定義對無向圖和有向圖均適用。下面討論歐拉圖時不考慮G是零圖的情況。

定理7.4.1

無向圖G=〈V,E〉是歐拉圖當(dāng)且僅當(dāng)G是連通的并且每個結(jié)點的度均為偶數(shù)。

證明必要性。如果G是歐拉圖，顯然G是連通的。設(shè)C為包含圖G中每條邊一次且僅一次的一條歐拉回路，如圖7.4.2所示，當(dāng)沿著C移動時，每通過一個結(jié)點一次，需使用關(guān)聯(lián)于這個結(jié)點的以前從未走過的兩條邊，即會用去該結(jié)點的2個度數(shù)。當(dāng)最終回到起點時，計算每個結(jié)點的度數(shù)，就等于它在歐拉回路中出現(xiàn)的次數(shù)乘以2，因此圖中所有結(jié)點的度數(shù)均為偶數(shù)。圖7.4.2充分性。設(shè)G連通，并且每個結(jié)點的度數(shù)均為偶數(shù)，則G中每個結(jié)點的度數(shù)均為大于等于2的偶數(shù)。根據(jù)定理7.2.2可知，G中必含圈。

在圖G中找到一個圈C1，設(shè)C1的邊集為E1，若E－E1=，即C1包含了G中的所有邊，則C1即為一條歐拉回路。否則，從圖G中刪掉C1中的所有邊E1，得到G的子圖G－E1，G－E1是非零圖，并且每個結(jié)點的度數(shù)仍然均為偶數(shù)。在G－E1中，任意選擇一個邊集不空的連通分支，找出一個圈C2，設(shè)C2的邊集為E2，若E－E1－E2=，即C1和C2中包含G中的所有邊，可由C1和C2構(gòu)造出G的一條歐拉回路。

否則，……

……?

?

如此下去，直到所有結(jié)點度數(shù)均為0。這樣可以從G中找到一組圈C1,C2,…,Cm且滿足：

E=E1∪E2∪…∪Em

(1)

Ei∩Ej＝i≠j，i,j∈{1,2,…,m}

(2)

即G中的每一條邊在且僅在E1,E2,…,Em的一個之中。?

現(xiàn)將閉跡集{C1,C2,…,Cm}連接成一條歐拉回路。從C1開始，由于G是連通的，所以在{C2,…,Cm}中至少有一個，設(shè)為Cp，滿足C1與Cp至少有一個公共結(jié)點，該結(jié)點設(shè)為v。

設(shè)C1=(v,vi1,

vi2,vi3,…,vim,v)，Cp=(v,vj1,vj2,vj3,…,vjt,v)則(v,vi1,vi2,vi3,…,vim,v，vj1,vj2,vj3,…,vjt,v)是一條恰包含C1和Cp中所有邊的閉跡，如圖7.4.3所示，記為T(1)。圖7.4.3將C1與Cp從閉跡集{C1,C2,…,Cm}中刪除，將T(1)加入其中，得到閉跡集{T(1),C2,…,Cp－1,Cp+1,…,Cm}。再開始考察T(1)，依然會得到一個包含更多邊的閉集。

……

重復(fù)此過程，直到閉跡集中僅剩下一條回路，即為歐拉回路。

故G是歐拉圖。

證畢

推論無向圖G中存在一條歐拉跡，當(dāng)且僅當(dāng)G是連通的，并且圖中恰有兩個奇數(shù)度的結(jié)點。

證明過程留作練習(xí)。特別指出：兩個奇數(shù)度的結(jié)點正是歐拉跡的起點和終點。

根據(jù)上述結(jié)論，很容易判斷哥尼斯堡七橋問題是不可解的，因為從圖7.4.1(b)中可以看出,deg(A)=5，deg(B)=deg(C)=deg(D)=3，故圖中不存在歐拉回路。

與七橋問題類似的還有一筆畫問題:要判定一個圖G是否可一筆畫出，即從圖G中某一結(jié)點出發(fā)，經(jīng)過圖G的每條邊一次且僅一次到達另一個結(jié)點。該問題可以用以上判定定理予以解決。

例1

圖7.4.4所示的各圖中，哪些圖可以一筆畫出?若能，請給出畫法。

圖7.4.4

例2

一塊多米諾骨牌由兩個半面組成，每個半面被標(biāo)記n個圓點，0≤n≤6，如圖7.4.5所示，共可產(chǎn)生多少塊不同的多米諾骨牌?能否將這些不同的多米諾骨牌排成一個圓環(huán)，使得每兩塊相鄰的多米諾骨牌的相鄰兩個半面是相同的？

圖7.4.5如果將7種不同的半面抽象成7個結(jié)點，那么關(guān)聯(lián)于任意兩個結(jié)點的無向邊可以看做是一張多米諾骨牌。每個結(jié)點與圖中所有的結(jié)點都恰有一條邊關(guān)聯(lián)，如圖7.4.6所示。

圖7.4.6

定理7.4.2

有向圖G是歐拉圖，當(dāng)且僅當(dāng)它是連通的，并且每個結(jié)點的入度等于其出度。

本定理證明過程與定理7.4.1類似，從略。

例3

若圖7.4.7(a)表示一個鄉(xiāng)鎮(zhèn)的地圖，結(jié)點表示交叉路口，邊表示街道，郵遞員每天騎自行車沿著街道兩側(cè)投遞郵件。能否為郵遞員找到一條沿街道的每一側(cè)恰好騎行一次就可以完成全部投遞工作的路線。

圖7.4.77.4.2漢密爾頓圖

1859年愛爾蘭數(shù)學(xué)家威廉·漢密爾頓(WillianHamilton)爵士在給他的朋友的一封信中，談到一個稱為“周游世界”的數(shù)學(xué)游戲。他將正十二面體的20個結(jié)點均標(biāo)上重要城市的名稱，希望能夠沿著正十二面體的棱行走，找到一個遍歷每個城市恰一次的周游路線。

如果將正十二面體的結(jié)點和邊畫在一個平面，如圖7.4.8(a)所示，“周游世界”游戲相當(dāng)于在圖7.4.8(a)中找到一條經(jīng)過每個結(jié)點一次且僅一次的回路。這個問題是有解的，如圖7.4.8(b)的粗線所示。圖7.4.8

定義7.4.2

包含圖中每個結(jié)點一次且僅一次的通路稱為漢密爾頓路(Hamiltonianpath)。包含圖中所有結(jié)點一次且僅一次的圈稱為漢密爾頓圈(Hamiltoniancycle)。含漢密爾頓圈的圖稱為漢密爾頓圖(Hamiltoniangraph)。

由于自回路和平行邊對于尋找漢密爾頓路沒有意義，因此以下僅討論簡單圖。

雖然漢密爾頓圖與歐拉圖問題頗為相似且同樣有趣，但是漢密爾頓圖問題到目前為止尚未完全解決，即還沒有找到一個簡單的判定漢密爾頓路或回路的存在性的充分必要條件。以下分別介紹漢密爾頓圖的必要條件和充分條件。

定理7.4.3

設(shè)G=〈V,E〉是無向圖，若圖G是漢密爾頓圖，則對于結(jié)點集V的每個非空子集S均滿足：

ω(G-S)≤|S|

其中，|S|表示S中的結(jié)點數(shù)，ω(G－S)表示G刪除S中所有結(jié)點后得到的連通分支個數(shù)。

證明設(shè)C是G中的一條漢密爾頓圈，則對于V的任一非空子集S，在C中刪除任一個S中的結(jié)點vi，如圖7.4.9所示，則C－vi是一條通路。若再刪去S中另一結(jié)點vj，最多形成2條通路，則ω(C－{vi,vj})≤2(當(dāng)vj為C－vi的起點或終點時，ω(C－{vi,vj})=1，當(dāng)vj為C－vi的中間結(jié)點時，ω(C－{vi,vj})=2)。重復(fù)此過程，不難得出ω(C－S)≤|S|。

同時，由于C－S是G－S的一個子圖，因而ω(G－S)≤ω(C－S)≤|S|。

證畢圖7.4.9

例4

判斷圖7.4.10(a)、(b)所示的圖是否是漢密爾頓圖。

圖7.4.10

解

(a)從圖中刪除a、b、c這3個結(jié)點后，所得子圖包含4個連通分支，如圖7.4.11(a)所示。

(b)從圖中刪除a、b這2個結(jié)點后，所得子圖包含3個連通分支，如圖7.4.11(b)所示。

因此以上兩圖均不是漢密爾頓圖。圖7.4.11

定理7.4.4

設(shè)G=〈X,E,Y〉是無向連通二部圖，其中，設(shè)|X|=m，|Y|=n。若m≠n，則G必不是漢密爾頓圖。

證明

方法1:用漢密爾頓圖的性質(zhì)證明。

因為|X|≠|(zhì)Y|，不妨設(shè)|X|＜|Y|,顯然有ω(G－X)=|Y|＞|X|，這與漢密爾頓圖的必要條件ω(G－X)≤|X|矛盾。因此G必不是漢密爾頓圖。因為|X|≠|(zhì)Y|，不妨設(shè)|X|＜|Y|。

假設(shè)G是漢密爾頓圖，則G中存在漢密爾頓圈C。因為|X|＜|Y|，所以在C中必然存在u,v∈Y，且u、v在C中鄰接。因此邊(u,v)∈E，這與二部圖中任何一條邊一個端點在X中而另一個端點在Y中矛盾。

因此G必不是漢密爾頓圖。

證畢

推論設(shè)G=〈X,E,Y〉是無向二部圖，其中，|X|=m，|Y|=n。若|m－n|＞1，則G中必不存在漢密爾頓路。

在圖中，有一種稱為A-B標(biāo)號法的操作，其過程是：選擇圖中任意一個結(jié)點標(biāo)記A，給與A鄰接的結(jié)點標(biāo)記B，再給與B鄰接的結(jié)點標(biāo)記A，重復(fù)此過程，直至給圖中所有結(jié)點給予標(biāo)記。對于一個圖進行A-B標(biāo)記，若使得圖中任意兩個鄰接結(jié)點的標(biāo)記均不相同，則稱該圖是可A-B標(biāo)記的，反之，稱為不可A-B標(biāo)記的。不難得出，一個圖是二部圖當(dāng)且僅當(dāng)它是可A-B標(biāo)記的。此外，A-B標(biāo)號法還有其他應(yīng)用。

例5

判斷圖7.4.12所示是否是漢密爾頓圖。

圖7.4.12

定理7.4.5

設(shè)G=〈V,E〉是含有n(n≥3)個結(jié)點的簡單無向圖，如果G中的任何兩個不同結(jié)點的度數(shù)之和都大于等于n－1，則G中存在漢密爾頓路。

證明

(1)證明G是連通的，采用反證法。

假設(shè)G中存在兩個或更多個互不連通的分支。設(shè)G中的結(jié)點vi和vj分別屬于兩個不同的連通分支G1和G2，其中G1和G2分別有n1和n2個結(jié)點。

顯然，n1+n2≤n，又有deg(vi)≤n1－1且deg(vj)≤n2－1,于是有：

deg(vi)+deg(vj)≤n1+n2－2=n－2

這與已知題設(shè)矛盾，所以G是連通的。

(2)證明G中存在漢密爾頓路。

在G中找到一條長度為p－1(0＜p＜n)的通路，如圖7.4.13所示，則該通路中含p個結(jié)點，設(shè)這些結(jié)點為v1,v2,…,vp。

圖7.4.13擴充這條通路，構(gòu)造G中的漢密爾頓路，方法如下：

①如果v1或vp還鄰接于不在這條路上的某個結(jié)點，則可立即延伸這條路以包含該結(jié)點，得到p條邊、p+1個結(jié)點的通路。

②如果v1和vp均只與該通路中的結(jié)點鄰接，那么接下來證明“存在一條包含結(jié)點v1,v2,…,vp的圈”。

a.如果v1與vp鄰接，則得到一條包含結(jié)點v1,v2,…,vp的圈。

b.如果v1與vp不鄰接。不妨設(shè)v1除鄰接v2外，還與vi1,vi2,…,vik(3≤i1＜i2＜…＜ik≤p－1)這k(k≤p-3)個結(jié)點鄰接，則vp至少與vi1－1,vi2－1,…,vik－1中之一鄰接,否則，vp至多與p－2－k個結(jié)點(除v1，vi1－1,vi2－1,…,vik－1，vp外)鄰接。因而deg(v1)+deg(vp)≤(k+1)+(p－2－k)=p－1≤n－2，這與已知題設(shè)矛盾。

因此，vp至少與vi1－1,vi2－1,…vik－1中之一鄰接。設(shè)v1與vit鄰接且vp與vit－1鄰接，如圖7.4.14所示，可以得到圈(v1,v2,…,vit－1,vp,vp－1,…,vit,v1)。圖7.4.14由于G是連通的，因此在該回路之外存在某結(jié)點x與回路中的結(jié)點vj鄰接?？梢杂萌鐖D7.4.15所示的方法將結(jié)點x引入到通路中來，從而得到一條長度為p的通路xvivi－1…v1vp

vp－1…vi+1。

重復(fù)上述過程，就一定能夠得到一條包含圖中所有n個結(jié)點的通路。

證畢圖7.4.15

推論設(shè)G是具有n個結(jié)點的簡單無向圖，如果G中每一對結(jié)點的度數(shù)之和大于等于n，則G中存在一條漢密爾頓圈。

證明由定理7.4.5可知，G中必存在漢密爾頓路，設(shè)為(v1,v2,…,vn)，如果v1與vn鄰接，則定理得證。

如果v1與vn不鄰接，不妨設(shè)v1除鄰接v2外，還鄰接于vi1,vi2,…,vik(3≤i1＜i2＜…＜ik≤n－1)總共k個結(jié)點，則vn至少與vi1－1,vi2－1,…,vik－1

中之一鄰接,否則,vp至多與n－2－k個結(jié)點(除v1，vi1－1,vi2－1,…,vik－1，vp外)鄰接。因而

deg(v1)+deg(vn)≤(k+1)+(n－2－k)=n－1＜n

這與已知題設(shè)矛盾。因此，vn至少與vi1－1,vi2－1,…,vik－1中之一鄰接。設(shè)v1與vit鄰接且vn與vit－1鄰接，如圖7.4.16所示。

可以得到一條漢密爾頓圈(v1,v2,…,vit－1,vn,vn－1,…,vit,v1)，故圖G是漢密爾頓圖。

證畢圖7.4.16

定義7.5.1

設(shè)G=〈V,E〉是一個無向圖，如果能夠把圖G圖示在一個平面上，且除端點外任意兩條邊均不相交，則稱G為平面圖(planar)，這樣的表示稱為G的一個平面嵌入(planarembedding)。

7.5平面圖應(yīng)該注意，有些圖雖然有邊在非端點處相交，如圖7.5.1(a)所示，但是可以通過移動圖中結(jié)點和邊的位置得到一個平面嵌入，如圖7.5.1(b)所示，這樣的圖是平面圖。

有些圖無論怎樣表示，總有邊在非端點處相交，這樣的圖是非平面圖。例如有三間房子，擬分別連接水、電、煤氣三種管線，如圖7.5.2(a)所示，該圖無論如何畫，總有邊在非端點處相交，如圖7.5.2(b)所示，它是非平面圖(nonplanar)。圖7.5.1圖7.5.2

定義7.5.2

設(shè)G是一連通平面圖，由圖G中的若干條邊包圍形成了一個區(qū)域，在該區(qū)域內(nèi)不再包含圖G中的邊和結(jié)點，這樣的區(qū)域稱為圖G的面(face)。設(shè)r是連通平面圖G的一個面，包圍面r的所有邊構(gòu)成的回路稱為該面的邊界，面r的邊界回路長度稱為該面的次數(shù)，記為deg(r)。

區(qū)域面積有限的面稱為有限面。區(qū)域面積無限的面稱為無限面。

例1

求圖7.5.3所示平面圖G中的所有面的次數(shù)。

圖7.5.3

解平面圖G中共有5個面，分別是圖中由r1、r2、r3、r4、r5所標(biāo)記的區(qū)域，各個面的邊界和次數(shù)如表7.5.1所示，其中r1是一個無限面，其余都是有限面。表7.5.1

定理7.5.1

設(shè)G=〈V,E〉是一連通平面圖，則圖G中所有面的次數(shù)之和等于邊數(shù)的兩倍，即

證明在連通平面圖中任何一條邊，它或者是兩個面的公共邊界，或者在一個面中作邊界重復(fù)計算兩次。所以圖G中所有面的次數(shù)之和等于邊數(shù)的兩倍。

證畢

定理7.5.2

設(shè)G=〈V,E〉是一連通平面圖，有n個結(jié)點、m條邊和r個面，則n－m+r=2成立。

證明對邊數(shù)m進行歸納。設(shè)nm和rm分別表示一個具有m條邊的連通平面圖的結(jié)點數(shù)和面數(shù)，即證明nm－m+rm=2。

(歸納基礎(chǔ))當(dāng)m=0時，連通圖G是一個孤立結(jié)點，則有n0=1,m=0,r0=1，故n0－0+r0=2。

當(dāng)m=1時有以下兩種情況，如圖7.5.4(a)、(b)所示。圖7.5.4對于圖7.5.4(a)，n1=1,m=1,r1=2，對于圖7.5.4(b)，n1=2,m=1,r1=1，因此，均有n1－1+r1=2成立。

(歸納假設(shè))假設(shè)m=k(k≥1)時公式成立，即nk－k+rk=2。

(歸納推理)考察m=k+1時的情況。用以下方法，從k+1條邊的連通平面圖G中去掉一條邊e。

(1)如果G中有度數(shù)為1的結(jié)點，則刪去該結(jié)點及其關(guān)聯(lián)的邊；否則執(zhí)行(2)。

(2)選擇G中一個面的邊界構(gòu)成的一條閉跡，刪去該閉跡上的一條邊。

因此得到一個具有k條邊的連通平面圖G′。根據(jù)歸納假設(shè)可知，G′滿足歐拉公式，即nk－k+rk=2。

(3)將刪去的一條邊放回原圖(對于情況(1)，結(jié)點也還原)，從而恢復(fù)圖G。根據(jù)(1)、(2)兩種不同的刪去方法，其邊數(shù)m、結(jié)點數(shù)nk、面數(shù)rk的變化情況分別如圖7.5.5(a)、(b)所示。

圖7.5.5①如圖7.5.5(a)所示，在這種情況下有：邊數(shù)加1，結(jié)點