離散數(shù)學10圖的基本概念

第10章圖的基本概念如何找到物流運輸?shù)淖顑?yōu)路徑？如何找到最優(yōu)的網(wǎng)絡通信線路？如果你想周游全國所有城市，如何設計旅游線路？化學化合物分析：結(jié)構(gòu)是否相同？程序結(jié)構(gòu)度量：程序是否結(jié)構(gòu)相似？如何為考試分配教室，使得資源利用率最優(yōu)？如何安排工作流程而達到最高效率？如何設計為眾多的電視臺頻道分配最優(yōu)方案？如何設計通信編碼以提高信息傳輸效率？操作系統(tǒng)中,如何調(diào)度進程而使得系統(tǒng)效率最優(yōu)？如何設計集成電路線路布局而達到最優(yōu)效率？如何設計計算機鼓輪？七枚同重量硬幣與一枚較輕的偽幣，使用天平秤多少次就能找出偽幣？如何設計下棋程序？n-皇后問題最少用幾種顏色就能將世界地圖都著色？如何使箱子盡可能裝滿物體？一個船夫要把一只狼，一只羊和一棵白菜運過河。問題是當人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個。那么他怎樣才能把三者都運過河呢？研究主題旅行商問題：TSP問題中國郵路問題地圖著色問題：四色定理最短路徑問題網(wǎng)絡流匹配組合計數(shù)主要內(nèi)容

1)圖的基本術(shù)語；2)結(jié)點的度，子圖，完全圖；3)圖的連通性；4)圖的運算，圖的矩陣表示及其性質(zhì)；5)圖的同構(gòu)；6)

歐拉圖與哈密爾頓圖的性質(zhì)及其應用。

10.1圖論概述

圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載體，其突出的特點是直觀、形象。圖論，顧名思義是運用數(shù)學手段研究圖的性質(zhì)的理論，但這里的圖不是平面坐標系中的函數(shù)，而是由一些點和連接這些點的線組成的結(jié)構(gòu)。圖論是有許多應用的古老學科，也一直以來都是一個熱門學科，它已經(jīng)被廣泛應用于計算機科學、化學、運籌學、心理學等很多領域。10.2圖與圖模型例10.2

某學校共有10名教師，他們分別參加7個班級的討論課，每個班級可能同時需要多位教師參加，有的教師可能需要參加多個班級的討論，每個班級必須單獨開展討論課，則如何安排才使得所有班級在最短時間段內(nèi)完成討論課？討論課的情況如下（Vi為班級編號，數(shù)字1-10為教師編號）：V6V5V4V2V3V7V1V1={1，2，3}，V2={1，3，4，5}，V3={2，5，6，7}，V4={2，6，7}，V5={4，7，8，9}，V6={8，9，10}，V7={1，3，9，10}。10.2圖與圖模型V6V5V4V2V3V7V1頂點集V={V1,V2,V3,V4,V5,V6,V7}邊集E={<V1,V2>,<V1,V3>,<V1,V4>,<V1,V7>,<V2,V3>,<V2,V4>,<V2,V7>,<V3,V4>,<V3,V5>,<V4,V5>,<V5,V6>,<V5,V7>,<V6,V7>}圖G=(V,E)的階為7，圖的規(guī)模為1310.2圖與圖模型

定義10.1

圖G=(V,E)包括兩個集合：結(jié)點集V(G)

：非空的對象的集合,V={v1,v2,…,vn}；邊集E(G)

：有限的兩個對象構(gòu)成的V的無序?qū)?gòu)成的集合。E={e1,e2,…,em};其中，每一條邊都是集合V的二元子集，如邊ei={u，v}，常常簡記為uv或vu，其中u、v稱為邊uv的端點。10.2圖與圖模型

設V={v1，v2，v3，v4，v5},E=

則G=（V，E）是一個圖。圖(a).(b)分別給出了圖G的圖解方法。10.2圖與圖模型

節(jié)點集合V(G)的基數(shù)n表示圖G的階，邊集合E(G)的基數(shù)m表示圖G的規(guī)模，有時也將圖G記作(n,m)。 在圖G中，若邊集E(G)=Ф,則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖（Trivialgraph）。N7V6V5V4V2V3V7V110.2圖與圖模型

結(jié)點集為空集的圖為空圖（EmptyGraph），并將空圖記為。 階為有限的圖稱為有限圖(FiniteGraph)，否則稱為無限圖(InfiniteGraph)。10.2圖與圖模型:無向圖環(huán)loop-->非簡單圖deg(v2)=4邊e2關聯(lián)結(jié)點v1、v2結(jié)點平行邊/重邊多重圖孤立點懸掛邊懸掛點分離邊v3結(jié)點度為3,

deg(v3)=3v3v1v2e1e2(G)=4(G)=010.2圖與圖模型如果圖中存在某兩條邊的端點都相同，則稱該圖為多重圖(Multigraph)，該兩條邊稱為平行邊。如果一條邊關聯(lián)的兩個結(jié)點是相同的結(jié)點，則稱該邊為圈或自環(huán)(Loop)。不存在平行邊與圈的圖即稱為簡單圖(SimpleGraph)。

10.2圖與圖模型定義10.2

如果uv是圖G的邊，記為e，即uvE(G),則稱結(jié)點u和v鄰接(Adjacent),否則稱結(jié)點u與v非鄰接。與同一個結(jié)點關聯(lián)的兩條邊稱為鄰接邊。與結(jié)點v關聯(lián)的邊數(shù)稱為結(jié)點v的度，記作deg(v)。與結(jié)點v關聯(lián)的環(huán)對v的度數(shù)的貢獻要計算兩次。如果結(jié)點v的度為0，則稱之為孤立點(IsolatedVertex)。一度的結(jié)點稱為懸掛點（PendantVertex）。圖G的所有結(jié)點度數(shù)的最小度數(shù)稱為G的最小度，記作(G)，而所有結(jié)點度數(shù)的最大者稱為G的最大度，記作(G)。各結(jié)點的度均相同的圖稱為正則圖（RegularGraph）。各結(jié)點度均為k的正則圖稱為k-正則圖。

10.2圖與圖模型

定義10.3

如果圖的每條邊是二結(jié)點構(gòu)成的有序?qū)?，則該圖稱為有向圖(DirectedGraph)，上文所定義的圖都是無向圖(UndirectedGraph)。有向圖中邊uv與vu是兩條不同的邊，對于邊uv，稱u為始點，v為終點。

有向圖中，結(jié)點v的度分為入度，即與該結(jié)點相關聯(lián)并以該結(jié)點為終點的邊的數(shù)目，以及出度,即與該結(jié)點相關聯(lián)并以該結(jié)點為始點的邊的數(shù)目,分別記作deg+(v)，deg-(v)。

10.2圖與圖模型：有向圖邊e2(有向邊<v1,v2>)關聯(lián)結(jié)點v1、v2結(jié)點

(頂點)孤立點懸掛邊懸掛點分離邊v3結(jié)點度為3,出度為1,入度為2v3v1v2e1e210.2圖與圖模型v1v2e1e2v1v2e1e2無向圖有向圖10.2圖與圖模型

練習1

設G=(V,E)是一無向圖，V={v1,v2,…,v8}，E={(v1,v2),(v2,v3),(v3,v1),(v1,v5),(v5,v4),(v4,v3),(v7,v8)}

（1）畫出G的圖解；（2）指出與V3鄰接的結(jié)點，以及和V3關聯(lián)的邊；（3）指出與(v2,v3)鄰接的邊和與(v2,v3)關聯(lián)的結(jié)點；（4）該圖是否有孤立結(jié)點和孤立邊？（5）求出各結(jié)點的度數(shù)，并判斷是否是完全圖和正則圖？（6）該(n,m)圖中，n=？，m=？定理10.1（歐拉定理）在任何圖中，結(jié)點度的總和等于邊數(shù)的兩倍。該定理也被稱為握手定理，被認為圖論第一定理，可以用于證明圖的相關性質(zhì)。

推論10.1

在任意圖中，奇數(shù)度的結(jié)點個數(shù)為偶數(shù)。

V6V5V4V2V3V7V110.2圖與圖模型邊數(shù)=?結(jié)點度的總和=?例10.3

設G=<V;E>，|V|=n,|E|=m，證明：(G)≤2m/n≤(G)。

V6V5V4V2V3V7V110.2圖與圖模型(G)=？(G)=？每個頂點的平均度數(shù)=？例10.4

請證明：有向圖中，所有結(jié)點出度之和等于所有結(jié)點入度之和。10.2圖與圖模型所有結(jié)點出度之和=？所有結(jié)點入度之和=？10.2圖與圖模型

練習2

設G=(V,E)有12條邊，有6個度為3的結(jié)點，其余結(jié)點的度數(shù)均小于3，問G中至少有多少個結(jié)點？10.2圖與圖模型V1V5V3V4V2圖G圖G2V5V3V4V2V1G2為G的子圖。

10.2圖與圖模型

定義10.4

令圖G=（V，E），稱(V′,E′)為G的子圖（Subgraph），當

(1)VV且EE；

(2)對任意eE，則與e相關聯(lián)的結(jié)點u,vV。若G是G的子圖,則稱G是G的超圖/母圖，記作GG。 若GG且G≠G(即VV或EE)，則稱G是G的真子圖。 若GG且VV，則稱G是G的生成子圖（SpanningSubgraph）。 設V1V,且V1≠，以V1為結(jié)點集，以兩端點均在V1中的全體邊為邊集的G的子圖，稱為結(jié)點集V1導出的導出子圖（DerivedSubgraph）。 設E1E,且E1≠，以E1為邊集，以E1中邊關聯(lián)的結(jié)點的全體為結(jié)點集G的子圖，稱為邊集E1導出的導出子圖。

10.2圖與圖模型真

生成真

非生成真

非生成真

非生成10.2圖與圖模型顯然，子圖或?qū)С鲎訄D可以通過刪除一些結(jié)點或一些邊得到。

10.2圖與圖模型例10.9

下圖所示的圖中，G1是G的由結(jié)點導出的導出子圖，G2為G的由邊集導出的導出子圖。V5V3V4V2V1V3V4V2V1由邊集導出的導出子圖G2圖G2圖G圖G1由結(jié)點導出的導出子圖G1V5V3V4V2V110.2圖與圖模型(a)(b)(c)(a)為四個結(jié)點的完全圖，(b)不是完全圖，(c)是有向完全圖。10.2圖與圖模型

定義10.5

設G=<V,E>是n階圖,若G中任何結(jié)點都與其余的n1個結(jié)點相鄰，則稱G為n階完全圖(CompleteGraph)。記作Kn。設D=<V,E>為n階有向圖,若對于任意的結(jié)點,u,vV(u≠v),既有有向邊<u,v>,又有<v,u>，則稱D為有向完全圖。

容易得到如下重要結(jié)論：

Kn的邊數(shù)|E(Kn)|=n(n-1)/2，且對于一般的n個結(jié)點的圖G其邊數(shù)|E(G)|≤n(n-1)/2。10.2圖與圖模型

定義10.6

若圖G的結(jié)點可以分為兩個非空集合V1，V2，G中的邊的端點分別屬于V1，V2，則稱G為二分圖（BipartiteGraph），可簡記為G(V1，V2)。若V1中結(jié)點與V2中結(jié)點均鄰接且V2中結(jié)點與V1中結(jié)點也均鄰接，則稱G為完全二分圖（CompleteBipartiteGraph），記為Km,n，m,n分別是V1，V2的基數(shù)。

10.2圖與圖模型v1v3v2v4v6v5v1v3v2v4v6v5二分圖完全二分圖V1，={v1,v3,v5},V2={v2,v4,v6}10.2圖與圖模型v1v6v2v3v5v1v3v2v4v6v4v5圖(a)圖（b）圖(a)是二分圖,圖（b）是圖(a)的另一種表示。10.3路徑與圖連通性例10.11

在右圖中，1)通道：aebcaebd。2)通道：beacbd（跡）。3)通道：acbe（路）4）通道：acbea（環(huán)）。abedc10.3路徑與圖連通性圖論中的許多概念和應用都與對圖的遍歷有關，即是從一個結(jié)點u出發(fā)，到達與之相鄰接的結(jié)點，在從該鄰接結(jié)點出發(fā)到達其鄰接的結(jié)點，依次類推，最后可以到達圖中的某結(jié)點v，從而就得到一條從u到v的通路。從

u到v的通路W的表示：W:u=v0,v1,v2,…,vk=v，k0。 通路W常表示為u-v通路。這些結(jié)點序列中任意相鄰的結(jié)點在圖中是鄰接的關系，稱結(jié)點vi（i=0，1,…,k）以及邊(vi,vi+1)(i=0,1,…,k-1)為通路W上的結(jié)點與邊。10.3路徑與圖連通性如果通路上首尾結(jié)點相同，則稱該通路是閉的(Closed)，否則稱該通路是開的(Opened)。如果通路上沒有相同的邊，則稱該通路為跡(Trail)，如果跡上的開始結(jié)點與結(jié)束結(jié)點相同，則稱之為回路(Circuit)，如果通路上沒有相同的結(jié)點，則稱該通路為路或路徑(Path)，有n個結(jié)點的路常記作Pn。

如果回路上除了開始結(jié)點與結(jié)束結(jié)點沒有相同的結(jié)點，則稱之為環(huán)(Cycle)。10.3路徑與圖連通性通路遍歷過的邊的數(shù)目為通路的長度，如果通路長度為0，則稱之為平凡通路（TrivialWalk）。兩結(jié)點u，v間的路可能不只一條，將其中的最短的路稱為u，v間的距離。如果一條通路W上有k+1個結(jié)點，即W:u=v0,v1,v2,…,vk=v，k≥0。則由于W上的邊是由W上相鄰結(jié)點(vi,vi+1)(i=0,1,…,k-1)構(gòu)成，因此W上有k條邊，即W的長度為k。如果一條環(huán)C上有k+1個結(jié)點，即C:v0,v1,v2,…,vkv0，k≥0.則由于C上的邊是由C上相鄰結(jié)點(vi,vi+1)(i=0,1,…,k-1)以及（vk,v0）構(gòu)成，因此C上有k+1條邊，即C的長度為k+1。10.3路徑與圖連通性10.3路徑與圖連通性

定理10.2

如果圖G上存在一條u-v通路，則必然存在一條u-v路；如果G上存在一條閉通路，則必然存在一條回路(環(huán))。這是因為，如果通路上存在相同的結(jié)點vi,vj，則可將vi,vj之間的一段通路刪除，并合并vi，vj為一個結(jié)點，從而得到一條更短的u-v通路。如果所得到的u-v通路上還存在相同的結(jié)點，則可以依此繼續(xù)執(zhí)行刪除操作，最終一定可以得到一條沒有相同結(jié)點的u-v通路，也就是一條u-v路。類似地，如果G上存在一條閉通路，則必然存在一條回路（環(huán)）。

10.3路徑與圖連通性例10.11

在右圖中，1)找出一條包含圖所有結(jié)點的通道；2)找出一條包含圖所有結(jié)點的跡；3)找出所有a-d路，并求出其長度；4)找出圖中所有的環(huán)。解

1)包含圖所有結(jié)點的不是跡的通道：aebcaebd。2)包含所有結(jié)點的跡：beacbd。3)a-d路：aebd,acbd,長度均為3。4)環(huán)：acbea，長度為4。abedc找一條回路，且該回路不是環(huán)。V5V3V4V2V1圖G10.3路徑與圖連通性

例10.12

每個結(jié)點的度數(shù)至少為2的圖必包含一個回路。證明設P是圖G中最長路經(jīng)中的一條，并設其長度為m,P的一個端點為u?？疾霨中與u關聯(lián)的邊，由于G中每個結(jié)點的度至少為2，故u必關聯(lián)一條不在P上的邊e，從而e的另一個端點v必然在P上，否則，將這個結(jié)點加入P上，則可以得到更長的路。于是，P上u到v的的路與邊e構(gòu)成回路。

uvP2145832610ABCDEF10.3路徑與圖連通性

例10.13

下圖所示的帶權(quán)圖中，求A到其余結(jié)點的最短路徑。

ABCDEF2145832610ABCDEF求A到其余結(jié)點的最短路徑。

ABCDEF∞∞∞42ABCDEF1012∞32初始基于A→B最短路徑2更新最短路徑:A→C,D,E,FABCDEF812∞32基于A→C最短路徑3更新最短路徑:A→D,E,FFABCDE8101432基于A→D最短路徑8更新最短路徑:A→E,F基于A→E最短路徑10更新最短路徑:A→F2145832610ABCDEF求A到結(jié)點F的最短路徑。

2145832610ABCDEF10.3路徑與圖連通性Dijkstra最短路徑算法輸入：一個帶權(quán)圖G，G的任意兩個結(jié)點間有路徑存在，G中任意邊(v,x)的權(quán)值w(v,x)>0；結(jié)點a與z輸出：L(z)，從結(jié)點a到z的最短路徑長度1ProcedureDijkstra(G)2 For所有結(jié)點x≠a

3

L(x)=∞;L(x)表示a到x的最短路徑長度4 Endfor;5

L(a)=0;6T=V(G);7 S=;

10.3路徑與圖連通性8While(z∈T)9 從T中找出具有最小L(v)的結(jié)點v;10 For所有與v相鄰的結(jié)點x∈T11

L(x)=min{L(x),L(v)+w(v,x)}12 EndFor13 T=T-{v};14 S=S∪{v};15 EndWhile16EndProcedure

10.3路徑與圖連通性

連通圖非連通圖10.3路徑與圖連通性

定義10.5

如果圖G中結(jié)點u到v有一條路徑，則稱結(jié)點u到v是可達的（Accesible）或連通的（Connected）。結(jié)點u到其自身也定義為連通的。

定義10.6

如果圖G的任何兩個結(jié)點都是相互可達的，稱G是連通的（Connected）,并稱G為連通圖(ConnectedGraph)。對于有向圖G，如果G的任何兩個結(jié)點都是相互可達的，則稱有向圖G是強連通的；如果G的任何兩個結(jié)點中，至少從一個結(jié)點到另一個結(jié)點是可達的，稱有向圖G是單向連通的；如果G的有向邊被看作無向邊時是連通的，稱有向圖G是弱連通的。

10.3路徑與圖連通性

容易判斷，強連通圖必定是單向連通圖，單向連通圖必定是弱連通圖。連通圖非連通圖強連通圖單向連通圖弱連通圖10.3路徑與圖連通性

練習4

已知關于a,b,c,d,e,f,g的下述事實：

a說英語；

b說英語和西班牙語；

c說英語、意大利語和俄語；

d說日語和西班牙語；

e說德語和意大利語；

f說法語、日語和俄語；

g說法語和德語；試問：上述7人中是否任意兩人都能交談（如果必要，可由其余5人中所組成的譯員鏈幫忙？）A={王一,王二,張一,張二,張三,李一,李二,李三,李四}兒子孫子重孫子王一王二張一張二張三李一李二李三李四李一李三李二李四王一王二張一張三張二A上的親屬關系滿足自反性、對稱性、傳遞性，一個等價關系決定A的一個分類：

{王一,王二},{張一,張二,張三},{李一,李二,李三,李四}10.3路徑與圖連通性若將圖中兩個結(jié)點間的連通性看作圖的結(jié)點間的一種關系，容易判定圖中兩個結(jié)點間的連通性是一個等價關系， 因為結(jié)點u到u是連通的滿足自反性；若u到v是連通的，則v到u也是連通的，滿足對稱性；若u到v連通，v到w連通，則u到w存在一條通路，從而存在一條u到w的路徑，故u到w是連通的，滿足傳遞性。 但對于有向圖，結(jié)點間的連通性不滿足對稱性。10.3路徑與圖連通性45e3123e2e1V={1，2，3，4，5}圖上的連通關系R={(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2),(4,4),(5,5),(4,5),(5,4)}是一個等價關系，決定V的一個分類：{1，2，3}，{4，5}10.3路徑與圖連通性

現(xiàn)在可以利用結(jié)點的連通性對圖G的結(jié)點集進行劃分，于是利用這個劃分可以得到G的多個連通子圖，如

G[v]=(V[v],E[v]),

是結(jié)點v所在的一個連通子圖，其中，V[v]={x|x到v可達}，E[v]為V[v]中結(jié)點在G中相應的邊之集合。

G[v]具有一個特點，即不存在一個G的真子圖G′,G[v]為G′的真子圖,且G′也是G的連通子圖。稱G[v]為G的連通分支或連通分圖（ConnectedComponent）,也稱為極大連通子圖。

10.3路徑與圖連通性

例10.15

如果圖G恰有兩個不同的奇數(shù)度的結(jié)點u，v，那么u到v必定是可達的。

證明如果u到v不可達，那么G不是連通的，u與v必分屬于兩個連通分支G1，G2，而G1，G2是G的子圖，且都恰有一個奇數(shù)度結(jié)點。與推論10.1矛盾。因而u到v是可達的。

10.3路徑與圖連通性定理10.3

設G是一(n，m)圖，G有ω個分圖，則n-ω≤m≤(n-ω)(n-ω+1)/210.3路徑與圖連通性練習5

在任何n(n≥2)個頂點的簡單圖G中，至少有兩個頂點具有相同的度。

證明如果G有兩個或更多孤立頂點，那么它們便是具有相同的度的兩個頂點。

如果G恰有一個孤立頂點，那么我們可對有n–1個頂點但沒有孤立頂點的G’（它由G刪除孤立頂點后得到）作討論；如果G有分圖，則也可以直接對分圖進行討論。因此，不妨設G沒有孤立頂點，那么G的n個頂點的度數(shù)應是：1，2，3，…，n–1這n–1種可能之一，顯然，必定有兩個頂點具有相同的度。10.3路徑與圖連通性練習6

給定簡單圖G=<V,E>，且|V|=n，|E|＞(n-1)(n-2)/2，試證G是連通圖。試給出|V|=n，|E|=(n-1)(n-2)/2的簡單無向圖G=<V,E>是不連通的例子。

10.3路徑與圖連通性點割集{1，5}126735e1e3e2e4e7e8e64e9e526735e3e4e7e8e64e92673e7e8e64e910.3路徑與圖連通性126735e1e3e2e4e7e8e64e9e5{e4,e5}是邊割集126735e1e3e2e7e8e64e9e5126735e1e3e2e7e8e64e910.3路徑與圖連通性

v4是割點10.3路徑與圖連通性

定義10.9

設S為圖G的結(jié)點集V的子集，稱S為G的點割集（CutSetofVertex）,如果從G中刪除S中的所有結(jié)點后G的連通分支數(shù)增加，但S的任何真子集均無這一特性。當點割集為單元素集合{v}時，v稱為割點（CutVertex）。

設S為連通圖G邊集E的子集，稱S為G的邊割集（CutsetofEdge），如果從G中刪除S的所有邊后G的連通分支數(shù)增加，但S的任何真子集均無這一特性。當割集為單元素集{e}時，稱e為橋(Bridge)或割邊（CutEdge）。

10.3路徑與圖連通性{1，5}是點割集，2是割點，3是割點，{4，7}不是點割集。{e1,e3}是邊割集，{e4,e5}是邊割集，{e6,e8}是邊割集，e9是割邊。126735e1e3e2e4e7e8e64e9e510.3路徑與圖連通性例10.18

試證明：圖G的任一邊，若其不是割邊，則必出現(xiàn)于G的某一環(huán)里。

證明設圖G的邊e=(vi，vj)不是分割邊，去掉e后，與vi相連接的接點集為V1，與vj相連接的結(jié)點集為V2，由割邊定義知，V1∩V2≠。因而存在一結(jié)點v∈V1∩V2，使得在去掉e后，vi與v有路相連，v與vj有路相連。于是vi與vj有路相連接，因而必存在一條連接vi與vj的路P=vi，v1，v2，…，v，…，vj，從而P與邊(vi，vj)組成一個環(huán)。

10.5圖的表示與圖的同構(gòu)1

圖的表示在集合論中，曾經(jīng)用關系矩陣來表示關系，事實上，圖也是一種關系的表示，但用計算機來分析一個圖時，矩陣是其更為形式化的表示方法，這里主要討論鄰接矩陣。構(gòu)造一個圖的鄰接矩陣是很容易的，可以通過下面的例子來分析。10.5圖的表示與圖的同構(gòu)

例10.21

構(gòu)造下圖中圖G的鄰接矩陣。顧名思義，鄰接矩陣就是表示圖結(jié)點的鄰接關系的矩陣，鄰接矩陣與圖是一種一一對應關系。首先，需要確定圖結(jié)點的順序，本題中為a，b，c，d，e。接著，矩陣的元素(ij)表示第i個結(jié)點與第j個結(jié)點的鄰接關系，這里用1或0來表示，如果鄰接，則(ij)為1，否則為0。于是得到圖G的鄰接矩陣

aedcbA(G)=

10.5圖的表示與圖的同構(gòu)

A(G)2==

以A(G)2中d行c列的元素為例，其值是A(G)中第d行與A(G)中第c列運算得到，即

=1?1+0?1+1?0+0?1+1?1=2

aedcb10.5圖的表示與圖的同構(gòu)10.5圖的表示與圖的同構(gòu)

定理9.7

如果A是一個圖G的鄰接矩陣，那么An（n=1，2，3，…）中元素(ij)等于從結(jié)點i到結(jié)點j的長度為n的路徑的數(shù)目。10.2圖與圖模型u1u3u2u4u6u5圖(a)v1v6v2v3v5v4圖（b）定義映射f:{u1,u2,u3,u4,u5,u6}

->{v1,v2,v3,v4,v5,v6},u1->v1,u2->v2,u3->v3,u4->v4,u5->v5,u6->v6圖(a)與圖(b)同構(gòu)10.5圖的表示與圖的同構(gòu)2

圖的同構(gòu)定義10.12

設圖G1=<V1,E1>，G2=<V2,E2>，若存在雙射f:V1V2，滿足uV1，vV1，(u,v)E1當且僅當(f(u),f(v))E2，則稱G1與G2同構(gòu)，記作G1G2，f稱為同構(gòu)映射。如果討論有向圖的同構(gòu)，則對應邊的方向也必須一致。從圖的同構(gòu)的定義可知，二圖同構(gòu)則必有結(jié)點數(shù)相同，邊數(shù)相同，兩圖中度數(shù)相同的結(jié)點的個數(shù)相同。還可以知道，圖的同構(gòu)關系是一種等價關系。

10.5圖的表示與圖的同構(gòu)G1G2G3G4 G1與G2同構(gòu)？ G1與G2不同構(gòu)，原因在于G1中存在三結(jié)點兩兩相鄰，而G2中不存在，因此不可能建立滿足定義的雙射關系。

G4與G2同構(gòu)？ G4與G2不同構(gòu)，原因在于G4中存在三結(jié)點兩兩不相鄰，而G2中卻不存在這樣的情況。 G1與G3同構(gòu)？

10.5圖的表示與圖的同構(gòu)

G與G’同構(gòu)？10.5圖的表示與圖的同構(gòu)圖的同構(gòu)的判斷主要是建立同構(gòu)映射，如果能夠建立，則同構(gòu)的兩個圖除了結(jié)點符號相異外，結(jié)構(gòu)上是完全一樣的。因此，容易想到考慮用鄰接矩陣來進行判斷，即：圖G1和G2是同構(gòu)的當且僅當對某一結(jié)點的順序，其鄰接矩陣是一樣的，最基本的方法是通過變換矩陣行、列元素的順序來比較二鄰接矩陣是否相等。盡管通過判斷鄰接矩陣來判斷圖是否同構(gòu)是可行的，但在最壞情況下，其搜索空間將達到n!(n為結(jié)點數(shù))，具有指數(shù)級算法復雜性。如果n很大，算法的效率是非常低的，甚至不可解。

10.5圖的表示與圖的同構(gòu)從例10.23還可以看到，圖G1和G2同構(gòu)時，G1具有的特性P，G2也應該具備這個特性P。于是判斷兩個圖G1和G2不同構(gòu)的辦法可以是：找到一個G1的特性P，G2并不具備。這樣的一個特性稱為不變量。如“有10個結(jié)點”、“有一個度數(shù)為k的結(jié)點”，以及例10.23中用到的“有k個結(jié)點兩兩相鄰（或不相鄰）”等等。如果能夠找到一些可以簡單測試的同構(gòu)圖具有且只有同構(gòu)圖具有的不變量，那么就可以非常容易的判斷兩個圖是否同構(gòu)。不幸的是，沒有人能夠成功找到這樣一些不變量。10.5圖的表示與圖的同構(gòu)

練習7

畫出完全圖K5的4條邊的所有非同構(gòu)的生成子圖。10.5圖的表示與圖的同構(gòu)

練習8畫出所有具有5個結(jié)點3條邊的互不同構(gòu)的簡單無向圖。10.5圖的表示與圖的同構(gòu)

練習9設G是具有3個結(jié)點的完全圖，試問：（1）G有多少個子圖？（2）G有多少個生成子圖？（3）如果沒有任何兩個子圖同構(gòu)，則G的子圖個數(shù)是多少？10.6歐拉圖七橋問題問題

尋找走遍哥尼斯堡（K?nigsberg）城的7座橋，且只許走過每座橋一次，最后又回到原出發(fā)點(圖論源于游戲)

求解1736年瑞士大數(shù)學家歐拉（Leonhard?Euler）發(fā)表了關于“哥尼斯堡七橋問題”的論文（圖論的第一篇論文）。10.6歐拉圖研究方法——抽象用4個字母A、B、C、D代表4個城區(qū),并用7條線表示7座橋。從而將哥尼斯堡七橋問題抽象為一個數(shù)學問題:即經(jīng)過圖中每邊一次且僅一次的問題。ACDB10.6歐拉圖

定義10.11

給定無孤立點圖G， 若存在一條回路，經(jīng)過圖中的每邊一次且僅一次，該回路稱為歐拉回路(EulerCircuit),稱該圖為歐拉圖。 若存在一條跡，經(jīng)過圖中每邊一次且僅一次，該條路稱為歐拉跡(EulerTrail)，稱該圖為半歐拉圖。10.6歐拉圖

下圖所給出的四個圖，哪些是歐拉圖？

YNYN10.6歐拉圖

定理10.8

圖G是歐拉圖當且僅當G是連通的且每個結(jié)點的度數(shù)為偶數(shù)。證明先證必要條件：設G是歐拉圖。α是G的一個歐拉回路。當α通過G的任一結(jié)點v時，α通過關聯(lián)于v的兩條邊。若α通過v點k次，則α通過關聯(lián)于v的2k條邊。α是歐拉回路。因此α通過關聯(lián)于v的2k條邊即是關聯(lián)于v的所有邊且互不相同，即v的度數(shù)為2k。由v的任意性，必要性得證。

10.6歐拉圖

再證充分條件：設G是連通圖且所有結(jié)點度數(shù)為偶數(shù)，按如下步驟構(gòu)造G的歐拉回路。1)從任一結(jié)點v0出發(fā)，取關聯(lián)于v0的邊(v0，v1)到v1，從v1取關聯(lián)于v1的未通過的邊(v1，v2)到v2，每條邊只取一次，依此可得到一條通路。因為G的任意結(jié)點v的度數(shù)均為偶數(shù)，所以通路到達vi≠v0時，必存在關聯(lián)于vi的未通過的邊(vi，vi+1)沒有出現(xiàn)在通路上。又G的邊為有限條，所以最終總會有某個vk使vk=v0，即得到回路α，α中沒有重復邊。

10.6歐拉圖

2)若α中包含G中所有邊，α即為歐拉回路；反之，設G′為從G中去掉α中的邊后所剩邊及這些邊關聯(lián)的結(jié)點組成，H1，H2，…，Hk為G′的k個分圖。對任一分圖Hi，其所有結(jié)點度數(shù)均為偶數(shù)，Hi與α至少有一個結(jié)點重合，設為vi，對Hi從vi出發(fā)重復步驟(1)，得到回路α′i=vivi1…vi，將α′i并入α中，對于每個分圖H1，…，Hk重復上述過程。

3)若經(jīng)(2)得到的α包含G中的所有邊，則α為歐拉回路；否則重復(2)直到構(gòu)造出一條包含G中所有邊的回路為止。

10.2歐拉圖

練習10

判斷下列各圖，哪些有歐拉路？哪些是歐拉圖？（a）(b)(c)10.6歐拉圖

推論10.2

連通圖G是半歐拉圖，當且僅當G恰有兩個奇數(shù)度結(jié)點。且圖中的歐拉跡一定始于一個奇數(shù)度結(jié)點而止于另一個奇數(shù)度結(jié)點。

10.6歐拉圖

例10.25

一筆畫問題（筆不離開紙,不重復地畫遍紙上圖形的所有的邊）請問下圖中的各圖能否一筆畫出，如果不能，則需要幾筆？

(a)(b)(c)10.6歐拉圖

解一筆畫問題其實可以轉(zhuǎn)化為判斷圖中是否具有歐拉回路或歐拉跡的問題。上圖的三個圖都是連通圖，圖(a)存在歐拉回路，故可以一筆畫出，并回到起始點；圖(b)含有兩個度數(shù)為奇數(shù)的結(jié)點，存在歐拉跡，也可以一筆畫出，但需要從其中一個度數(shù)為奇數(shù)的結(jié)點出發(fā)，結(jié)束點在另一個度數(shù)為奇數(shù)的結(jié)點；圖(c)含有六個奇數(shù)度的結(jié)點，不能一筆畫出。10.6歐拉圖

但可以三筆畫出，因為可以將六個度數(shù)為奇數(shù)的結(jié)點分為三對，每對之間添加一條邊，如下圖中所示，虛線為添加的邊。這樣構(gòu)造出的新圖就存在歐拉回路，可以一筆畫出。但其歐拉回路上存在三條添加的但不鄰接的邊，去除這三條邊，則該歐拉回路被截斷為三段，故需要三筆畫出。

10.6歐拉圖

例10.26

設某封閉式小區(qū)的路網(wǎng)結(jié)構(gòu)如下圖所示，請證明能否設計出一條路線使得清潔車從小區(qū)大門出發(fā)清掃每條道路恰好一次，且在清掃完最后一條道路后正好返回小區(qū)大門處。

小區(qū)大門10.6歐拉圖

解將該小區(qū)路網(wǎng)結(jié)構(gòu)圖用圖論中的圖來表示，如下圖所示，其中，每個結(jié)點代表小區(qū)道路的交叉點，每條邊代表道路。小區(qū)大門位于結(jié)點1處。由于所得到的圖有兩個結(jié)點度數(shù)為奇數(shù)（結(jié)點1與2），其它結(jié)點度數(shù)為偶數(shù)，因此，圖中不存在歐拉回路，即不能設計出一條路線使得清潔車從小區(qū)大門出發(fā)完成清掃道路工作并回到出發(fā)地。

2110.6歐拉圖

例11.27

中國郵路問題

中國郵路問題是我國數(shù)學家管梅谷先生在20世紀60年代提出來的。該問題描述如下：一個郵遞員從郵局出發(fā)，到所管轄的街道投遞郵件，最后返回郵局，若必須走遍所轄各街道中每一條至少一次，則怎樣選擇投遞路線使所走的路程最短？

下面用圖論的語言來描述：用圖論的語言來描述，即在一個帶權(quán)圖G中，能否找到一條回路C，使C包含G的每條邊最少一次且C的長度最短？

10.6歐拉圖

該問題求解思路大體包括三個方面：

1)若G沒有奇數(shù)度結(jié)點，則G是歐拉圖，于是歐拉回路C是唯一的最小長度的投遞路線。

2)若G恰有兩個奇數(shù)度結(jié)點vi和vj，則G具有歐拉跡，且郵局位于結(jié)點vi，則郵遞員走遍所有的街道一次到達結(jié)點vj；從vj返回vi可選擇其間的一條最短路徑。這樣，最短郵路問題轉(zhuǎn)化為求vi到vj的歐拉跡和vj到vi的最短通路問題。

3)若G中奇數(shù)度結(jié)點數(shù)多于2，則回路中必須增加更多的重復邊(路徑）。這時，怎樣使重復邊的總長度最小？已有定理給出了判定條件，若有興趣請查閱相關文獻。

10.6歐拉圖

練習11確定n取怎樣的值，n階完全圖Kn為歐拉圖？10.6歐拉圖

練習12證明：若無向圖G是歐拉圖，則G中無橋。定義10.15

給定圖G，若存在一個環(huán)經(jīng)過圖中的每一個結(jié)點恰好一次，這個環(huán)稱作哈密爾頓環(huán)（H-環(huán)），具有哈密爾頓環(huán)的圖稱為