重慶大學《離散數(shù)學》課件第7章-圖論

1離散數(shù)學

第四篇圖論胡春強重慶大學大數(shù)據(jù)與軟件學院第七章圖論(GraphTheory)7.1圖的基本概念(Graph)7.2路與回路(Walks&Circuits)7.3圖的矩陣表示(MatrixNotationofGraph)7.4歐拉圖與哈密爾頓圖(EulerianGraph&HamiltonianGraph)7.5平面圖(PlanarGraph)7.7樹與生成樹(TreesandSpanningTrees)7.8根樹及其應用(RootedTreesandItsApplications)7-1圖的基本概念定義7-1.1圖一個圖是一個三元組〈V(G)，E(G)，

G〉，其中V(G)是一個非空的結點集合，E(G)是邊的集合，

G為邊集E到結點無序偶（有序偶）集合上的函數(shù)。若把圖中的邊看作總與兩個結點關聯(lián)，集合E(G)的元素e可表示為序偶〈vi，vj〉，在不強調邊的方向時（即為無向邊時，〈vi，vj〉又可表示為(vi，vj)）。在這樣的約定下，可將圖的定義簡化為二元組〈V(G)，E(G)〉。舉例說明：不同形狀的圖形表示同一圖7-1圖的基本概念定義：無向邊和有向邊若邊ei與無序偶(vj,vk)相關聯(lián),則稱邊為無向邊。若邊ei與有序偶<vj,vk>相關聯(lián),則稱邊為有向邊。其中vj稱為ei

的起始結點;vk

稱為ei的終止結點。7-1圖的基本概念[定義]無向圖，有向圖和混合圖每一條邊都是無向邊的圖稱為無向圖,如圖7-1.2(a)所示，表示為：G=<V,E>=<{a,b,c,d,e},{(a,b),(a,d),(b,c),(b,d)}>每一條邊都是有向邊的圖稱為有向圖,如圖7-1.2(b)所示，表示為：G’=<V,E>=<{a,b,c,d},{<b,a>,<b,c>,<d,b>,<d,c>}>如果在圖中一些邊是有向邊,另一些邊是無向邊,這個圖稱為混合圖,如圖7-1.2(c)所示，表示為：G”=<V,E>=<{a,b,c,d},{(a,d),(a,c),(b,c),<c,c>,<b,a>,<d,b>}>7-1圖的基本概念圖7-1.2無向圖、有向圖和混合圖7-1圖的基本概念[定義]鄰接點在一個圖中，兩個結點由一條有向邊或無向邊關聯(lián)，則這兩個結點稱為鄰接點。[定義]鄰接邊在一個圖中，關聯(lián)于同一個結點的兩個邊稱為鄰接邊。[定義]孤立點在一個圖中不與任何結點相鄰接的結點，稱為孤立點。如圖7-1.2(a)中的結點e。7-1圖的基本概念[定義]零圖僅由孤立結點組成的圖（E=

）稱為零圖[定義]平凡圖僅由一個孤立點構成的圖(|V|=1)稱為平凡圖。[定義]自回路或環(huán)關聯(lián)于同一結點的一條邊稱為自回路或環(huán)。如圖7-1.2中(c,c)是環(huán)。環(huán)的方向是沒有意義的，它既可以作為有向邊，也可以作為無向邊。7-1圖的基本概念[定義7-1.2]結點的度數(shù)

在圖G＝〈V，E〉中，與結點v(v∈V)關聯(lián)的邊數(shù)稱為該結點的度數(shù)，記作deg(v)。例如在圖7-1.3（b）中，結點A的度數(shù)為2，結點B的度數(shù)為3，我們約定：每一個環(huán)在其對應的結點上的度數(shù)增加2。故圖7-1.3（b）中結點E的度數(shù)為5。7-1圖的基本概念圖7-1.3度數(shù)示意圖7-1圖的基本概念[定義]圖G的最大度和最小度

Δ(G)＝max{deg(v)｜v∈V(G)}，

δ(G)＝min{deg(v)｜v∈V(G)},

分別稱G＝〈V,E〉的最大度和最小度。如圖7-1.3（b）中,Δ(G)＝5,δ(G)＝2。7-1圖的基本概念7-1圖的基本概念[定理7-1.1]握手定理

每個圖中，結點度數(shù)的總和等于邊數(shù)的兩倍。證明：因為每條邊關聯(lián)著兩個結點,而每條邊分別給這兩個結點的度數(shù)為1。因此在一個圖中，結點度數(shù)的總和等于邊數(shù)的兩倍。[定理7-1.2]

在任何圖中,度數(shù)為奇數(shù)的結點,必定是偶數(shù)個。證明設V1為圖G中度數(shù)為奇數(shù)的結點集,而V2為圖G中度數(shù)為偶數(shù)的結點集,則根據(jù)定理7-1.1,有由于為偶數(shù)之和，是偶數(shù),又2|E|為偶數(shù),所以必為偶數(shù)，所以|V1|為偶數(shù)。7-1圖的基本概念[定義7-1.3]

結點的入度，結點的出度，結點的度數(shù)在有向圖中,射入一個結點的邊數(shù)稱為該結點的入度,由一個結點射出的邊數(shù)稱為該結點的出度。結點的出度和入度之和就是該結點的度數(shù)。7-1圖的基本概念[定理7-1.3]

在任何有向圖中，所有結點入度之和等于所有結點出度之和，都等于邊數(shù)。證明：因為每一條有向邊必對應一個入度和一個出度,若一個結點具有一個入度或出度,則必關聯(lián)一條有向邊,所以,有向圖中各結點入度之和等于邊數(shù),各結點出度之和也等于邊數(shù)。因此任何有向圖中,入度之和等于出度之和。7-1圖的基本概念在上面所講的圖的概念中，一個結點的度數(shù)可能大于１，但是任何一對結點間常常不多于一條邊。[定義]平行邊連接于同一對結點間的多條邊稱為平行邊。[定義7-1.4]多重圖含有平行邊的任何一個圖稱為多重圖。7-1圖的基本概念圖7-1.4多重圖7-1圖的基本概念[定義]簡單圖把不含有平行邊和環(huán)的圖稱為簡單圖。[定義7-1.5]完全圖簡單圖G＝〈V,E〉中若每一對結點間都有邊相連,則稱該圖為完全圖。有n個結點的無向完全圖記作Kn。7-1圖的基本概念定理7-1.4

n個結點的無向完全圖Kn的邊數(shù)為n(n-1)/2。證明:在Kn中,任意兩個結點都有邊相連,n個結點中任兩個點的組合數(shù)為:7-1圖的基本概念故Kn的邊數(shù)為如果在有向圖中，對每一對節(jié)點之間都有兩條方向相反的邊連接，就稱該圖為n個結點的有向完全圖。顯然,它的邊數(shù)為

|E|

=

n(n-1)7-1圖的基本概念什么叫做給一個圖添加或刪除一個結點或邊呢？添加一個結點，即集合V增加一個元素，在圖形中畫上一個點；添加一條邊即現(xiàn)有的圖形中的兩個結點加上一條邊。在現(xiàn)有的圖中刪除一條邊是將圖形中的一條邊刪除；而刪除一個結點不僅僅將此結點刪去，而且要刪去由此結點連接的所有邊。7-1圖的基本概念給定任意含有n個結點的圖G,總可以把它補成一個具有同樣結點的完全圖,方法是把那些沒有聯(lián)上邊的結點添加上邊。7-1圖的基本概念[定義7-1.6]

相對于完全圖的補圖給定一個圖G,由G中所有結點和所有能使G成為完全圖的添加邊組成的圖,稱為G的相對于完全圖的補圖,或簡稱為G的補圖,記作G。7-1圖的基本概念圖7-1.6相對于完全圖的補圖如圖7-1.6中的(a)和(b)互為補圖。7-1圖的基本概念[定義7-1.7]子圖設圖G=<V,E>，如果有圖G’=<V’,E’>，若有V’

V，E’

E，則稱圖G’是圖G的子圖。[定義]生成子圖如果圖G的子圖G’包含G的所有結點,則稱該圖G’為G的生成子圖。如圖7-1.8中G'和G"都是G的生成子圖。7-1圖的基本概念[定義7-1.8]

相對于圖G的補圖設圖G'＝〈V',E'〉是圖G＝〈V,E〉的子圖,若給定另外一個圖G"＝〈V",E"〉使得E"＝E-E',且V"中僅包含E"的邊所關聯(lián)的結點。則稱G"是子圖G'的相對于圖G的補圖。7-1圖的基本概念圖7-1.7(c)為(b)相對于(a)的補圖7-1圖的基本概念如圖7-1.7中的圖(c)是圖(b)相對于圖(a)的補圖。而圖(b)不是圖(c)相對于圖(a)的補圖,因為圖(b)中有結點c。在上面的一些基本概念中,一個圖由一個圖形表示,由于圖形的結點的位置和連線長度都可任意選擇,故一個圖的圖形表示并不是唯一的。下面我們討論圖的同構的概念。7-1圖的基本概念[定義7-1.9]圖的同構設圖G＝〈V,E〉和圖G'＝〈V',E'〉,如果存在一一對應的映射g:V→V’且e＝(vi,vj)(或〈vi,vj〉)

E,當且僅當e’＝(g(vi),g(vj))(或〈g(vi),g(vj)〉)

E’，則稱G和G'同構,記作G≌G'。7-1圖的基本概念圖7-1.8圖的同構7-1圖的基本概念從這個定義可以看出,若G與G‘同構,它的充要條件是:兩個圖的結點和邊分別存在著一一對應,且保持關聯(lián)關系,例如圖7-1.8中,(a)與(b)不是同構的,(c)與(d)是同構的。從圖7-1.8的(c)與(d)可以看出此兩圖在結點間存在著一一對應的映射G:G(a)＝u3,G(b)＝u1,G(c)＝u2,且有:〈a,c〉,〈a,b〉,〈b,d〉,〈c,d〉分別與〈u3,u4〉,〈u3,u1〉,〈u1,u2〉,〈u4,u2〉一一對應。7-1圖的基本概念表7-1.1

分析本例還可以知道,此兩圖結點的度數(shù)也分別對應相等,如表7-1.1所示。結點abcd結點v1v2v3v4出度2101出度1021入度0121入度12017-1圖的基本概念兩圖同構的一些必要條件:1.結點數(shù)目相等;3.邊數(shù)相等;3.度數(shù)相等的結點數(shù)目相等。需要指出的是這幾個條件不是兩個圖同構的充分條件,例如圖7-1.9中的(a)和(b)滿足上述的三個條件,但此兩個圖并不同構。7-1圖的基本概念圖7-1.9不同構的圖7-1圖的基本概念在現(xiàn)實世界中,常常要考慮這樣的一個問題:如何從一個圖G中的給定的結點出發(fā),沿著一些邊連續(xù)移動,達到另一個指定的結點,這種依次由點和邊組成的序列,就形成路的概念。7-2路與回路定義7-2.1路給定圖G=〈V,E〉,設v0，v1，…，vn∈V,e1，e2，…，en∈E,其中ei是關聯(lián)結點vi-1,vi的邊,交替序列v0e1v1e2…envn稱為聯(lián)結v0到vn的路。路:v1e2v2e3v3e4v2e6v5e7v37-2路與回路[定義]路的長度v0和vn分別稱作路的起點和終點,邊的數(shù)目n稱作路的長度。[定義]回路當v0=vn時,這條路稱作回路。[定義]跡若一條路中所有的邊e1，e2，…，en均不相同,稱作跡。(邊不相同，但結點可以重復)跡:v5e8v4e5v2e6v5e7v3e2v47-2路與回路[定義]通路若一條路中所有的結點v0，v1，…，vn均不同,則稱作通路。(1)通路:v4e8v5e6v2e1v1e2v3[定義]圈閉的通路,即除v0=vn外,其余的結點均不相同的路,就稱作圈。圈:v2e1v1e3v3e7v5e6v27-2路與回路例如在圖7-2.1中有7-2路與回路圖7-2.1路的例子路:v1e2v3e3v2e3v3e4v2e6v5e7v3跡:v5e8v4e5v2e6v5e7v3e4v2通路:v4e8v5e6v2e1v1e2v3圈:v2e1v1e2v3e7v5e6v2在簡單圖中一條路v0e1v1e2…envn

，由它的結點序列v0v1…vn確定,所以簡單圖的路,路可由其結點序列[v0v1…vn]表示。在有向圖中,結點數(shù)大于1的一條路可由邊序列[e1e2…en]表示。7-2路與回路[定理7-2.1]在一個具有n個結點的圖中，如果從結點vj到結點vk存在一條路，則從結點vj到結點vk存在一條不多于n-1條邊的路。證明

如果從結點vj到結點vk存在一條路，則該路上的結點序列是[vj…vi…vk]，如果在這路上有l(wèi)條邊，則序列中必有l(wèi)+1個結點，若l>n-1，結點數(shù)>n,則必有結點vs，它在序列中不止一次出現(xiàn)，即必有序列[vj…vs…vs…vk]，在路中去掉從vs到vs的這些邊，仍然得到一條從結點vj到結點vk的路，但此路比原來的路的邊數(shù)要少。如此重復進行下去，必得到一條從結點vj到結點vk不多于n-1條邊的路。7-2路與回路[推論]

在具有n個結點的圖中，若從結點vj到結點vk存在一條路，則存在一條從結點vj到結點vk而邊數(shù)小于n的通路。[定義7-2.2]連通在無向圖G中，結點u和v之間若存在一條路，則結點u和v稱為是連通的。結點u和v之間連通，用[u，v]表示。7-2路與回路[定理]在一個簡單無向連通圖中，結點之間的連通性是結點集V上的等價關系?！咀C明】⑴[u，u]為真。（自反性）⑵若[u，v]為真，則[v，u]為真。（對稱性）⑶若[u，v]為真且[v，w]為真，則[u，w]為真。（傳遞性）根據(jù)等價關系R進行關于V的等價分類，則關于V的等價類為關于V的一個劃分。7-2路與回路[定義]連通分支

根據(jù)圖G中的一個結點v定義圖G的子圖[v]G如下：[v]G=〈V(v)，E(v)〉，其中V(v)={x｜[v，x]為真}；E(v)包含所有連結V(v)中結點的邊。[v]G

為V(v)的一個等價類，稱它為G的一個連通分支。7-2路與回路[定理7-2.3]

圖G的不同的連通分支構成一個關于集合V的劃分,即。①對于任意v

V，[v]G≠

。②[a]G≠[b]G則[a]G∩[b]G=

。③。證明因為v

[v]G，所以①成立。②：假定[a]G∩[b]G≠

，則需證明[a]G=[b]G。令x

[a]G∩[b]G，則結點x與結點a和b都連通，則在a和b之間存在著一條G的路，則b

[a]G，這意味著

[b]G

[a]G。同樣的方法證明[a]G

[b]G

。即[a]G=[b]G。7-2路與回路③的正確性是由于：7-2路與回路圖G=〈V，E〉可以分解為若干個連通分支Gi=〈Vi，Ei〉(i=1，2，…，k)，G的連通分支數(shù)用W(G)來表示。在連通分支中兩個存在著通路[u，v]的結點u和v之間定義它們的距離。用l[u，v]表示從結點u到v之間存在某一條路的長度，結點u和v之間的距離用d(u，v)來表示，并d(u,v)=minl[u，v]。結點u和v之間的距離是從u到v的最短跡的長度。7-2路與回路對于距離有如下明顯的結果：①d(u，u)=0，若u≠v，則d(u，v)＞0。②d(u，v)=d(v，u)。③d(u，v)+d(v，w)≥d(u，w)。因此在連通分支上的結點的距離是可測的。7-2路與回路[定義]

令G=〈V,E〉為任意圖，如果對于任意(u，v)

E，皆有(v，u)

E，則G稱為是對稱的。任何一個無向圖都是對稱的。對稱的有向圖，相鄰的兩個結點，必然存在著兩條方向相反的連結它們的邊。因此，任何一個對稱的有向圖，可以用一個無向圖來表示，相反，任何一個無向圖都可以將它變換成對稱的有向圖。7-2路與回路[定義7-2.3]連通圖若圖G只有一個連通分支，則稱G是連通圖。有一個平凡的結論：連通圖G=〈V，E〉中，任意兩個結點之間必是連通的。7-2路與回路[定義]設無向圖G=〈V,E〉為連通的，若對于圖G中的兩個結點x，y的任何通路，皆通過結點v

（x和y除外），則稱結點v為結點x，y的關節(jié)點。換言之，∩{[x，y]}

={v}。這樣在圖中連通的兩個結點，當刪除它們的關節(jié)點后，它們將不連通。7-2路與回路定義7-2.4點割集和割點設無向圖G=〈V,E〉為連通的，若有結點集V1

V，使得圖G刪除了V1所有結點后，所得的子圖是不連通的，而刪除了V1的任意真子集后，所得的子圖仍然是連通圖。則稱集合V1為圖G的點割集。若某一結點就構成點割集，則稱該結點為割點。這樣，一個連通圖，將刪除它的一個點割集后，將分成兩個或多于兩個連通分支。7-2路與回路若G不是完全圖，我們定義k(G)=min{|V1||V1是G的點割集}為G的點連通度(或連通度)。連通度k(G)是為了產生一個不連通圖需要刪去的點的最少數(shù)目。于是，一個不連通圖的連通度等于0，存在著割點的連通圖的連通度為1。完全圖Kp中刪去任何m個(m＜p-1)點后仍然連通，但是刪去了p-1個結點后產生一個平凡圖，故k(Kp

)=p-1。7-2路與回路[定義7-2.5]邊割集、割邊設無向圖G=〈V,E〉為連通的，若有邊集E1

E，使得圖G刪除了E1所有邊后，所得的子圖是不連通的，而刪除了E1的任意真子集后，所得的子圖仍然是連通圖。則稱集合E1為圖G的邊割集。若某一邊構成邊割集，則稱該邊為割邊(或橋)。7-2路與回路G的割邊也就是G中的一條邊e使得W(G-e)＞W(wǎng)(G)。與點連通度相似，我們定義非平凡圖G的邊連通度為：λ(G)=min{|E1||E1是G的邊割集}，邊連通度λ(G)是為了產生一個不連通圖需要刪去邊的最少數(shù)目。對于平凡圖λ(G)=0，此外一個不連通圖也有λ(G)=0。7-2路與回路定理7-2.2

對于任何一個圖G=〈V,E〉，有k(G)≤λ(G)≤δ(G)證明若G不連通，則k(G)=λ(G)=0，故上式成立。若G連通，①證明λ(G)≤δ(G)。若G是平凡圖，則λ(G)=0≤δ(G)，若G是非平凡圖，則因每一結點的所有關聯(lián)邊構成一個邊割集，故λ(G)≤δ(G)。②再證k(G)≤λ(G)設λ(G)=1，即G有一割邊，顯然此時k(G)=1，上式成立。7-2路與回路(b)設λ(G)≥2，則必可刪去某λ(G)條邊，使G不連通。而刪除λ(G)-1條邊，它仍然連通，而且有一條橋e=(u，v)。對λ(G)-1條邊中的每一條邊都選取不同于u，v的端點，將這些端點刪去必至少刪去λ(G)-1條邊。若這樣產生的圖是不連通的，則k(G)≤λ(G)-1≤λ(G)，若這樣產生的圖是連通的，則e=(u，v)仍然是橋，此時再刪去u，v，就必產生一個不連通圖，故k(G)≤λ(G)。由此得k(G)≤λ(G)≤δ(G)。7-2路與回路[定理7-2.3]一個連通無向圖G=〈V,E〉的某一點v是圖G的割點的充分必要條件是存在兩個結點u和w，使得u和w的每一條路都通過v。證明

必要性：若結點v是G的割點，則刪去它后，必然有兩個以上的連通分支。u和w分別在不同的連通分支上取，顯然v是結點u，w的關節(jié)點。充分性：若v是結點u，w的關節(jié)點，則u到w的每一條路都通過v，刪除v后u到w已不連通，故v是圖G的割點。7-2路與回路無向圖的連通性不能直接推廣到有向圖。在有向圖G=〈V,E〉中，從結點u到v有一條路，稱為從u可達v?？蛇_性是有向圖的二元關系，它是自反的和傳遞的，但一般來說它不是對稱的。關于有向圖的結點的距離與無向圖類似定義，它有：①d(u，u)=0，若u≠v，則d(u，v)＞0。②d(u，v)+d(v，w)≥d(u，w)。從u不可達v，則通常寫成d(u，v)=

但是若從u可達v而且從v可達u時，以下的等式d(u，v)=d(v，u)不一定成立。今后我們將稱作圖G的直徑。7-2路與回路[定義7-2.6]強連通、單側連通、弱連通簡單有向圖G=〈V,E〉中，任意一對結點間，至少有一個結點到另一個結點是可達的，則稱這個圖為單側連通。如果對于圖G中的任意兩個結點兩者之間是互相可達的，則稱這個圖為強連通的。如果在圖G中略去方向，將它看成是無向圖，圖是連通的，則稱該有向圖為弱連通的。7-2路與回路從前面的定義可以看出，強連通圖必是單側連通的，單側連通必是弱連通的。它們的逆命題都不真。7-2路與回路[定理7-2.7]

一個有向圖是強連通的，當且僅當G中有一個回路，它至少包含每個結點一次。證明充分性：如果圖中有一條回路，它至少包含每個結點一次，則G中任意兩個結點都是相互可達的，故G是強連通的。必要性：若有向圖G是強連通的，則任意兩個結點都是可達的故必可作一回路經(jīng)過圖中的所有各點。若不然則必有一回路不包含某一結點v，因此，v與回路上的各結點就不是相互可達的了，與強連通的條件矛盾。7-2路與回路[定義7-2.7]設在簡單有向圖中，具有強連通性質的最大子圖，稱為強分圖；具有單側連通性質的最大子圖，稱為單側分圖；具有弱連通性質的最大子圖，稱為弱分圖。7-2路與回路[定理7-2.5]

在有向圖G=〈V,E〉中，它的每一個結點位于且僅位于一個強分圖內。證明⑴設v

V，令S是G中所有與v相互可達的結點的集合，當然S也包括v，而S是G中的一個強分圖，因此G中的每一個結點必位于一個強分圖中。7-2路與回路⑵設v位于兩個不同的強分圖S1和S2中，因為S1中的每一個結點與v可達，而v與S2中的每一個結點也相互可達，S1中的每一個結點與S2中的每一個結點通過v都相互可達，這與題設S1為強分圖矛盾，故G的每一個結點只能位于一個強分圖中。7-2路與回路7-3圖的矩陣表示矩陣是研究圖的一種有力工具，特別是利用計算機來處理有關圖的算法時，首先遇到的難題是如何識別圖？在前面我們也用有向圖來表示集合A中元素的關系R，這種圖被稱為關系圖，表示了集合A中元素的鄰接關系，只要將集合A中的元素進行編號，這樣的鄰接關系同樣可以用矩陣表示。識別一個圖等價于識別一個矩陣。我們要討論前面的有關圖的概念，如何在矩陣中表達出來。我們討論的是簡單圖，并令圖的結點已經(jīng)編號。[定義7-3.1]鄰接矩陣設G=〈V，E〉為簡單圖，它有n個結點V={v1,v2,…vn}，，則n階方陣A(G)=(aij)稱為G的鄰接矩陣。其中adj表示鄰接，nadj表示不鄰接。7-3圖的矩陣表示圖7-3.17-3圖的矩陣表示例如圖7-3.1(a)的鄰接矩陣為：7-3圖的矩陣表示當給定的簡單圖是無向圖時，鄰接矩陣為對稱的，當給定的圖是有向圖時，鄰接矩陣不一定對稱。圖G的鄰接矩陣顯然與結點標定的次序有關，例如在圖7-3.1的兩個圖(b)與圖(c)中的結點v1和v2的次序對調,那么新的鄰接矩陣由原來的鄰接矩陣的第一行和第二行對調,第一列和第二列對調而得到。7-3圖的矩陣表示圖7-3.1圖的鄰接矩陣及置換7-3圖的矩陣表示一般地說，我們把一個n階方陣A的某些列作一置換，再把相應的行作同樣的置換，得到一個新的n階方陣A’，我們稱A和A’為置換等價。有向圖的結點，按不同次序所寫出來的鄰接矩陣是彼此置換等價的，今后我們略去這種元素次序的任意性，可取任何一個鄰接矩陣作為該圖的矩陣表示。7-3圖的矩陣表示從鄰接矩陣A中表示了圖的基本概念和許多圖的性質:第i行的元素是由結點vi出發(fā)的邊所決定的，第i行第j列為1的的元素，表示了在vi和vj之間有邊相連，即存在(vi，vj)；第i行中值為1的元素的數(shù)目等于從vi出發(fā)的出度；第j列中值為1的元素的數(shù)目等于從vj進入的入度。如果給定的圖是零圖，則其對應的矩陣中所有的元素都為零，它是一個零矩陣，反之亦然，即鄰接矩陣為零矩陣的圖必是零圖。7-3圖的矩陣表示用圖形表示圖的方法，關于結點間的通路很容易在圖形中看出來，但在鄰接矩陣中就需經(jīng)過計算，不過，可以在計算機中處理。設有向圖G的結點集V={v1,v2,…vn}，它的鄰接矩陣為：A(G)=(aij)n×n，現(xiàn)在我們來計算從結點vi到結點vj的長度為2的路的數(shù)目。注意到每條從結點vi到結點vj的長度為2的路的中間必經(jīng)過一個結點vk，即vi→vk→vj(1≤k≤n)，如果圖中有路vivkvj存在，那么aik=akj=1，即aik·akj=1，反之如果圖G中不存在路vivkvj，那么aik=0或akj=0，即aik·akj=0，于是從結點vi到結點vj的長度為2的路的數(shù)目等于：7-3圖的矩陣表示按照矩陣的乘法規(guī)則，這恰好是矩陣中的第i行，第j列的元素。7-3圖的矩陣表示

表示從結點vi到結點vj的長度為2的路的數(shù)目。表示從結點vi到結點vi的長度為2的回路的數(shù)目。從結點vi到結點vj的一條長度為3的路，可以看作從結點vi到結點vk的長度為1的路，在聯(lián)結從結點vk到結點vj的長度為2的路，故從結點vi到結點vj的一條長度為3的路的數(shù)目：7-3圖的矩陣表示即。一般地有7-3圖的矩陣表示上述這個結論對無向圖也成立。[定理7-3.1]

設A(G)為圖G的鄰接矩陣，則(A(G))l中的i行j列元素等于G中聯(lián)結vi與vj的長度為l的路的數(shù)目。證明對l施歸納法當l=2時，由上得知是顯然成立。設命題對l成立，由故根據(jù)鄰接矩陣的定義aik表示聯(lián)結vi與vk長度為1的路的數(shù)目，而是聯(lián)結vk與vj長度為l的路的數(shù)目，上式的每一項表示由vi經(jīng)過一條邊到vk，再由vk經(jīng)過長度為l的路到vj的，總長度為l+1的路的數(shù)目。對所有的k求和，即是所有從vi到v的長度為l+1的路的數(shù)目，故命題對l+1成立。7-3圖的矩陣表示從上面的矩陣中我們可以看到一些結論，如v1與v2之間有兩條長度為3的路，結點v1與v3之間有一條長度為2的路，在結點v2有四條長度為4的回路。在許多問題中需要判斷有向圖的一個結點vi到另一個結點vj是否存在路的問題。如果利用圖G的鄰接矩陣A，則可計算A，A2，A3，…，An，…，當發(fā)現(xiàn)其中的某個Al的≥1，就表明結點vi到vj可達。但這種計算比較繁瑣，且Al不知計算到何時為止。從前面我們得知，如果有向圖G有n個結點V={v1,v2,…vn}，vi到vj有一條路，則必有一條長度不超過n的通路，因此只要考察就可以了，其中(1≤l≤n)。對于有向圖G中任意兩個結點之間的可達性，亦可用可達矩陣(P291定義7-3.2)表達。7-3圖的矩陣表示例：7-3圖的矩陣表示圖的距離矩陣DD的說明：(a)D中“1”均是A1中的非零元素；

D中“2”均是A2中的非零元素，且不是A1中的非零元素；

D中“3”均是A3中的非零元素，且不是A2、A1中的非零元素；(b)在D中主對角線為“0”是規(guī)定的，∵i→j的距離為“0”。(c)若i≠j，且i到j不存在路徑，則按定義d（i,j）=∞。7-3圖的矩陣表示[定義7-3.2]可達性矩陣令G=〈V，E〉是一個簡單有向圖，|V|=n，假定G的結點已編序，即V={v1,v2,…vn}，定義一個n×n矩陣。其中

稱矩陣P是圖G的可達性矩陣。7-3圖的矩陣表示可達性矩陣表明了圖中任意兩個結點間是否至少存在一條路以及在任何結點上是否存在回路。一般地講可由圖G的鄰接矩陣A得到可達性矩陣P。即令Bn=A+A2+…+An，在從Bn中將不為0的元素改為1，而為零的元素不變，這樣改換的矩陣即為可達性矩陣P。7-3圖的矩陣表示[定義7-3.3]完全關聯(lián)矩陣給定無向圖G，令v1,v2,…,vp和e1,e2,…,eq分別記為G的結點和邊，則矩陣M(G)=(mij)，其中

稱M(G)為完全關聯(lián)矩陣。7-3圖的矩陣表示⑴圖中每一邊關聯(lián)兩個結點，故M(G)的每一列只有兩個1。⑵每一行元素的和數(shù)對應于結點的度數(shù)。⑶一行中的元素全為0，其對應的結點為孤立點。⑷兩個平行邊其對應的兩列相同。⑸同一圖當結點或邊的編序不同，其對應M(G)僅有行序、列序的差別。7-3圖的矩陣表示當一個圖是有向圖時，亦可用結點和邊的關聯(lián)矩陣來表示。定義7-3.4

給定簡單有向圖G=〈V，E〉，V={v1,v2,…vp}，E={e1,e2,…eq}，p×q階矩陣M(G)=(mij)，其中

稱M(G)為G的關聯(lián)矩陣。7-3圖的矩陣表示一、歐拉圖主要內容：1、歐拉圖的定義2、歐拉圖的判定3、建模：歐拉圖應用重點：歐拉圖判定定理7-4歐拉圖與哈密爾頓圖7-4歐拉圖與哈密爾頓圖1736年瑞士數(shù)學家列昂哈德·歐拉(leonhardEuler)發(fā)表了圖論的第一篇論文“哥尼斯堡七橋問題”。這個問題是這樣的：哥尼斯堡(Konigsberg)城市有一條橫貫全城的普雷格爾(Pregel)河，城的各部分用七座橋連接，每逢假日，城中的居民進行環(huán)城的逛游，這樣就產生一個問題，能不能設計一次“逛游”，使得從某地出發(fā)對每座跨河橋走一次，而在遍歷了七橋之后卻又能回到原地。7-4歐拉圖與哈密爾頓圖LeonhardEuler(1707~1783):人類有史以來最多產的數(shù)學家.1736年,“七橋問題”,圖論和拓撲學誕生ADcdabfCgBe7-4歐拉圖與哈密爾頓圖圖7-4.2為七橋問題的圖。圖中的結點A，B，C，D表示四塊地，而邊表示七座橋。哥尼斯堡七橋問題是在圖中找尋經(jīng)過每一條邊且僅一次而回到原地的路。ADcdabfCgBe7-4歐拉圖與哈密爾頓圖歐拉在1736年的一篇論文中提出了一條簡單的準則，確定了哥尼斯堡七橋問題是不能解的。下面將討論這個問題的證明。[定義]歐拉回路給定無孤立結點圖G，若存在一條路，經(jīng)過圖中每邊一次且僅一次，該條路稱為歐拉路；若存在一條回路，經(jīng)過圖中的每邊一次且僅一次，該回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖7-4歐拉圖與哈密爾頓圖[定理7-4.1]

無向圖G具有一條歐拉路，當且僅當G是連通的，且有零個或兩個奇數(shù)度結點。證明必要性:

設G具有歐拉路，即有點邊序列v0e1v1e2v2…eiviei+1…ekvk，其中結點可能重復出現(xiàn)，但邊不重復，因為歐拉路經(jīng)過圖G中每一個結點，故圖G必連通的。對任意一個不是端點的結點vi，在一個歐拉路中每當vi出現(xiàn)一次，必關聯(lián)兩條邊，故雖然vi可重復出現(xiàn)，但deg(vi)必是偶數(shù)。對于端點，若v0=vk，則deg(v0)為偶數(shù)，即G中無奇數(shù)度結點，若端點v0與vk不同，則deg(v0)為奇數(shù)，deg(vk

)為奇數(shù)，G中就有兩個奇數(shù)度結點。7-4歐拉圖與哈密爾頓圖充分性:

若圖G連通，有零個或兩個奇數(shù)度結點，我們構造一條歐拉路如下：⑴若有兩個奇數(shù)度結點，則從其中的一個結點開始構造一條跡，即從v0出發(fā)關聯(lián)e1“進入”v1，若deg(v1)為偶數(shù)，則必由v1再經(jīng)過e2進入v2，如此進行下去，每邊僅取一次。由于G是連通的，故必可到達另一奇數(shù)度結點停下，得到一條跡L1：v0e1v1e2v2…eiviei+1…ekvk。若G中沒有奇數(shù)度結點，則從任一結點v0出發(fā)，用上述的方法必可回到結點v0，得到上述一條閉跡L1。⑵若L1通過了G的所有邊，則L1就是歐拉路。7-4歐拉圖與哈密爾頓圖⑶若G中去掉L1后得到子圖G’，則G’中每一點的度數(shù)為偶數(shù)。因原圖是連通的，故L1與G’至少有一個結點vi重合，在G’中由vi出發(fā)重復⑴的方法，得到閉跡L2。⑷當L1與L2組合在一起，如果恰是G，則即得歐拉路，否則重復⑶可得到閉跡L3，以此類推直到得到一條經(jīng)過圖G中所有邊的歐拉路。7-4歐拉圖與哈密爾頓圖v0構造法7-4歐拉圖與哈密爾頓圖推論無向圖G具有一條歐拉回路，當且僅當G是連通的，并且所有結點度數(shù)為偶數(shù)。由于有了歐拉路和歐拉回路的判別準則，因此哥尼斯堡七橋問題立即有了確切的答案，因為有四個結點的度數(shù)皆為奇數(shù)，故歐拉路必不存在。7-4歐拉圖與哈密爾頓圖歐拉圖的判定

(a)(b)上述2圖是否為歐拉圖？v1v2v3v4v5v1v2v3v4v5請你思考？G1G27-4歐拉圖與哈密爾頓圖歐拉路和歐拉回路的概念，很容易推廣到有向圖上去。[定義7-4.2]

給定有向圖G，通過每邊一次且僅一次的一條單向路(回路)，稱作單向歐拉路(回路)。7-4歐拉圖與哈密爾頓圖[定理7-4.2]有向圖G具有一條單向歐拉回路，當且僅當是連通的，且每個結點的入度等于出度。一個有向圖G具有單向歐拉路，當且僅當是連通的，而且除兩個結點外，每個結點的入度等于出度，但這兩個結點中，一個結點的入度比出度大1。另一個結點的入度比出度小1。7-4歐拉圖與哈密爾頓圖二、漢密爾頓圖

主要內容：1、哈密爾頓圖2、哈密爾頓圖判定定理3、建模：哈密爾頓圖應用重點難點：哈密爾頓圖判定定理7-4歐拉圖與哈密爾頓圖漢密爾頓回路與歐拉回路非常類似的問題是漢密爾頓回路問題。1859年愛爾蘭數(shù)學家威廉·漢密爾頓爵士在給他的朋友的一封信中，首先談到關于十二面體的一個數(shù)學游戲：一個木刻的正十二面體，每面系正五角形，三面交于一角，共有20個角，每角標有世界上一個重要城市。漢密爾頓提出一個問題：要求沿正十二面體的邊尋找一條路通過20個城市，而每個城市只通過一次，最后返回原地。漢密爾頓將此問題稱為周游世界問題。7-4歐拉圖與哈密爾頓圖7-4歐拉圖與哈密爾頓圖[定義7-4.3]漢密爾頓路，漢密爾頓回路給定圖G，若存在一條路經(jīng)過圖中的每一個結點恰好一次，這條路稱作漢密爾頓路。若存在一條回路，經(jīng)過圖中的每一個結點恰好一次，這個回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱為漢密爾頓圖。7-4歐拉圖與哈密爾頓圖[定理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是連通非回路，若刪去S中的另一個結點a2，則W(C－a1－a2)≤2，由歸納法得知

W(C－S)≤|S|同時C－S是G－S的一個生成子圖，因而

W(G－S)≤W(C－S)所以W(G－S)≤|S|7-4歐拉圖與哈密爾頓圖利用該定理可以證明某些圖是非漢密爾頓圖。（a）(b)(c)7-4歐拉圖與哈密爾頓圖這個方并不是總是有效的。例如，著名的彼得森(Pertersen)圖，如下圖所示，在圖中刪去任一個結點或任意兩個結點，不能使它不連通；刪去三個結點，最多只能得到有兩個連通分支的子圖；刪去四個結點，最多只能得到有三個連通分支的子圖；刪去五個或五個以上的結點，余下的結點數(shù)都不大于5，故必不能有5個以上的連通分支數(shù)。所以該圖滿足W(C－S)≤|S|，但是可以證明它非漢密爾頓圖。7-4歐拉圖與哈密爾頓圖雖然漢密爾頓回路問題和歐拉回路問題在形式上極為相似，但對圖G是否存在漢密爾頓回路還無充要的判別準則。下面我們給出一個無向圖具有漢密爾頓路的充分條件。7-4歐拉圖與哈密爾頓圖[定理7-4.4]

無向圖具有漢密爾頓路的充分條件設G具有n個結點的簡單圖，如果G中每一對結點的度數(shù)之和大于等于n-1，則在G中存在一條漢密爾頓路。證明

首先，證明G是連通的?

若G有兩個或更多互不連通的分圖，設一個分圖有n1個結點，任取一個結點v1，設另一個分圖有n2個結點，任取一個結點v2，由

d(v1)≤n1－1，d(v2)≤n2－1，有

d(v1)+d(v2)≤n1+n2－2＜n－1，這表明與題設矛盾，故G必連通。7-4歐拉圖與哈密爾頓圖其次，證明G有漢密爾頓通路？

只要在G中構作出一條長為n－1的H-通路即可得證。為此，不妨令P為G中任意一條長為p－1(p＜n)的H-通路，設其結點序列為v1，v2，…，vp。反復應用下面方法來擴充這一通路，直到P長度為n-1：

1）如果有v

v1，v2，…，vp，它與v1或vp有邊相關聯(lián)，那么可立即擴充P為長度為p的通路。

2）如果v1，vp均只與原通路P上的結點相鄰，則首先證明：G中有一條包含v1，v2，…，vp，長度為p的回路。

2.1)

如果v1與vp相鄰，則回路已找到。否則7-4歐拉圖與哈密爾頓圖

2.2)

如果v1與vi1,vi2,…,vir相鄰，1＜i1，i2,…,ir＜p,考慮vp：若vp不與vi1-1,vi2-1,…,vir-1中任何一個相鄰，則deg(vp)≤p-r-l，因而deg(v1)+deg(vp)≤r+p–r–l=p–1＜n–1，與題設矛盾，因此vp與vi1-1,vi2-1,…,vir-1之一,例如vi1-1相鄰，于是,可得到包含v1，v2，…，vp的回路：（v1，v2，…，vi1-1,vp,vp-1,…，vi1,v1）如圖所示。v1vpv2vi-1vi7-4歐拉圖與哈密爾頓圖

考慮G中這條包含v1，v2，…，vp、長度為p的回路。由于p<n，故必有回路外結點v與回路上結點(例如vk)相鄰，如圖所示，可以得到一條長度為p的、包含v1，v2，…，vp的通路：(v,vk,vk-1,…,v1,vi1,vi1+1,…,vp,vi1-1,…,vk+1)。擴充這一通路，直到P長度為n-1v1vpv2vkvk+1vvi-1vi7-4歐拉圖與哈密爾頓圖容易看出，定理7-4.4的條件是圖中的漢密爾頓路的存在的充分條件，但是并不是必要的條件。設圖是n邊形，如下圖所示，其中n=6雖然任何兩個結點度數(shù)的和是4＜6－1，但在G中有一條漢密爾頓路。7-4歐拉圖與哈密爾頓圖[定理7-4.5]

無向圖具有漢密爾頓回路的充分條件設圖G是具有n個結點的簡單圖，如果G中每一對結點的度數(shù)大于等于n，則在G中存在一條漢密爾頓回路。證明由定理7-4.4可知必有一條漢密爾頓路，設為v1v2…vn，如果v1與vn鄰接，則定理得證。如果v1與vn不鄰接，假設v1鄰接，2≤ij≤n-1，可以證明vn必鄰接于中之一。如果不鄰接于中的任意一點，則vn至多鄰接于n-k-1個結點，因而d(vn)≤n－k－1，而d(v1)=k，故d(v1)+d(vn)≤n－k－1+k=n-1，與題設矛盾，所以必有漢密爾頓回路v1v2…vj-1vnvn-1…vjv1。7-4歐拉圖與哈密爾頓圖7-5平面圖在現(xiàn)實生活中，常常要畫一些圖形，希望邊與邊之間盡量減少相交的情況，例如印刷線路板的布線，交通道路的設計等。[定義7-5.1]平面圖設G＝〈V，E〉是一個無向圖，如果能夠把G的所有結點和邊畫在平面上，且使任何兩條邊除了端點外沒有其它的交點，就稱G是一個平面圖。應該注意，有些圖形從表面上看有幾條邊是相交的，但不能就此肯定它不是平面圖。例如圖7-5.1(a)，表面上看有幾條邊相交，但把它畫成圖7-5.1(b)，則可看出它是一個平面圖。7-5平面圖圖7-5.1改畫的平面圖7-5平面圖有些圖形不論怎樣改畫，除去結點外，總有邊相交。如有三間房子A1、A2、A3，擬分別連接水、煤氣和電三個接口，如圖7-5.2(a)所示，這個圖不論怎樣改畫，改畫后至少有一條邊與其它邊在結點以外的地方相交，如圖7-5.2(b)所示，故它不是一個平面圖。7-5平面圖圖7-5.2不是平面圖7-5平面圖[定義7-5.2]圖G的面和邊界

設G是一個連通平面圖，由圖中的邊所包圍的區(qū)域，在區(qū)域內既不包含圖的結點，也不包含圖的邊，這樣的區(qū)域稱為圖G的一個面，包圍該面的諸邊所構成的回路稱為這個面的邊界。7-5平面圖圖7-5.3

面及其邊界

7-5平面圖例如圖7-5.3，具有六個結點九條邊，它把平面分成五個面。其中r1、r2、r3、r4四個面是由回路構成邊界，如由回路BADB所圍，r3可看成從C點開始圍繞r3按反時針走，得到回路CDEFEC所圍。另外還有一個面r5在圖形之外，不受邊界約束，稱作無限面。如果我們把圖形看作包含在比整個平面還要大的一個矩形之內，那么在計算圖形面的數(shù)目時，就不會遺漏無限面了。今后我們把面的邊界的回路長度稱作該面的次數(shù)，記為deg(r)，在圖7-5.3中deg(r1)＝3，deg(r2)＝3，deg(r3)＝5，deg(r4)＝4，deg(r5)＝3。7-5平面圖定理7-5.1一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。證明因為任何一條邊，或者是兩個面的公共邊，或者在一個面中作為邊界被重復計算兩次，故面的次數(shù)之和等于其邊數(shù)的兩倍。如圖7-5.3中＝18，正好是邊數(shù)9的兩倍。7-5平面圖在三維空間中，關于凸多面體有一個著名的歐拉定理，設凸多面體有v個頂點e條棱r塊面，則v-e+r＝2。我們可以將這個定理推廣到平面圖上。7-5平面圖[定理7-5.2](歐拉定理)（平面圖的必要條件，用于判定某個圖不是平面圖）設有一個連通平面圖G，共有v個結點e條邊r塊面，則歐拉公式v-e+r＝2成立。證明⑴若G為一個孤立結點，則v＝1，e＝0，r＝1，故v-e+r＝2成立。⑵若G為一條邊，則v＝2，e＝1，r＝1，則v-e+r＝2成立。⑶設G為k條邊時，歐拉公式成立。即vk–ek+rk＝2。下面考察G為k+1條邊時的情況。7-5平面圖圖7-5.4

歐拉定理證明的示意圖7-5平面圖因為在k條邊的連通圖上增加一條邊，使它仍為連通圖，只有下述兩種情況：①加上一個新的結點Q2，Q2與圖上的一點Q1相連(如圖7-5.4(a)所示)，此時，vk和ek兩者都增加1，而面數(shù)rk未變，故

(vk+1)-(ek+1)+rk＝vk-ek+rk＝2②用一條邊連接圖上的已知點Q1和Q2,如圖7-5.4(b)所示，此時ek和rk都增加1，而結點數(shù)未變，故vk-(ek+1)+(rk+1)＝vk-ek+rk＝27-5平面圖[定理7-5.3]

設G為有v個結點e條邊的連通平面圖，若v≥3，則e≤3v-6。證明設連通平面圖G的面數(shù)為r，當v＝3，e＝2時上式顯然成立，除此之外，若e≥3，則每一個面的次數(shù)不小于3，由定理1得知各面次數(shù)之和為2e，因此代入歐拉定理：

6≤3v-ee≤3v-6應用此定理可以判定某些圖不是平面圖。7-5平面圖例1設圖G如圖7-5.5所示，該圖是K5圖。因為有5結點10條邊，故3×5－6＜10，即e≤3v-6對本圖不成立，故K5是非平面圖。圖7-5.5K5圖需要注意定理7-5.3的條件并不是充分的，如圖7-5.2所示的圖，常稱作K3,3圖，由于有6個結點9條邊，故3×6－6≥9，即滿足e≤3v-6，但可以證明K3,3也是非平面圖。7-5平面圖例2

證明K3,3圖不是平面圖。如果K3,3是平面圖，因為在K3,3中任意取三個結點，其中必有兩個結點不鄰接，故每個面的次數(shù)都不小于4，由于，即圖中有6個結點9條邊，故2×6－4＜9，即不是平面圖。7-5平面圖如前面所講，有些圖形看來有邊相交，但可以改畫為平面圖，有些圖不論怎樣改畫，總會有邊相交的。如果圖的結點數(shù)和邊數(shù)較多，改畫起來比較麻煩，能否根據(jù)圖所包含的子圖來判定原圖是否是平面圖？雖然歐拉公式有時能用來判定某一個圖是非平面圖，但是還沒有簡便的方法可以確定某個圖是平面圖。下面介紹庫拉托夫斯基定理。7-5平面圖我們可以看到在給定的圖G的邊上，插入一個新的度數(shù)為2的結點，使一條邊分成兩條邊，或者對于關聯(lián)于一個度數(shù)為2的結點的兩條邊，去掉這個結點，使兩條邊化為一條邊，這樣不會影響圖的平面性，如圖7-5.6(a)和(b)。圖7-5.6

7-5平面圖[定義7-5.4]圖是在2度結點內同構給定兩個圖G1和G2，如果它們是同構的，或通過反復插入或刪去度數(shù)為2的結點后，使G1和G2同構，則稱該圖是在2度結點內同構。[定理7-5.4](Kuratowski庫拉托夫斯基定理)

一個平面圖，當且僅當它不包含與K3,3或K5在2度結點內同構的子圖。7-5平面圖庫拉托夫斯基圖(Kuratowskigraph)K3,3K57-5平面圖K3,3和K5(如圖7-5.7所示)常稱為庫拉托夫斯基圖，這個定理雖然很基本，但證明較長，故從略。7-5平面圖7-6對偶圖與著色與平面圖有密切關系的一個圖的應用是圖形的著色問題，這個問題最早起源于地圖的著色，一個地圖的相鄰的兩個國家著于不同的顏色，那么最少需用多少種顏色？一百多年前，英國格色里(Guthrie)提出了用四種顏色即可對地圖著色的猜想，1879年肯普(Kempe)提出了這個猜想的第一個證明，但到1890年希伍德(Hewood)發(fā)現(xiàn)肯普的證明是錯誤的，但他指出肯普的方法，雖不能證明地圖著色用四種顏色就夠了，但可證明用五種顏色就夠了。此后四色猜想一直成為數(shù)學家感興趣而未能解決的難題。直到1976年美國數(shù)學家阿佩爾和黑肯宣布：他們用電子計算機證明了四色猜想是成立的。所以從1976年以后就把四色猜想這個名詞改為“四色定理”了。為了敘述圖形著色的有關定理，下面先介紹對偶圖的概念。[定義7-6.1]對偶圖給定平面圖G＝〈V，E〉，它有面F1，F(xiàn)2，…，F(xiàn)n，若有圖G*＝〈V*，E*〉滿足下述條件：⑴對于圖G的任一個面Fi，內部有且僅有一個結點vi*∈V*。⑵對于圖G的面Fi，F(xiàn)j的公共邊ek，存在且僅存在一條邊ek*∈E*，使ek*＝(vi*，vj*)，且ek*和ek相交。⑶當且僅當ek只是一個面Fi的邊界時，vi*存在一個環(huán)ek*和ek相交，則圖G*是圖G的對偶圖。根據(jù)一個圖得到它的對偶圖實際上是將該圖的結點改變成為對偶圖的面，該圖的面改變?yōu)閷ε紙D的結點。7-6對偶圖與著色從這個定義看出，G*是G的對偶圖，則G也是G*的對偶圖。一個連通平面圖的對偶圖也必是平面圖。[定義7-6.2]自對偶圖如果圖G的對偶圖G*同構于G，則稱G是自對偶的。從對偶圖的概念，我們可以看到，對于地圖的著色問題，可以歸納為對于平面圖的結點著色問題，因此四色問題可以歸結為要證明對于任何一個平面圖，一定可以用四種顏色對它的結點進行著色，使得鄰接的結點都有不同的顏色。7-6對偶圖與著色圖G的正常著色(或簡稱為著色)是指對它的每一個結點指定一種顏色，使得沒有兩個相鄰的結點有同一種顏色。如果圖G在著色時用n種顏色，我們稱G為n-色的。對于圖G著色時，需最少顏色數(shù)稱為著色數(shù)，記作x(G)。雖然到現(xiàn)在還沒有一個簡單通用的方法，可以確定任一圖G是否是n-色的。但我們可用韋爾奇·鮑威爾法(WelchPowell)對圖G進行著色，其方法是：7-6對偶圖與著色⑴將圖G的結點按照度數(shù)的遞減次序進行排列。(這種排列可能并不是唯一的，因為有些點有相同的度數(shù))。⑵用第一種顏色對第一點進行著色，并且按排列次序，對前面著色點不鄰接的每一點著上同樣的顏色。⑶用第二種顏色對尚未著色的點重復⑵，用第三種顏色繼續(xù)這種做法，直到所有的點全部著上色為止。7-6對偶圖與著色例1

用韋爾奇·鮑威爾法對圖7-6.1著色。圖7-6.1解⑴根據(jù)遞減次序排列各點A5，A3，A7，A1，A2，A4，A6，A8。7-6對偶圖與著色⑵第一種顏色對A5著色，并對不相鄰的結點A1也著第一種顏色。⑶對A3結點和它不相鄰的結點A4，A8著第二種顏色。⑷對A7結點和它不相鄰的結點A2，A6著第三種顏色。因此圖G是三色的。注意圖G不可能是二色的，因為A1，A2，A3相互鄰接，故必須用三種顏色。所以x(G)＝3。7-6對偶圖與著色定理7-6.1

對于n個結點的完全圖Kn，有x(Kn)＝n。證明因為完全圖每一個結點與其它各結點都相鄰接，故n個結點的著色數(shù)不能少于n，又n個結點的著色數(shù)至多為n，故有x(Kn)＝n。定理7-6.2

設G為至少有三個結點的連通平面圖，則G中必有一個結點u，使得deg(u)≤5。證明設G＝〈V，E〉，若G的每一個結點u，都有deg(u)≥6，但因故2e≥6v，所以e≥3v＞3v－6，與定理7-5.3矛盾。定理7-6.3任意平面圖G最多是5-色的。7-6對偶圖與著色7-7樹與生成樹樹是圖論中最主要的概念之一，而且是最簡單的圖之一。它在計算機科學中應用非常廣泛。我們從一個問題談起，下圖是通訊線路圖(圖7-7.1)。圖7-7.1通訊線路圖其中v1，v2,…,v10是十個城市，線路只能在這里相接。不難發(fā)現(xiàn)，只要破壞了幾條線路，立即使這個通訊系統(tǒng)分解成不相連的兩部分。但要問在什么情況下這十個城市依然保持相通？不難知道，至少要有九條線把這十個城市連接在一起，顯然這九條線是不存在任何回路的，因而九條線少一條就會使系統(tǒng)失去連通性。7-7樹與生成樹[定義7-7.1]樹、森林一個連通且無回路的無向圖稱為樹。在樹中度數(shù)為1的結點稱為樹葉，度數(shù)大于1的結點稱為分枝點或內點。如果一個無回路的無向圖的每一個連通分圖是樹，稱為森林。7-7樹與生成樹定理7-7.1

給定圖T，以下關于樹的定義是等價的：⑴無回路的連通圖；⑵無回路且e=v-1，其中e為邊數(shù)，v為結點數(shù)；⑶連通且e=v-1；⑷無回路且增加一條新邊，得到一個且僅一個回路；⑸連通且刪去任何一個邊后不連通；⑹每一對結點之間有一條且僅一條路。7-7樹與生成樹證明

⑴

⑵已知無回路的連通圖，證無回路，且e=v-1

數(shù)學歸納法設在圖T中，當v=2時，連通無向圖，T中的邊數(shù)e=1，因此e=v-1成立。設v=k-1時命題成立，當v=k時，因無回路且連通，故至少有一條邊其一個端點u的度數(shù)為1。設該邊為(u,w)，刪去結點u，便得到一個k-1個結點的連通無向圖T’，由歸納假設，圖T’的邊數(shù)e’=v’-1=(k-1)-1=k-2，于是再將結點u和關聯(lián)邊(u,w)加到圖T’中得到原圖T，此時圖T的邊數(shù)為e=e’+1=(k-2)+1=k-1，結點數(shù)v=v’+1=(k-1)+1=k，故e=v-1成立。7-7樹與生成樹⑵

⑶已知無回路，e=v-1，證連通若T不連通，并且有k(k≥2)個連通分支T1，T2，…，Tk，因為每個分圖是連通無回路，則我們可證：如Ti有vi個結點vi＜v時，Ti有vi-1條邊，而v=v1+v2+…+vke=(v1-1)+(v2-1)+…+(vk-1)=v-k但e=v-1，故k=1，這與假設G是不連通即k≥2相矛盾。7-7樹與生成樹⑶

⑷已知連通且e=v-1，證明無回路，但增加一條新邊，得到一個且僅有一個回路若T連通且有v-1條邊。當v=2時，e=v-1=1，故T必無回路。如增加一條邊得到且僅得到一個回路。設v=k-1時命題成立?？疾靨=k時的情況，因為T是連通的，e=v-1。故每個結點u有deg(u)≥1，可以證明至少有一結點u0，使deg(u0)=1，若不然，即所有結點u有deg(u)≥2，則2e≥2v，即e≥v與假設e=v-1矛盾。刪去u0及其關聯(lián)的