離散數(shù)學第7章

第四篇 圖論

圖論是近年來發(fā)展迅速而又應用廣泛的一門新興學科。它最早起源于一些數(shù)學游戲的難題研究，如1736年歐拉（L.Euler)所解決的哥尼斯堡七橋問題。以及在民間廣為流傳的一些游戲問題：例如迷宮問題、棋盤上馬的行走路線問題等等。這些古老的問題當時吸引了許多學者的注意，從而在這些問題研究的基礎上，又提出了著名的四色猜想和環(huán)游世界各國的問題。例：用定理解決哥尼斯堡橋的問題

第四篇 圖論

圖論不斷發(fā)展，它在解決運籌學，網絡理論，信息論，控制論，博奕論以及計算機科學等各個領域的問題時，顯示出越來越大的效果。對于這樣一門應用廣泛的學科，其包含的內容是豐富的，本篇我們只準備介紹基本的概念和定理，為今后有關學科及課程的學習和研究提供方便。WWW電力網因特網復雜網絡的事例——技術網絡復雜網絡的事例——社會網絡朋友關系網演員網科學家合著網科學引文網復雜網絡的事例——交通運輸網絡城市公共交通網道路交通網航空網復雜網絡的事例——生物網絡神經網絡生態(tài)網絡蛋白質相互作用網絡基因網絡新陳代謝網絡SantaFe研究所的科學家合作網復雜網絡的事例——科學家合作網經濟物理學科學家合作網復雜網絡的事例——科學家合作網復雜網絡的事例——中藥方劑網示意圖點（藥材），邊（藥材之間相互作用），局域世界（方劑）§1圖的基本概念定義:

圖（graph）G由一個三元組<V(G),E(G),G>表示，其中：非空集合V(G)={v1,v2,…,vr}

稱為圖G的結點集，其成員vi(i=1,2,…,r)稱為結點或頂點（nodes

orvertices）；集合E(G)={e1,e2,…,es}

稱為圖G的邊集，其成員ej(j=1,2,…s)稱為邊(edges)。函數(shù)G

：E(G)→(V(G),V(G))

，稱為邊與頂點的關聯(lián)映射（associatvemapping）§1圖的基本概念例：G=<V(G)，E(G)，G>其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)abcde1e2e3e4e5e6§1圖的基本概念

討論定義：

(1)V(G)={V1，V2，…，Vn}為有限非空集合,Vi稱為結點,簡稱V是點集。

(2)E(G)={e1，…，em}為有限的邊集合,ei稱邊，每個ei都有V中的結點對與之相對應,稱E為邊集。即每條邊是連結V中的某兩個點的?！?圖的基本概念(3)若Ｇ中每一條邊e與有序偶對<vi,vj>或無序偶對(vi,vj)相關聯(lián)，則可說邊e連接結點vi和vj(4)可用e＝<vi,vj>或e＝(vi,vj)，以結點來表示圖的邊，這樣可把圖簡化成：Ｇ＝<Ｖ，Ｅ>。例：有圖如下，試寫成定義表達式Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝{v1,v2,v3,v4,v5}Ｅ＝{x1,x2,x3,x4,x5,x6}§1圖的基本概念例：對有向圖可表示為：Ｇ＝〈Ｖ、Ｅ〉，其中Ｖ＝｛a、b、c、d｝Ｅ＝｛<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>｝§1圖的基本概念下面定義一些專門名詞：(1)有向邊：若邊ej與結點序偶<vj,vk>關聯(lián)，那么稱該邊為有向邊。(2)無向邊：若邊ej與結點無序偶(vj,vk)關聯(lián)，那么稱該邊為無向邊?！?圖的基本概念(3)鄰接結點：由一條邊（有向或無向）連接起來的結點偶對。(4)（ｎ，ｅ）圖：具有ｎ個結點（頂點），ｅ條邊的圖?！?圖的基本概念(5)有向圖：在Ｇ中每一條邊均為有向邊。(6)無向圖：每條邊均為無向邊的圖。(7)混合圖：有些邊是無向邊，有些邊是有向邊的圖稱為混合圖?！?圖的基本概念V1’v1v4v5v1v2v3v4V2’V3’V4’(a)無向圖(b)有向圖(c)混合圖(孤立點)v2v3環(huán)§1圖的基本概念(8)點和邊的關聯(lián)：如ei=(u，v)或ei=<u，v>稱u，v與ei關聯(lián)。(9)點與點的相鄰：關聯(lián)于同一條邊的結點稱為鄰接點。(10)邊與邊的鄰接：關聯(lián)于同一結點的邊稱為鄰接邊。§1圖的基本概念(11)孤立結點：不與任何結點相鄰接的結點稱為孤立結點。(12)零圖：僅有孤立結點的圖。(13)平凡圖：僅有一個孤立結點的圖。(14)自回路(環(huán))：關聯(lián)于同一結點的邊稱為自回路，或稱為環(huán)。§1圖的基本概念(15)

平行邊：在有向圖中，始點和終點均相同的邊稱為平行邊，無向圖中若兩點間有多條邊，稱這些邊為平行邊，兩點間平行邊的條數(shù)稱為邊的重數(shù)。

定義：在圖G=<V，E>，vV，與結點v關聯(lián)的邊數(shù)稱為該點的度數(shù)，記為deg(v)。孤立結點的度數(shù)為0。圖G最大度記為(G)=max{deg(v)|vV(G)}，最小度數(shù)記為(G)=min{deg(v)|vV(G)}§1圖的基本概念

定義：在有向圖中，vV，以v為始點的邊數(shù)稱為該結點的出度，記作deg+(v);以v為終點的邊數(shù)稱為該結點的入度，記作deg-(v)。顯然有

deg(v)=deg+(v)+deg-(v)如：G1是無向圖，deg(v1)=3，deg(v2)=1G2是有向圖，deg+(v1)=2，deg-(v1)=3，deg(v1)=5，v1v2G1v1v3v4v2G2定理：每個圖中，結點度數(shù)總和等于邊數(shù)的兩倍。即deg(v)=2|E|vV

定理：在任何圖中,度數(shù)為奇數(shù)的結點必定是偶數(shù)個。定理：在任何有向圖中，所有結點的入度之和等于所有結點的出度之和。定義：含有平行邊的圖稱為多重圖。簡單圖：不含平行邊和環(huán)的圖稱為簡單圖。定義：簡單圖G=<V，E>中，若每一對結點間均有邊相連，則稱該圖為完全圖。有n個結點的無向完全圖記為Kn。定理：在任何圖中,n個結點的無向完全圖Kn的邊數(shù)為n(n-1)/2。無向完全圖：每一條邊都是無向邊不含有平行邊和環(huán)每一對結點間都有邊相連證明：n個結點中任取兩個結點的組合數(shù)為

Cn2

=

n(n-1)/2故的邊數(shù)為

|E|=n(n-1)/2定義：給定一個簡單圖G，由G中所有結點和所有能使G成為完全圖的添加邊組成的圖，稱為G的相對于完全圖的補圖，或簡稱為G的補圖，記為G。即G=<V，E1>，G=<V，E2>，其中E2={(u，v)u，vV，(u，v)E1}。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖K5(b)圖G(c)圖G的補圖G’定義：設圖G=<V，E>，如果有圖G’=<V’，E’>，且E’E，V’V，則稱G’為G的子圖。當V’=V時，則稱G’為G的生成子圖。相對于圖G的補圖定義：設G’=<V’，E’>是G=<V，E>的子圖，若給定另一個圖G”=<V”，E”>使得E”=E-E’，且V”中僅包含E”的邊所關聯(lián)的結點，則稱G”是子圖G’相對于圖G的補圖。定義：設圖G=<V，E>及圖G’=<V’，E’>，如果存在一一對應的映射g：vivi’且e=(vi，vj)(或<vi，vj>)是G的一條邊，當且僅當e’=(g(vi)，g(vj))(或<g(vi)，g(vj)>)是G’的一條邊，則稱G與G’同構，記作G≌G’。兩圖同構的一些必要條件：1.結點數(shù)目相同；2.邊數(shù)相等；3.度數(shù)相同的結點數(shù)目相等。§2路與回路

定義:

給定圖G=<V,E>,設v0,v1,…,vnV，e1,…,enE,其中ei是關聯(lián)于結點vi-1,vi的邊，交替序列v0e1v1e2…envn稱為結點v0到vn的路（擬路徑Pseudopath）

。

v0和vn分別稱為路的起點和終點，邊的數(shù)目n稱作路的長度。當v0=vn時，這條路稱作回路（閉路徑closedwalk）。

例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3v5e8v4e5v2e6v5e7v3e4v2v4e8v5e6v2e1v1e2v3v2e1v1e2v3e7v5e6v2§2路與回路

若一條路中所有的邊e1,…,en均不相同稱作跡（路徑walk）。若一條路中所有的結點v0,v1,…,vn均不相同,稱作通路（Path）。閉的通路,即除v0=vn之外，其余結點均不相同的路，稱作圈（回路circuit）。

§2路與回路

定理：

在一個具有n個結點的圖中，如果從結點vj到結點vk存在一條路，則從結點vj到結點vk必存在一條不多于n-1條邊的路。§2路與回路

推論：在一個具有n個結點的圖中，如果從結點vj到結點vk存在一條路，則從結點vj到結點vk必存在一條邊數(shù)小于n的通路?！?路與回路

定義：

在無向圖G中，如果從結點u和結點v之間若存在一條路，則稱結點u和結點v是連通的（connected）?！?路與回路

結點之間的連通性是結點集V上的等價關系。把子圖G(V1),G(V2),…,G(Vm)稱為圖G的連通分支（connectedcomponents）,圖G的連通分支數(shù)記為W(G)

?！?路與回路

定義：若圖G只有一個連通分支，則稱G是連通圖。顯然在連通圖中，任意兩個結點之間必是連通的?！?路與回路

對于連通圖，常常由于刪除了圖中的點或邊，而影響了圖的連通性。

刪除結點：所謂在圖中刪除結點v，即是把v以及與v關聯(lián)的邊都刪除。刪除邊：所謂在圖中刪除某條邊，即是把該邊刪除。

§2路與回路v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e

定義：設無向圖G=<V,E>是連通圖,若有結點集V1V,使圖G中刪除了V1的所有結點后,所得到的子圖是不連通圖,而刪除了V1的任何真子集后,所得到的子圖仍是連通圖,則稱V1是G的一個點割集(cut-set

ofnodes)。若某一個點構成一個點割集，則稱該點為割點。sabcdabcdba§2路與回路

點連通度：為了產生一個不連通圖需要刪去的點的最少數(shù)目，也稱為連通度,記為k(G)。即k(G)=min{|V1||是G的點割集}稱為圖G的點連通度(node-connectivity)?！?路與回路(1)若G是平凡圖則k(G)=0(2)k(Kn)=n-1(3)若圖存在割點，則k(G)=1(4)規(guī)定非連通圖的連通度k(G)=0§2路與回路v5v1v2v3v4v5v1v3v4點割集V1={v2}§2路與回路

定義：設無向圖G=<V,E>是連通圖,若有邊集E1E，使圖

G中刪除了E1的所有邊后，所得到的子圖是不連通圖，而刪除了E1的任何真子集后，所得到的子圖仍是連通圖，則稱E1是G的一個邊割集(cut-setof

edges)。若某一條邊就構成一個邊割集，則稱該邊為割邊或橋。割邊e使圖G滿足W(G-e)>W(G)

?！?路與回路

邊連通度(edge-connectivity)

(G)定義：非平凡圖的邊連通度為

(G)=min{|E1||E1是G的邊割集}

邊連通度

(G)是為了產生一個不連通圖需要刪去的邊的最少數(shù)目?！?路與回路(1)若G是平凡圖則(G)=0(2)若G存在割邊，則(G)=1，(3)規(guī)定非連通圖的邊連通度為(G)=0§2路與回路

定理：

對于任何一個圖G,有k(G)≤(G)≤δ(G)

。δ(G)=min(deg(v)，vV)§2路與回路

若G不連通，則k(G)=(G)=0，故上式成立。若G連通，可分兩步證明上式也成立：

1)先證明(G)≤(G)：如果G是平凡圖，則(G)=0≤(G)，若G是非平凡圖，則因每一結點的所有關聯(lián)邊必含一個邊割集，(因(G)=min{deg(v)|vV}，設uV使的deg(u)=δ(G)，與u相關聯(lián)的條邊必包含一個邊割集，至少這條邊刪除使圖不連通。)故(G)≤(G)?！?路與回路

2)再證k(G)≤(G)：(a)設(G)=1，即G有一割邊，顯然這時k(G)=l，上式成立?！?路與回路

(b)設(G)≥2，則必可刪去某(G)條邊，使G不連通，而刪去其中(G)-1條邊，它仍是連通的，且有一條橋e=(u，v)。對(G)-1條邊中的每一條邊都選取一個不同于u，v的端點，把這些端點刪去則必至少刪去(G)-1條邊。若這樣產生的圖是不連通的，則k(G)≤(G)-1<(G)，若這樣產生的圖是連通的，則e仍是橋，此時再刪去u或v就必產生一個不連通圖，故k(G)≤(G)。由1)和2)得k(G)≤(G)≤(G)?！?路與回路

定理：一個連通無向圖G的結點v是割點的充分必要條件是存在兩個結點u和w,使得結點u和w的每一條路都通過v

?！?路與回路

1)先證:v是割點存在結點u和w的每條路都通過v

若v是連通圖G=<V,E>割點，設刪去v得到的子圖G’,則G’至少包含兩個連通分支G1=<V1,E1>和G2=<V2,E2>

。任取uV1，wV2，因為G是連通的，故在G中必有一條連結u和w的路C，但u和w在G’中屬于兩個不同的連通分支，故u和w必不連通，因此C必須通過v，故u和w之間的任意一條路都通過v

。

§2路與回路

2)再證:存在結點u和w的每條路都通過v

v是割點若連通圖G中的某兩個結點的每一條路都通過v，則刪去v得到子圖G’

，在G’中這兩個結點必然不連通，故v是圖G的割點。§2路與回路

在無向圖G中，從結點u到v若存在一條路，則稱結點u到結點v是可達的?！?路與回路

對于任何一個有向圖G=<V,E>,從結點u和到結點v有一條路,稱為從u可達v?？蛇_性(accesible),是結點集上的二元關系，它是自反的和傳遞的，但是一般來說不是對稱的。故可達性不是等價關系?！?路與回路

如果u可達v，它們之間可能不止一條路，在所有這些路中，最短路的長度稱為u和v之間的距離（或短程線），記作d<u,v>，它滿足下列性質：

d<u,v>≥0d<u,u>=0d<u,v>+d<v,w>≥d<u,w>§2路與回路如果從u到v是不可達的，則通常寫成d<u,v>=∞注意：當u可達v，且v也可達u時，d<u,v>不一定等于d<v,u>§2路與回路有關距離的概念對無向圖也適用，把

D=maxd<u,v>,u,v∈V稱作圖的直徑。§2路與回路

定義:

在簡單有向圖G中，任何一對結點間，至少有一個結點到另一個結點是可達的，則稱這個圖是單側連通的?！?路與回路

如果對于圖G中的任何一對結點兩者之間是相互可達的，則稱這個圖是強連通的。如果在圖G中略去邊的方向，將它看成無向圖后，圖是連通的，則稱該圖為弱連通的。顯然，強連通圖→單側連通圖→弱連通圖。而逆推均不成立。§2路與回路v2v3v4v1(a)強連通v2v3v4v1(b)單側連通v2v3v4v1(c)弱連通§2路與回路

定理：一個有向圖是強連通的充分必要條件是G有一個回路，它至少包含每個結點一次?！?路與回路

證明：充分性：如G中有一條有向回路，經過每一點至少一次，則G中任意兩點u，v∈V，u可以沿著該有向回路的一部分的而到達v，則G是強連通圖?！?路與回路

必要性：任取u，v∈V，圖G是強連通圖，則u→v有有向路，v→u也有有向路，則u→v→u構成了一個有向回路，如果該有向回路沒有包含w，而u→w，w→u均有有向路，則u→v→u→w→u又是一個有向回路，一直下去可以將圖中所有的點均包含進去?！?路與回路

定義：在簡單有向圖中，具有強連通性質的最大子圖，稱為強分圖；具有單側連通性質的最大子圖，稱為單側分圖；具有弱連通性質的最大子圖，稱為弱分圖?！?路與回路v4v2v3v1(a)v5v4v2v3v1(b)§2路與回路

定理:在有向圖G=<V,E>中，它的每一個結點位于且只位于一個強分圖中?！?圖的矩陣表示

圖的鄰接矩陣表示方法

定義：設Ｇ＝＜Ｖ，Ｅ＞是簡單有向圖，其中V={v1,v2,…vn}定義一個nxn的矩陣A，并把其中各元素aij表示成：

則稱矩陣A為圖G的鄰接矩陣。§3圖的矩陣表示例：設圖Ｇ＝＜Ｖ，Ｅ＞如下圖所示討論定義：（1）圖G的鄰接矩陣中的元素為0和1，∴又稱為布爾矩陣；（2）圖G的鄰接矩陣中的元素的次序是無關緊要的，只要進行行和行、列和列的交換，則可得到相同的矩陣?！?圖的矩陣表示∴若有二個簡單有向圖，則可得到二個對應的鄰接矩陣，若對某一矩陣進行行和行、列和列之間的交換后得到和另一矩陣相同的矩陣，則此二圖同構。（3）當有向圖中的有向邊表示關系時，鄰接矩陣就是關系矩陣；（4）零圖的鄰接矩陣稱為零矩陣，即矩陣中的所有元素均為0；（5）在圖的鄰接矩陣中，①行中1的個數(shù)就是行中相應結點的引出次數(shù)②列中1的個數(shù)就是列中相應結點的引入次數(shù)§3圖的矩陣表示２．矩陣的計算：§3圖的矩陣表示主對角線上的數(shù)表示結點i（或j）的引出次數(shù)。

主對角線上的數(shù)表示結點i（或j）的引入次數(shù)。§3圖的矩陣表示表示i和j之間具有長度為2的路徑數(shù)，表示i和j之間具有長度為3的路徑數(shù)，表示i和j之間具有長度為4的路徑數(shù)，§3圖的矩陣表示bij表示從結點vi到vj有長度分別為1，2，3，4的不同路徑總數(shù)。此時，bij0，表示從vi到vj是可達的?！?圖的矩陣表示定義：設Ｇ＝＜Ｖ，Ｅ＞是簡單有向圖，其中|V|=ｎ（），定義一個矩陣P，它的元素為：則P稱為圖G的可達性矩陣。

由可計算出可達性矩陣，其方法是：若中（i,j）是非“0”元素，則對應，否則?！?圖的矩陣表示定義：設無向圖Ｇ＝＜Ｖ，Ｅ＞，

其中，則稱B為無向圖G的完全關聯(lián)矩陣。

令可達矩陣表明了圖中任意兩結點間是否至少存在一條路以及在結點處是否有回路。從圖G的鄰接矩陣A可以得到可達矩陣P，即令Bn=A+A2+A3+…+An，再從Bn中非零元素改為1而零元素不變，這種變換后的矩陣即是可達矩陣P?！?圖的矩陣表示例：討論定義：（1）完全關聯(lián)矩陣為布爾矩陣；（2）對應B中行均為0的結點為孤立結點，只有一個“1”的行的結點一定為懸掛的邊，且一定不在任一循環(huán)中全部為1的行的結點必定聯(lián)結圖中所有的結點。3)每一條邊關聯(lián)兩個結點,故每一列中只有兩個1。

4)每一行中元素之和等于該行對應的結點的度數(shù)。

5)兩個平行邊其對應的兩列相同。

6)同一個圖當結點或邊的編號不同時，其對應的矩陣只有行序列序的差別。有向圖的關聯(lián)矩陣

定義：給定簡單有向圖G=<V,E>,設v1,v2,…,vpV,e1,…,eqE,稱p×q階矩陣M(G)=(mij)p×q

為圖G的完全關聯(lián)矩陣(incidencematrix)。其中:1

若vi是

ej的起點。

-1

若vi是

ej的終點。

0若vi不關聯(lián)

ej。mij=

有向圖的關聯(lián)矩陣的特點：

(1)每一列中有一個1和一個-1，對應一邊一個始點、一個終點，元素和為零。

(2)每一行元素的絕對值之和為對應點的度數(shù)。-1的個數(shù)等于入度，1的個數(shù)等于出度。

有向圖G的兩行相加定義為：第i行第j列的對應元素算術相加；相當于刪除結點vi與結點vj之間的關聯(lián)邊，合并結點vi和vj

。合并后得到的新結點記為vi,j。無向圖G的兩行相加定義為：第i行第j列的對應元素模2相加；相當于刪除結點vi與結點vj之間的關聯(lián)邊，合并結點vi和vj

。合并后得到的新結點記為vi,j。

3、關聯(lián)矩陣的秩

定理：

如果一個連通圖G=<V,E>,有r個結點,則其完全關聯(lián)矩陣M(G)的秩為r-1,即rankM(G)=r-1

。推論：如果一個連通圖G=<V,E>,有r個結點,w個最大連通子圖,則圖G的完全關聯(lián)矩陣M(G)的秩為r-w,即rankM(G)=r-w

。

例：寫出如圖7-3.11所示的圖G的完全關聯(lián)矩陣，并驗證其秩如定理7-3.2所述。e1e2e3e4e5e6e7e8e9A100001010B011000100C000110010D110000001E000011100F001100001完全關聯(lián)矩陣為:此圖為連通圖，由定理其秩為5?！?歐拉圖和漢密爾頓圖2.定理7-4.1

無向圖G具有一條歐拉路，當且僅當G連通，并且有零個或兩個奇數(shù)度結點。1.定義7-4.1

如果無孤立結點圖G上有一條經過G的所有邊一次且僅一次的路徑，則稱該路徑為圖G的歐拉路徑（Eulerwalk）。如果圖G上有一條經過G邊一次且僅一次的的回路，則稱該回路為圖G的歐拉回路，具有歐拉回路的圖稱為歐拉圖（Eulergraph）。

由于有了歐拉路和歐拉回路的判別準則，因此哥尼斯堡七橋問題立即有了確切的否定答案，因為從圖中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)=3，故歐拉回路必不存在。3.定理7-4.1的推論

無向圖G具有一條歐拉路，當且僅當G連通且所有結點度數(shù)皆為偶數(shù)。例：用定理解決哥尼斯堡橋的問題一筆畫問題要判定一個圖G是否可一筆畫出，有兩種情況：一是從圖G中某一結點出發(fā)，經過圖G的每一邊一次僅一次到達另一結點。另一種就是從G的某個結點出發(fā)，經過G的每一邊一次僅一次再回到該結點。上述兩種情況分別可以由歐拉路和歐拉回路的判定條件予以解決。定義7-4.2：給定有向圖G，通過圖中每邊一次且僅一次的一條單向路（回路），稱作單向歐拉路（回路）?？梢詫W拉路和歐拉回路的概念推廣到有向圖中。

定理7-4.2

有向圖G為具有一條單向歐拉回路，當且僅當G連通，并且每個結點的入度等于出度。有向圖G有單向歐拉路，當且僅當G連通，并且恰有兩個結點的入度與出度不等，它們中一個的出度比入度多1，另一個入度比出度多1。

例1有向歐拉圖應用示例：計算機鼓輪的設計。鼓輪表面分成24=16等份，其中每一部分分別用絕緣體或導體組成，絕緣體部分給出信號0，導體部分給出信號1，在下圖中陰影部分表示導體，空白體部分表示絕緣體，根據鼓輪的位置，觸點將得到信息4個觸點a,b,c,d讀出1101(狀態(tài)圖中的邊e13),轉一角度后將讀出1010(邊e10)。問鼓輪上16個部分怎樣安排導體及絕緣體才能使鼓輪每旋轉一個部分，四個觸點能得到一組不同的四位二進制數(shù)信息。01111111100000001110abcd

設有一個八個結點的有向圖，如下圖所示。其結點分別記為三位二進制數(shù){000，001，……，111}，設ai{0,1}，從結點a1a2a3可引出兩條有向邊，其終點分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。按照上述方法，對于八個結點的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式，即是第一條邊標號的后三位數(shù)與第二條邊的頭三位數(shù)相同。由于圖中16條邊被記為不同的二進制數(shù)，可見前述鼓輪轉動所得到16個不同位置觸點上的二進制信息，即對應于圖中的一條歐拉回路。

設有一個八個結點的有向圖，如下圖所示。其結點分別記為三位二進制數(shù){000，001，……，111}，設ai{0,1}，從結點a1a2a3可引出兩條有向邊，其終點分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。按照上述方法，對于八個結點的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式，即是第一條邊標號的后三位數(shù)與第二條邊的頭三位數(shù)相同。由于圖中16條邊被記為不同的二進制數(shù)，可見前述鼓輪轉動所得到16個不同位置觸點上的二進制信息，即對應于圖中的一條歐拉回路。

所求的歐拉回路為：

e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0)

（從圖示位置開始）

e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6(e13)

所求的二進制序列為：

0000100110101111(0)

1101011110000100(1)（從圖示位置開始）

上述結論可推廣到鼓輪具有n個觸點的情況。構造2n-1

個結點的有向圖，每個結點標記為n-1位二進制數(shù),從結點a1a2a3...an-1出發(fā),有一條終點為a2a3...an-10的邊,該邊記為a1a2a3...an-10；還有一條終點標記為a2a3...an-11的邊,該邊記為a1a2a3...an-11

。鄰接邊的標記規(guī)則為：“第一條邊后n-1位與第二條邊前n-1位二進制數(shù)相同”。二、漢密爾頓圖

與歐拉回路類似的是漢密爾頓回路。它是1859年漢密爾頓首先提出的一個關于12面體的數(shù)學游戲：能否在圖7-4.6中找到一個回路，使它含有圖中所有結點一次且僅一次？若把每個結點看成一座城市，連接兩個結點的邊看成是交通線，那么這個問題就變成能否找到一條旅行路線，使得沿著該旅行路線經過每座城市恰好一次，再回到原來的出發(fā)地？他把這個問題稱為周游世界問題。定義7-4.3：給定圖G，若存在一條路經過圖中的每個結點恰好一次，這條路稱作漢密爾頓路。若存在一條回路，經過圖中的每個結點恰好一次，這條回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。圖7-4.6存在一條漢密爾頓回路，它是漢密爾頓圖定理7-4.3若圖G＝<V，E>具有漢密爾頓回路，則對于結點集V的每個非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的連通分支數(shù)。證明設C是G的一條漢密爾頓回路，對于V的任何一個非空子集S，在C中刪去S中任一結點a1，則C-a1是連通的非回路，W(C-a1)=1，|S|≥1，這時W(C-S)≤|S|。若再刪去S中另一結點a2，則W(C-a1-a2)≤2，而|S|≥2，這時W(C-S)≤|S|。由歸納法可得：W(C-S)≤|S|。同時C-S是G-S的一個生成子圖，因而W(G-S)≤W(C-S)，所以W(G-S)≤|S|。

此定理是必要條件，可以用來證明一個圖不是漢密爾頓圖。

如右圖，取S={v1,v4}，則G-S有3個連通分支，不滿足W(G-S)≤|S|，故該圖不是漢密爾頓圖。

所以用此定理來證明某一特定圖是非漢密爾頓圖并不是總是有效的。例如，著名的彼得森(Petersen)圖，在圖中刪去任一個結點或任意兩個結點，不能使它不連通；刪去3個結點，最多只能得到有兩個連通分支的子圖；刪去4個結點，只能得到最多三個連通分支的子圖；刪去5個或5個以上的結點，余下子圖的結點數(shù)都不大于6，故必不能有5個以上的連通分支數(shù)。所以該圖滿足W(G-S)≤|S|，但是可以證明它是非漢密爾頓圖。說明：此定理是必要條件而不是充分條件。有的圖滿足此必要條件，但也是非漢密爾頓圖。下面的定理給出一個無向圖具有漢密爾頓路的充分條件

定理7-4.4

設圖G具有n個結點的簡單圖,如果G中每一對結點度數(shù)之和大于等于n-1,則G中存在一條漢密爾頓路。證明思路：1)先證G連通:

若G有兩個或多個互不連通的分支,設一個分圖有n1個結點,任取一個結點v1,另一分圖有n2個結點,任取一個結點v2,因為deg(v1)≤n1-1,deg(v2)≤n2-1,deg(v1)+deg(v2)≤n1+n2-2<n-1,與假設矛盾,G是連通的。2)先證(構造)要求的漢密爾頓路存在:

設G中有p-1條邊的路,p<n,它的結點序列為v1,v2,…,vp。如果有v1或vp鄰接于不在這條路上的一個結點,立刻擴展該路,使它包含這個結點,從而得到p條邊的路。否則v1和vp都只鄰接于這條路上的結點,我們證明在這種情況下,存在一條回路包含結點v1,v2,…,vp。

若v1鄰接于vp,則v1,v2,…,vp即為所求。若v1鄰接于結點集{vl,vm,…,…,vj,…,vt}中之一,這里2≤l,m,...,j,...,t≤p-1,如果vp是鄰接于vl-1,vm-1,…,…,vj-1,…,vt-1中之一,譬如是vj-1,則v1v2…vj-1vpvp-1...vjv1是所求回路（如圖7-4.9(a)所示）。如果vp不鄰接于vl-1,vm-1,…,…,vj-1,…,vt-1中任一個,則vp最多鄰接于p-k-1個結點,deg(vp)≤p-k-1,deg(v1)=k,故deg(vp)+deg(v1)≤p-k-1+k<n-1,即v1與vp度數(shù)之和最多為n-2，得到矛盾。至此，已經構造出一條包含結點v1,v2,…,vp的回路,因為G是連通的,所以在G中必有一個不屬于該回路的結點vx與回路中某一結點vk鄰接,如圖7-4.9(b)所示,

于是就得到一條包含p條邊的回路(vx,vk,vk+1,…,vj-1,vp,vp-1,…,vj,v1,v2,…,vk-1),如圖7-4.9(c)所示,重復前述構造方法，直到得到n-1條邊的路。例某地有5個風景點，若每個景點均有兩條道路與其他景點相通，問是否可經過每個景點一次而游完這5處。解將景點作為結點，道路作為邊，則得到一個有5個結點的無向圖。由題意，對每個結點vi(i=1,2,3,4,5)有

deg(vi)=2。則對任兩點和均有

deg(vi)+deg(vj)=2+2=4=5–1

所以此圖有一條漢密爾頓回路。即經過每個景點一次而游完這5個景點。例：在七天內安排七門課程的考試，使得同一位教師所任的兩門課程不排在接連的兩天中，試證明如果沒有教師擔任多于四門課程，則符合上述要求的考試安排總是可能的。證明：設G為具有七個結點的圖，每個結點對應于一門課程考試，如果這兩個結點對應的課程考試是由不同教師擔任的，那么這兩個結點之間有一條邊，因為每個教師所任課程數(shù)不超過4，故每個結點的度數(shù)至少是3，任兩個結點的度數(shù)之和至少是6，故G總是包含一條漢密爾頓路，它對應于一個七門考試課程的一個適當?shù)陌才拧?.定理7-4.5

設圖G具有n個結點的簡單圖,如果G中每一對結點度數(shù)之和大于等于n,則G中存在一條漢密爾頓回路。證明思路：由定理7-4.4知,必有一條漢密爾頓路,設為v1,v2,…,vn,若v1與vn鄰接,則定理得證。若v1與vn不鄰接,假設v1鄰接于{vi1,vi2,…,vik},2≤ij≤n-1,vn必鄰接于vi1-1,vi2-1,…,vik-1中之一。若vn不鄰接于vi1-1,vi2-1,…,vik-1中之一,則vn至多鄰接于n-k-1個結點,因而,

deg(vn)≤n-k-1,而

deg(v1)=k,

deg(v1)+deg(vn)≤n-k-1+k=n-1,與假設矛盾,所以必有一條漢密爾頓路v1v2…vj-1vnvn-1…vjv1,如圖7-4.11所示。