1、10.1 圖的基本概念 10.1.1 圖的基本概念 10.1.2 圖的結點的度數及其計算 10.1.3 子圖和圖的同構第1頁/共237頁 圖 10.1.1哥尼斯堡七橋問題 10.1 圖的基本概念 第2頁/共237頁10.1.1 圖 現實世界中許多現象能用某種圖形表示,這種圖形是由一些點和一些連接兩點間的連線所組成。 【例10.1.1】a， b， c， d 4個籃球隊進行友誼比賽。 為了表示個隊之間比賽的情況， 我們作出圖10.1.1的圖形。 在圖中個小圓圈分別表示這個籃球隊， 稱之為結點。如果兩隊進行過比賽，則在表示該隊的兩個結點之間用一條線連接起來，稱之為邊。這樣利用一個圖形使各隊之間的比賽

2、情況一目了然。1.圖的定義 10.1 圖的基本概念圖的基本概念 第3頁/共237頁 圖 10.1.1如果圖 10.1.1中的個結點a， b， c， d分別表示個人，當某兩個人互相認識時， 則將其對應點之間用邊連接起來。 這時的圖又反映了這個人之間的認識關系。 10.1 圖的基本概念 第4頁/共237頁 定義10.1.1一個圖G是一個序偶V(G), E(G)， 記為GV(G), E(G)。 其中V(G)是非空結點集合， E(G)是邊集合， 對E(G)中的每條邊， 有V(G)中的結點的有序偶或無序偶與之對應。 若邊e所對應的結點對是有序偶a,b,則稱e是有向邊。a叫邊e的始點,b叫邊e的終點,統稱

3、為e的端點。若邊e所對應的結點對是無序偶(a,b) ,則稱e是無向邊。這時統稱e與兩個結點a和b互相關聯。 10.1 圖的基本概念 第5頁/共237頁 【例10.1.2】 設G=V(G),E(G),其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。則圖G可用圖10.1.2(a)或(b)表示。我們將結點a、b的無序結點對記為(a，b）， 有序結點對記為a，b。 一個圖G可用一個圖形來表示且表示是不唯一的。 10.1 圖的基本概念 第6頁

4、/共237頁圖 10.1.2 10.1 圖的基本概念 第7頁/共237頁圖 10.1.2 10.1 圖的基本概念 第8頁/共237頁 2. 圖G的結點與邊之間的關系 鄰接點: 同一條邊的兩個端點。 孤立點: 沒有邊與之關聯的結點。 鄰接邊: 關聯同一個結點的兩條邊。 孤立邊: 不與任何邊相鄰接的邊。 自回路（環）：關聯同一個結點的一條邊（v，v）或v，v）。 平行邊(多重邊):關聯同一對結點的多條邊。 10.1 圖的基本概念 第9頁/共237頁 如例10.1.1中的圖，結點集Va，b，c，d， 邊集 Ee1， e2， e3， e4， e5， 其中 e1（a，b），e2（a, c），e3（a，d

5、）， e4（b, c）， e5（c, d）。 d與a、 d與c是鄰接的， 但d與b不鄰接， 邊e3與e5是鄰接的。 10.1 圖的基本概念 第10頁/共237頁 【 例 1 0 . 1 . 3 】 設 圖G V ,E 如 圖10.1.3所示。 這里Vv1，v2，v3， Ee1，e2，e3，e4，e5， 其中e1 =(v1, v2) ，e2=(v1，v3) ， e3 =(v3, v3), e4 =(v2, v3), e5=(v2，v3)。 在這個圖中，e3是關聯同一個結點的一條邊,即自回路；邊e4和e5都與結點v2、 v3關聯，即它們是平行邊。 10.1 圖的基本概念 圖 10 .1. 3第11

6、頁/共237頁 3. 圖G的分類按G的結點個數和邊數分為(n,m)圖,即n個結點, m條邊的圖; 特別地, (n,0)稱為零圖, (1,0) 圖稱為平凡圖 。(2) 按G中關聯于同一對結點的邊數分為多重圖和簡單圖; 多重圖:含有平行邊的圖（如圖 10 .1. 3） ； 線 圖: 非多重圖稱為線圖； (1) 簡單圖:不含平行邊和自環的圖。 10.1 圖的基本概念 第12頁/共237頁G1、G2是多重圖G3是線圖G4是簡單圖第13頁/共237頁 (3)按G的邊有序、無序分為有向圖、無向圖和混合圖; 有向圖：每條邊都是有向邊的圖稱為有向圖 （圖 10 .1.4 (b)； 無向圖：每條邊都是無向邊的圖

7、稱為無向圖； 混合圖：既有無向邊, 又有有向邊的圖稱為混合圖。 (4)按G的邊旁有無數量特征分為加權圖、無權圖(如圖 10.1.4); 10.1 圖的基本概念 第14頁/共237頁圖 10 .1. 4(5)按G的任意兩個結點間是否有邊分為完全圖Kn (如圖 10.1.5)和不完全圖(如圖 10.1.6)。 10.1 圖的基本概念 第15頁/共237頁 完全圖：任意兩個不同的結點都鄰接的簡單圖稱為完全圖。n 個結點的無向完全圖記為Kn。 圖10.1.5給出了K3和K4。從圖中可以看出K3有條邊，K4有條邊。 容易證明Kn有 條邊。(1)2n n 10.1 圖的基本概念 圖 10 .1. 6圖 1

8、0.1.5 K3與K4示意圖第16頁/共237頁例213213有向完全圖無向完全圖第17頁/共237頁 給定任意一個含有n個結點的圖G,總可以把它補成一個 具有同樣結點的完全圖,方法是把那些缺少的邊添上。 定義10.1.2 設GV, E是一個具有n個結點的簡單 圖。以V為結點集，以從完全圖Kn中刪去G的所有邊后 得到的圖（或由G中所有結點和所有能使G成為完全圖 的添加邊組成的圖）稱為G的補圖，記為 。 例如，零圖和完全圖互為補圖。G 10.1 圖的基本概念 第18頁/共237頁G相對于Kn的補圖是下圖中的G第19頁/共237頁第20頁/共237頁互為補圖互為補圖互為補圖第21頁/共237頁 【

9、例10.1.4】（拉姆齊問題）試證在任何一個有個人的組里， 存在個人互相認識， 或者存在個人互相不認識。 我們用個結點來代表人， 并用鄰接性來代表認識關系。 這樣一來， 該例就是要證明： 任意一個有個結點的圖G中， 或者有個互相鄰接的點， 或者有個互相不鄰接的點。 即， 對任何一個有個結點的圖G， G或 中含有一個三角形（即K3）。 G 10.1 圖的基本概念 第22頁/共237頁 證明: 設GV ,E， |V|6， v是G中一結點。 因為v 與G的其余個結點或者在 中鄰接， 或者在G中鄰接。 故不失一般性可假定， 有個結點v1， v2， v3在G中與v鄰接。 如果這個結點中有兩個結點（如v1

10、， v2）鄰接， 則它們與v 就是G中一個三角形的個頂點。 如果這3個結點中任意兩個在G中均不鄰接， 則v1， v2， v3就是 中一個三角形的個頂點。 GG 10.1 圖的基本概念 第23頁/共237頁 10.1.2 圖的結點的度數及其計算 我們常常需要關心圖中有多少條邊與某一結點 關聯，這就引出了圖的一個重要概念結點的度數。 10.1 圖的基本概念 定義定義: 在有向圖中在有向圖中, 以以v為終點的邊數稱為結點為終點的邊數稱為結點v 的入的入度，度， 記為記為 ;以以v為始點的邊數稱為結點為始點的邊數稱為結點v 的出的出度，度， 記為記為 。結點。結點v的入度與出度之和稱為結的入度與出度之

11、和稱為結點點v的度數，記為的度數，記為 d(v)或或deg(v)。 ( )dv( )dv第24頁/共237頁定義定義: 在無向圖中，圖中結點在無向圖中，圖中結點v所關聯的邊所關聯的邊數數(有環時計算兩次有環時計算兩次)稱為結點稱為結點v 的度數，記為的度數，記為d(v)或或deg(v) 。| )(min)( | )(max)( VvvdGVvvdG最小度最大度第25頁/共237頁例245136G1頂點2入度：1 出度：3頂點4入度：1 出度：0例157324G26頂點5的度：3頂點2的度：4第26頁/共237頁 定理 10.1.1 無向圖GV ,E中結點度數的總和等于邊數的兩倍， 即 證明:

12、因為每條邊都與兩個結點關聯， 所以加上一條邊就使得各結點度數的和增加 2， 由此結論成立。 定義：無向圖中，如果每個結點的度都是k,則稱為k-度正則圖。d( )2VE 10.1 圖的基本概念 第27頁/共237頁 推論: 無向圖G中度數為奇數的結點必為偶數個。 證明: 設V1和V2分別是G中奇數度數和偶數度數的結點集。 由定理10.1.1知 由于 是偶數之和， 必為偶數， 而2|E|也為偶數， 故 是偶數。 由此|V1|必為偶數。1deg( )VEvvVvVv2)deg()deg(212)deg(Vvv 10.1 圖的基本概念 第28頁/共237頁 定理定理 10.1.2 在任何有向圖在任何有

13、向圖GV ,E中，中， 有有( )( )v Vv VdvdvE圖10.1.4第29頁/共237頁 10.1.3 子圖和圖的同構 1.子圖 在研究和描述圖的性質時，子圖的概念占有重要地位。 定義10.1.5 設有圖G=V , E和圖 G= V, E 。 1) 若VV， EE， 則稱G是G的子圖。 2) 若G是G的子圖，且EE，則稱G是G 的真子圖。 第30頁/共237頁356例245136圖與子圖第31頁/共237頁 3) 若V=V， EE，則稱G是G的生成子圖。 圖10.1.7給出了圖G以及它的真子圖G1和生成子圖G2。 圖10.1.7 圖G以及其真子圖G 1和生成子圖G2 10.1 圖的基本

14、概念 第32頁/共237頁例例 畫出畫出K4的所有非同構的生成子圖。的所有非同構的生成子圖。第33頁/共237頁2221112222222222222 , , GV EGV Euvu vEGVGVG VGEGEEEGV結點定義： 設圖是圖的子圖。若對任意結點 和 ，如果，則由唯一地確定，并稱是，記為或。如果無孤立結點，且集合的誘導子圖邊集的誘導子圖由所唯一確定，則稱是，記為或。第34頁/共237頁 2. 圖的同構 10.1 圖的基本概念 試觀察下面各圖有何異同？第35頁/共237頁 圖 10.1.8 同構的圖 圖 10.1.9 10.1 圖的基本概念 第36頁/共237頁 定義10.1.6 設

15、有圖 G=V , E和圖G= V, E。 如果存在雙射：VV，使得 e=(u, v) E iff e=(u),(v)E， 且 (u， v)與(u),(v)有相同的重數，則稱G與G 同構。記作GG。 注：由同構的定義可知，不僅結點之間要具有一一對應關系，而且要求這種對應關系保持結點間的鄰接關系。對于有向圖的同構還要求保持邊的方向。 10.1 圖的基本概念 第37頁/共237頁 【例10.1.5】考察圖10.1.9中的兩個圖GV , E和 G= V, E 。 顯然，定義：VV, (vi)v i , 可以驗證是滿足定義10.1.6的雙射，所以GG。 10.1 圖的基本概念 圖 10.1.9第38頁/

16、共237頁 一般說來，證明兩個圖是同構的并非是輕而易舉的事情，往往需要花些氣力。請讀者證明下圖中兩個圖是同構的。第39頁/共237頁第40頁/共237頁 根據圖的同構定義，可以給出圖同構的必要條件如下： (1) 結點數目相等； (2) 邊數相等； (3) 度數相同的結點數目相等。 但這僅僅是必要條件而不是充分條件。第41頁/共237頁下圖中的(a)和(b)滿足上述三個條件，然而并不同構。因為在(a)中度數為3的結點x與兩個度數為1的結點鄰接，而(b)中度數為3的結點y僅與一個度數為1的結點鄰接。尋找一種簡單有效的方法來判定圖的同構，至今仍是圖論中懸而未決的重要課題。第42頁/共237頁第43頁

17、/共237頁 對于同構，形象地說，若圖的結點可以任意挪動位置，而邊是完全彈性的，只要在不拉斷的條件下，這個圖可以變形為另一個圖，那么這兩個圖是同構的。故同構的兩個圖從外形上看可能不一樣，但它們的拓撲結構是一樣的。 第44頁/共237頁10.2 路與圖的連通性(Walks & The Connectivity of Graphs) 10.2.1 路與回路(Walks and Circuits) 1 0 . 2 . 2 圖 的 連 通 性 ( T h e Connectivity of Graphs) 第45頁/共237頁10.2.1 路與回路(Wlaks and Circuits) 定義

18、 10.2.1 給定圖GV ,E, 設v0, v1, , vkV， e1，e2，ekE，其中ei是關聯于結點vi-1和vi的邊， 稱交替序列v0e1v1e2ekvk為連接v0到vk的路， v0和vk分別稱為路的起點與終點。路中邊的數目k稱作路的長度。 當v0=vk時,這條路稱為回路。 在簡單圖中一條路v0e1v1e2ekvk由它的結點序列v0v1vk確定,所以簡單圖的路,可表示為v0v1vk 。如圖10.1.1表示的簡單圖中， 路ae1be4ce5d可寫成abcd。 第46頁/共237頁 定義 10.2.2 設=v0e1v1e2ekvk是圖G中連接v0到vk的路。 1)若e1， e2， ， e

19、k都不相同， 則稱路為簡單路或跡； 2)若v0， v1， ， vk都不相同，則稱路為基本路或通路； 3) 圈中若出現的每條邊恰好一次，稱簡單圈。若出現的每個結點恰好一次，稱基本圈。 10.2.1 路與回路(Wlaks and Circuits)第47頁/共237頁結點重復情況結點重復情況邊重復情況邊重復情況路路 允許允許 允許允許簡單路簡單路 允許允許不允許不允許 基本路基本路 不允許不允許 不允許不允許 回路回路允許允許允許允許簡單圈簡單圈允許允許不允許不允許基本圈基本圈不允許不允許不允許不允許10.2.1 路與回路(Wlaks and Circuits)第48頁/共237頁 注意：不同的教

20、材定義不同！ 途徑(walk)：圖G中一個點邊交替出現的序列。 跡(trail)：邊不重的途徑。 路(path): 頂點不重復的跡。 閉途徑（closed walk）：起點和終點相同的途徑。 閉跡(closed trail)：起點和終點相同的跡，也稱為回路（circuit）。 圈(cycle): 起點和終點相同的路。10.2.1 路與回路(Wlaks and Circuits)第49頁/共237頁例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長

21、度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1第50頁/共237頁 例如在圖 10.2.1中， 有連接v5到v3的路v5e8v4e5v2e6v5e7v3， 這也是一條簡單路；路 v1e1v2 e3v3是一條基本路； 路v1e1v2e3v3e4v2e1v1是一 條回路， 但不是基本圈； 路v1e1v2e3v3e2v1是一條 回路， 也是圈。 圖 10.2.1 10.2.1 路與回路(Wlaks and Circuits)第51頁/共237頁 定義 10.2.3 在圖G中， 若結點vi到vj有路連接（這時稱vi和vj是可達的）， 其中長度最短的路的長

22、度稱為vi到vj 的距離， 用符號d(vi,vj)表示。若從vi到vj不存在路徑,則d(vi,vj)=。 例如在圖10.2.1中， （v1， v4）。 10.2.1 路與回路(Wlaks and Circuits)第52頁/共237頁 注意:在有向圖中,d(vi,vj)不一定等于d(vj,vi), 但一般地滿足以下性質: (1) d(vi,vj)0; (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)d(vi,vk)。 圖 10.2.1 10.2.1 路與回路(Wlaks and Circuits)第53頁/共237頁 定理 10.2.1 設G是具有n個結點的圖， 如果

23、從結點v1到另一結點v2存在一條路，則從結點v1到v2必存在一條長度不大于n1的基本路（通路）。 10.2.1 路與回路(Wlaks and Circuits)第54頁/共237頁 證明:假定從v1到v2存在一條路徑,(v1,vi,v2)是所經的結點,如果其中有相同的結點vk,例 (v1,vi,vk,vk,v2),則刪去從vk到vk的這些邊,它仍是從v1到v2的路徑,如此反復地進行直至(v1,vi,v2)中沒有重復結點為止。此時,所得的就是通路。通路的長度比所經結點數少1,圖中共n個結點,故通路長度不超過n-1。 推論 設圖GV ,E ， |V|n， 則G中任一基本圈長度不大于n。10.2.1

24、 路與回路(Wlaks and Circuits)第55頁/共237頁 1. 無向圖的連通性 定義 10.2.4 在無向圖如果一個圖的任何兩個結點之間都有一條路，那么我們稱這個圖是連通的，否則是不連通的。 定義 10.2.5 圖G的一個連通的子圖G（稱為 連通子圖）若不包含在G的任何更大的連通子圖中， 它就被稱作G的連通分支。我們把圖G的連通分支個數記作（G）。10.2.2 圖的連通性(The Connectivity of Graphs)第56頁/共237頁圖 10.2.3 圖G與G 在圖10.2.3中， G是不連通的， （G）， 而G是連通的， （G）。 任何一個圖都可劃分為若干個連通分支

25、。 顯然， 僅當圖G的連通分支數（G）時， 圖G是連通的。10.2.2 圖的連通性第57頁/共237頁 在圖的研究中，常常需要考慮刪去與增加結點、結點集、邊和邊集（或弧集）的問題。所謂從圖G=中刪去結點集S，是指作V-S以及從E中刪去與S中的全部結點相聯結的邊而得到的子圖，記作G-S；特別當S=v時，簡記為G-v；所謂從圖G=中刪去邊集（或弧集）T，是指作E-T，且T中的全部邊所關聯的結點仍在V中而得到的子圖，記為G-T；特別當T=e 時，簡記作G-e。第58頁/共237頁 所謂圖G=增加結點集S，是指作VS以及向E中并入S中、S與V中所成的邊而得到的圖，記作G+S；特別當S=v 時，簡記為G

26、+v；圖G=增加邊集（或弧集）T是指作ET所得到的圖，記作G+T，這里T中全部邊（或弧）的關聯結點屬于V。第59頁/共237頁 定義: 給定連通無向圖G=，S V。若(G-S)(G)，但 T S有 (G-T)= (G)，則稱S是G的一個分離結點集。若圖G的分離結點集S=v ，則稱v是G的割點。 類似地可定義圖G的分離邊集T；若圖G的分離邊集T=e ，則稱e是G的割邊或橋。第60頁/共237頁 對于連通的非平凡圖G，稱 (G)= |S|S是G的分離結點集 為圖G的結點連通度，它表明產生不連通圖而需要刪去結點的最少數目。于是，對于分離圖G， (G)=0；對于存在割點的連通圖G， (G)=1。VSm

27、in第61頁/共237頁 類似地定義邊連通度 (G)= |T|T是G的分離邊集 ，它表明產生不連通圖而需要刪去邊的最少數目。可見，對于分離圖G， (G)=0；對于平凡圖G， (G)=0；對于圖K1， (K1)=0；對于存在割邊的連通圖G， (G)=1；對于完全圖Kn， (Kn)=n-1。ETmin第62頁/共237頁 下面是由惠特尼(H.Whitney)于1932年得到的關于結點連通度、邊連通度和最小度的不等式聯系的定理： 定理: 對于任何一個無向圖G，有 (G) (G)(G)。 定理: 一個連通無向圖G中的結點v是割點存在兩個結點u和w，使得聯結u和w的每條鏈都經過v。第63頁/共237頁

28、定理: 一個連通無向圖G中的邊e是割邊 存在兩個結點u和w，使得聯結u與w的每條鏈都經過e。 下面再給出一個判定一條邊是割邊的充要條件。 定理: 連通無向圖G中的一條邊e是割邊e不包含在圖的任何基本圈中。第64頁/共237頁 2. 有向圖的連通性 定義10.2.6 在有向圖中,若從結點u到v有一條路，則稱u可達v。 定義10.2.7 設有有向圖G， 1)若G的任意兩個結點中,至少從一個結點可達另一個結點,則稱圖G是單向連通的; 10.2.2 圖的連通性第65頁/共237頁 2)如果G的任意兩個結點都是相互可達的,則稱圖G是強連通的; 3)如果略去邊的方向后， G成為連通的無向圖，則稱圖G是弱連

29、通的。 從定義可知：從定義可知： 若圖若圖G是單向連通的，是單向連通的， 則必是弱連通的；若圖則必是弱連通的；若圖G是強連通的，是強連通的， 則則必是單向連通的，必是單向連通的， 且也是弱連通的。且也是弱連通的。 但反但反之不真。之不真。 第66頁/共237頁 定理 10.2.2一個有向圖G是強連通的， 當且僅當G中有一個（有向）回路， 它至少包含每個結點一次。 第67頁/共237頁證明: 必要性：如果有向圖G是強連通的，則任意兩個結點都是相互可達的。故必可作一回路經過圖中所有各結點。否則必有一回路不包含某一結點v。這樣，v與回路上各結點就不能相互可達， 這與G是強連通矛盾。 充分性：如果G中

30、有一個回路，它至少包含每個結點一次，則G中任意兩個結點是相互可達的， 故G是強連通的。 10.2.2 圖的連通性第68頁/共237頁 定義 10.2.8 在有向圖G=V,E中,G是G的子圖,若G是強連通的(單向連通的,弱連通的),沒有包含G的更大子圖G是強連通的(單向連通的,弱連通的),則稱G是G的強分圖(單向分圖,弱分圖)。 10.2.2 圖的連通性第69頁/共237頁連通圖例245136強連通圖356例非連通圖連通分圖例245136第70頁/共237頁圖 10.2.5 10.2.2 圖的連通性(The Connectivity of Graphs)第71頁/共237頁 在圖10.2.5中,

31、強分圖集合是: 1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8 單向分圖集合是: 1,2,3,4,5,e1,e2,e3,e4,e5,6,5,e6, 7,8,e7,e8 弱分圖集合是: 1,2,3,4,5,6,e1,e2,e3,e4,e5,e6, 7,8,e7,e810.2.2 圖的連通性第72頁/共237頁 下面給出簡單有向圖的一個應用資源分配圖。 在多道程序的計算機系統中，可以同時執行多個程序。實際上，程序共享計算機系統中的資源，如磁帶機、磁盤設備、CPU、主存貯器和編譯程序等。操作系統對這些資源負責分配給各個程序。當一個程序要求使用某種資源，它要發出請求，操作系統必須保證這一

32、請求得到滿足。第73頁/共237頁對資源的請求可能發生沖突。如程序A控制著資源r1，請求資源r2；但程序B控制著資源r2，請求資源r1。這種情況稱為處于死鎖狀態。然而沖突的請求必須解決，資源分配圖有助發現和糾正死鎖。假設某一程序對一些資源的請求，在該程序運行完之前必須都得到滿足。在請求的時間里，被請求的資源是不能利用的，程序控制著可利用的資源，但對不可利用的資源則必須等待。第74頁/共237頁令Pt=p1，p2，pm 表示計算機系統在時刻t的程序集合，Qt Pt是運行的程序集合，或者說在時刻t至少分配一部分所請求的資源的程序集合。Rt=r1，r2，rn 是系統在時刻t的資源集合。資源分配圖Gt

33、=是有向圖，它表示了時刻t系統中資源分配狀態。把每個資源ri看作圖中一個結點，其中i=1，2，n。表示有向邊，E當且僅當程序pkQt已分配到資源ri且等待資源rj。第75頁/共237頁例如，令Rt=r1,r2,r3,r4 ，Qt=p1,p2,p3,p4 。資源分配狀態是：p1占用資源r4且請求資源r1；p2占用資源r1且請求資源r2和r3；p3占用資源r2且請求資源r3；p4占用資源r3且請求資源r1和r4。第76頁/共237頁于是，可得到資源分配圖Gt=，如圖10.2.7所示。能夠證明，在時刻t計算機系統處于死鎖狀態資源分配圖Gt中包含強分圖。于是，對于圖10.2.7，Gt是強連通的，即處于

34、死鎖狀態。第77頁/共237頁圖 10.2.7第78頁/共237頁10.3 圖的矩陣表示(Matrix Notation of Graph) 10.3.1 鄰接矩陣 (Adjacency Matrices) 10.3.2 可達性矩陣 (Reachability Matrices )第79頁/共237頁10.3.1鄰接矩陣 (Adjacency Matrices) 上面我們介紹了圖的一種表示方法， 即用圖形表示圖。 它的優點是形象直觀， 但是這種表示在結點與邊的數目很多時是不方便的。 下面我們提供另一種用矩陣表示圖的方法。 利用這種方法， 我們能把圖用矩陣存儲在計算機中， 利用矩陣的運算還可以了

35、解到它的一些有關性質。第80頁/共237頁 定義 10.3.1 設GV ,E是有n個結點的簡單圖， 則n階方陣（aij）稱為G的鄰接矩陣。 其中1( ,)0ijijEa 否則 如圖10.3.1所示的圖G， 其鄰接矩陣A為10.3 圖的矩陣表示(Matrix Notation of Graph) 第81頁/共237頁0111110100110101010110010A 顯然無向圖的鄰接矩陣必是對稱的。 下面的定理說明， 在鄰接矩陣A的冪A2， A3， 等矩陣中， 每個元素有特定的含義。 圖10.3.1 G 10.3 圖的矩陣表示(Matrix Notation of Graph) 第82頁/共2

36、37頁圖10.3.1 圖G 10.3 圖的矩陣表示(Matrix Notation of Graph) 第83頁/共237頁 定理 10.3.1 設G是具有n個結點v1, v2, ,vn 的圖， 其鄰接矩陣為A， 則Ak（k1， 2， ）的（i， j）項元素a(k)ij是從vi到vj的長度等于k的路的總數。 證明: 施歸納于k。 當k1時， A1A， 由A的定義， 定理顯然成立。 若kl時定理成立， 則當kl1時， A l+1Al A， 所以 rjnrlirlijaaa1)()1(10.3 圖的矩陣表示(Matrix Notation of Graph) 第84頁/共237頁 根據鄰接矩陣定義

37、arj是聯結vr和vj的長度為1的路數目,a(l)ir是聯結vi和vr的長度為l的路數目,故上式右邊的每一項表示由vi經過l條邊到vr,再由vr 經過1條邊到vj的總長度為l+1的路的數目 。對所有r求和,即得a(l+1)ij是所有從vi到vj的長度等于l+1的路的總數,故命題對l+1成立。 10.3 圖的矩陣表示(Matrix Notation of Graph) 第85頁/共237頁 由定理10.3.1可得出以下結論： 1) 如果對l1， 2， ， n-1， Al的 （i， j）項元素（ij）都為零， 那么vi和vj之間無任何路相連接， 即vi和vj不連通。 因此， vi和vj必屬于G的不

38、同的連通分支。 10.3 圖的矩陣表示(Matrix Notation of Graph) 第86頁/共237頁 2) 結點vi 到vj （ij）間的距離d（vi， vj） 是使Al（l1， 2， ， n-1 ）的（i， j）項元素不為零的最小整數l。 3) Al的（i， i）項元素a(l)ii表示開始并結束于vi長度為l的回路的數目。10.3 圖的矩陣表示(Matrix Notation of Graph) 第87頁/共237頁 【例10.3.1】圖GV ,E的圖形如圖10.3.2， 求鄰接矩陣A和A2， A3， A4， 并分析其元素的圖論意義。 10.3 圖的矩陣表示(Matrix Not

39、ation of Graph) 圖 10.3.2第88頁/共237頁 解: 0100010000000100010100010A10.3 圖的矩陣表示(Matrix Notation of Graph) 第89頁/共237頁 1) 由A中a(1)121知， v1和v2是鄰接的； 由A3中a(3)122知， v1到v2長度為3的路有兩條， 從圖中可看出是v1v2v1v2和v1v2v3v2。 2) 由A2的主對角線上元素知， 每個結點都有長度為的回路， 其中結點v2有兩條： v2v1v2和v2v3v2， 其余結點只有一條。 3) 由于A3的主對角線上元素全為零， 所以G中沒有長度為的回路。10.3

40、 圖的矩陣表示(Matrix Notation of Graph) 第90頁/共237頁 4) 由于 所以結點v3和v4間無路， 它們屬于不同的連通分支。 5) d（v1， v3）。 , 0)4(34)3(34)2(34)1(34aaaa10.3 圖的矩陣表示(Matrix Notation of Graph) 第91頁/共237頁10.3.2可達性矩陣 (Reachability Matrices ) 下面用矩陣來研究有向圖的可達性。 與無向圖一樣， 有向圖也能用相應的鄰接矩陣 A（aij）表示， 其中但注意這里A不一定是對稱的。01ija否則Evvji,第92頁/共237頁 定義 10.3

41、.2 設GV ,E是一個有n個結點的有向圖， 則n階方陣（pij）稱為圖G的可達性矩陣。 其中10ijp (vi到vj可達) (否則) 10.3.2可達性矩陣 (Reachability Matrices )第93頁/共237頁 根據可達性矩陣， 可知圖中任意兩個結點之間是否至少存在一條路以及是否存在回路。 根據n個結點的圖中，基本路的長度不大于n-1，基本圈的長度不大于n。因此， 分以下兩步可得到可達性矩陣。 10.3.2可達性矩陣 (Reachability Matrices )第94頁/共237頁 1) 令BnAA2An, 2) 將矩陣n中不為零的元素均改為， 為零的元素不變，所得的矩陣

42、P就是可達性矩陣。 當n很大時， 這種求可達性矩陣的方法就很復雜。 下面再介紹一種更簡便的求可達性矩陣的方法。 10.3.2可達性矩陣 (Reachability Matrices )第95頁/共237頁 因可達性矩陣是一個元素僅為或的矩陣（稱為布爾矩陣）， 而在研究可達性問題時， 我們對于兩個結點間具有路的數目并不感興趣， 所關心的只是兩結點間是否有路存在。 因此， 我們可將矩陣A，A2, An,分別改為布爾矩陣A( 1 )， A( 2 )， ， A(n)。 10.3.2可達性矩陣 (Reachability Matrices )第96頁/共237頁 由此有 A(2)A(1)A(1)AA A

43、(3)A(2)A(1) A(n)A(n-1)A(1) PA(1)A(2)A(n) 相應的矩陣加法和乘法稱為矩陣的布爾加和布爾乘。10.3.2可達性矩陣 (Reachability Matrices )第97頁/共237頁令令B和和C的布爾和、布爾積分別記為的布爾和、布爾積分別記為B C和和B C，其定義為，其定義為(B C)ij=bij cij(B C)ij= (bik ckj)i,j=1,2,n。其中。其中bij，cij分別是分別是B和和C的的i行行j列列元素。元素。nk1nk1第98頁/共237頁特別地，對于鄰接矩陣特別地，對于鄰接矩陣A，記，記A A=A(2)，對任，對任何何r=2,3,

44、有有A(r-1) A=A(r)要注意的是要注意的是Ar與與A(r)的差別。的差別。Ar中中 表明從表明從vi到到vj長度為長度為r的鏈（或路）的數目，而的鏈（或路）的數目，而A(r)中中 是指出：若是指出：若vi到到vj至少存在一條鏈（或路）時，至少存在一條鏈（或路）時，=1，否則，否則， =0。由上說明，便得到可達矩陣由上說明，便得到可達矩陣P為：為：P=A A(2) A(3) A(n)= A(k)nk1arijarij)(arij)(arij)(arijrija()rija()rija()rija第99頁/共237頁圖 10.3.310.3.2可達性矩陣 (Reachability Mat

45、rices ) 【例10.3.2】求出圖10.3.3所示圖的可達性矩陣。 第100頁/共237頁0100001011001110A10.3.2可達性矩陣 (Reachability Matrices )解解: 該圖的鄰接矩陣為該圖的鄰接矩陣為(2)010001000010001000101100110011000110111011101110A第101頁/共237頁(3)(4)(1)(2)(3)(4)110001 10011011 10111011 10111011 101 1 101 1 101 1 101 1 10AAPAAAA故 10.3.2可達性矩陣 (Reachability Mat

46、rices )第102頁/共237頁 定理 10.3.2 有向圖G是強連通的當且僅當其可 達性矩陣P的元素均為。 與求關系的傳遞閉包的關系矩陣相同！ 10.3.2可達性矩陣 (Reachability Matrices )第103頁/共237頁 為了計算為了計算A+或或P，自然可先依次求得，自然可先依次求得A(2)，A(3)，A(n)，然后再計算，然后再計算 A(k)，其結果，其結果即為所求，這是計算即為所求，這是計算A+或或P的一種方法，還可的一種方法，還可介紹一種現有效的方法介紹一種現有效的方法Warshall算法，它由算法，它由鄰接矩陣鄰接矩陣A依下面給出的步驟便能計算依下面給出的步驟便

47、能計算A+。其。其步驟如下：步驟如下：nk1nk1第104頁/共237頁 (1) PA (2) k1 (3) i1 (4) 若pik=1，對j=1,2,n作pijpij pkj (5) ii+1，若in則轉(4) (6) kk+1，若kn則轉到(3)，否則停止。 該算法的關鍵的一步是(4)，它判定如果pik=1，將第i行和第k行的各對應元素作布爾和或邏輯加后送到第i行中去。第105頁/共237頁10. 5 歐拉圖與哈密爾頓圖(Eulerian Graph and Hamilton-ian Graph) 10.5.1 歐拉圖(Eulerian Graph) 10.5.2哈密爾頓圖(Hamilto

48、n-ian Graph) 第106頁/共237頁10.4.1 歐拉圖 歷史上的哥尼斯堡七橋問題是著名的圖論問題。 問題是這樣的： 18世紀的東普魯士有個哥尼斯堡城， 在橫貫全城的普雷格爾河兩岸和兩個島之間架設了7座橋， 它們把河的兩岸和兩個島連接起來（如圖10.4.1）。第107頁/共237頁 每逢假日，城中居民進行環城游玩，人們對此提出了一個“遍游”問題，即能否有這樣一種走法，使得從某地出發通過且只通過每座橋一次后又回到原地呢？ 10.4 歐拉圖與哈密爾頓圖第108頁/共237頁 我們將圖10.4.1中的哥尼斯堡城的4塊陸地部分分別標以A， B， ， D， 將陸地設想為圖的結點， 而把橋畫成

49、相應的連接邊， 這樣圖10.4.1可簡化成圖10.4.2。 于是七橋“遍游”問題等價于在圖10.4.2中， 從某一結點出發找到一條回路， 通過它的每條邊一次且僅一次， 并回到原來的結點。 10.4 歐拉圖與哈密爾頓圖第109頁/共237頁圖 10.4.1哥尼斯堡七橋問題示圖 10.4 歐拉圖與哈密爾頓圖第110頁/共237頁 圖 10.4.2哥尼斯保七橋問題簡化圖 10.4 歐拉圖與哈密爾頓圖第111頁/共237頁 定義 10.4.1 給定無孤立結點的圖G， 若存在一條經過G中每邊一次且僅一次的回路， 則該回路為歐拉回路。 具有歐拉回路的圖稱為歐拉圖。 例如， 給出如圖10.4.3所示的兩個圖

50、， 容易看出， (a)是歐拉圖， 而(b)不是歐拉圖。 10.4 歐拉圖與哈密爾頓圖第112頁/共237頁 圖 10.4.310.4 歐拉圖與哈密爾頓圖第113頁/共237頁 定理 10.4.1 連通圖G是歐拉圖的充要條件是G的所有結點的度數都是偶數。 證明: 必要性： 設G是一歐拉圖， 是G中的一條歐拉回路。 當通過G的任一結點時， 必通過關聯于該點的兩條邊。 又因為G中的每條邊僅出現一次， 所以所通過的每個結點的度數必定是偶數。 10.4 歐拉圖與哈密爾頓圖第114頁/共237頁 圖 10.4.4 圖G 10.4 歐拉圖與哈密爾頓圖第115頁/共237頁 充分性： 我們可以這樣來作一個閉跡

51、， 假設它從某結點A開始， 沿著一條邊到另一結點， 接著再從這個結點， 沿沒有走過的邊前進， 如此繼續下去。 因為我們總是沿著先前沒有走過的新邊走， 又由于圖G的邊數有限， 所以這個過程一定會停止。 但是， 因為每一個結點都與偶數條邊關聯， 而當沿前進到達結點v 時， 若vA， 走過了與v關聯的奇數條邊， 這樣在v上總還有一條沒有走過的邊。 因此， 必定返回停止在A（見圖10.4.4）。 10.4 歐拉圖與哈密爾頓圖第116頁/共237頁 如果走遍了G的所有邊， 那么我們就得到所希望的一條歐拉回路。 如果不是這樣， 那么在上將有某一結點B， 與它關聯的一些邊尚未被走過（因G連通）。 但是， 實

52、際上， 因為走過了與B關聯的偶數條邊， 因此不屬于的與B關聯的邊也是偶數條。 對于其他有未走過邊所關聯的所有結點來說， 上面的討論同樣正確。 于是若設G1是G的包含點B的一個連通分支， 則G1的結點全是偶數度結點。 10.4 歐拉圖與哈密爾頓圖第117頁/共237頁 運用上面的討論， 我們在G1中得到一個從B點出發的一條閉跡1。 這樣我們就得到了一條更大的閉跡， 它是從A點出發沿前進到達B， 然后沿閉跡1回到B， 最后再沿由B走到A。 如果我們仍然沒有走遍整個圖， 那么我們再次把閉跡擴大， 以此類推， 直到最后得到一個歐拉回路。 由于在七橋問題的圖10.4.2中， 有個點是奇數度結點， 故不存

53、在歐拉回路， 七橋問題無解。 10.4 歐拉圖與哈密爾頓圖第118頁/共237頁 在圖10.2.3中， (a)圖的每個結點的度數都為， 所以它是歐拉圖；(b)圖不是歐拉圖。 但我們繼續考察(b)圖可以發現， 該圖中有一條路v2v3v4v5v2v1v5， 它經過(b)圖中的每條邊一次且僅一次， 我們把這樣的路稱為歐拉路。 定義10.4.2 通過圖G的每條邊一次且僅一次的路稱為圖G的歐拉路。 對于歐拉路有下面的判定方法。 10.4 歐拉圖與哈密爾頓圖第119頁/共237頁 定理10.4.2 連通圖G具有一條連接結點vi和vj的歐拉路當且僅當vi和vj是G中僅有的奇數度結點。 10.4 歐拉圖與哈密

54、爾頓圖第120頁/共237頁 證明: 將邊(vi， vj)加于圖G上， 令其所得的圖為G（可能是多重圖）。 由定理10.4 .1知： G有連接結點vi和vj的歐拉路， iff G有一條歐拉回路， iff G的所有結點均為偶度結點， iff G的所有結點除vi和vj外均為偶度結點， iff vi和vj是G中僅有的奇度結點。10.4 歐拉圖與哈密爾頓圖第121頁/共237頁 我國民間很早就流傳一種“一筆畫”游戲。 由定理10.4 .1和定理10.4.2知， 有兩種情況可以一筆畫。 1) 如果圖中所有結點是偶數度結點， 則可以任選一點作為始點一筆畫完； 2) 如果圖中只有兩個奇度結點， 則可以選擇其

55、中一個奇度結點作為始點也可一筆畫完。 10.4 歐拉圖與哈密爾頓圖第122頁/共237頁 【例10.4.1】圖10.4.5(a)是一幢房子的平面圖形， 前門進入一個客廳， 由客廳通向4個房間。 如果要求每扇門只能進出一次， 現在你由前門進去， 能否通過所有的門走遍所有的房間和客廳， 然后從后門走出。 10.4 歐拉圖與哈密爾頓圖第123頁/共237頁圖 10.4.510.4 歐拉圖與哈密爾頓圖第124頁/共237頁 解: 將4個房間和一個客廳及前門外和后門外作為結點， 若兩結點有邊相連就表示該兩結點所表示的位置有一扇門相通。 由此得圖10.4.5(b)。 由于圖中有4個結點是奇度結點， 故由定

56、理10.4.2知本題無解。 類似于無向圖的結論， 對有向圖有以下結果。 10.4 歐拉圖與哈密爾頓圖第125頁/共237頁 定理10.4.3 一個連通有向圖具有（有向）歐拉回路的充要條件是圖中每個結點的入度等于出度。 一個連通有向圖具有有向歐拉路的充要條件是最多除兩個結點外的每個結點的入度等于出度， 但在這兩個結點中， 一個結點的入度比出度大1， 另一個結點的入度比出度少1。 下面舉一個有趣的例子是計算機鼓輪的設計。 10.4 歐拉圖與哈密爾頓圖第126頁/共237頁 【例10.4.2】設一個旋轉鼓的表面被分成16個部分，如圖10.4.6所示。其中每一部分分別由導體或絕緣體構成，圖中陰影部分表

57、示導體，空白部分表示絕緣體，絕緣體部分給出信號0，導體部分給出信號1。根據鼓輪轉動后所處的位置，4個觸頭a，b，c，d將獲得一定的信息。圖中所10.4 歐拉圖與哈密爾頓圖第127頁/共237頁 示的信息為1101，若將鼓輪沿順時針方向旋轉一格，則4個觸頭a，b，c，d獲得1010 。試問鼓輪上16個部分怎樣安排導體及絕緣體，才能使鼓輪每旋轉一格后，4 個觸頭得到的每組信息（共16組）均不相同？這個問題也即為：把16個二進制數字排成一個環形，使得4個依次相連的數字所組成的16個4位二進制數均不相同。10.4 歐拉圖與哈密爾頓圖第128頁/共237頁 解: 問題的答案是肯定的。下面談一下解決這個問

58、題的思路。 設i 0， 1 （i16）。 每旋轉一格，信號從1234轉到2345，前者的右 3 位決定了后者的左 3 位。于是，我們的想法是將這16個二進制數字的環形1216對應一個歐拉有向路，使其邊依次為1234，2345，3456， （圖10.4.7）。10.4 歐拉圖與哈密爾頓圖第129頁/共237頁 我們把234對應一個結點，它是弧1234的終點也是弧2345的始點。 這樣我們的問題就轉化為以位二進制數為結點作一個有向圖， 再在圖中找出歐拉回路。 10.4 歐拉圖與哈密爾頓圖第130頁/共237頁圖 10.4.610.4 歐拉圖與哈密爾頓圖第131頁/共237頁 圖 10.4.7 歐拉

59、有向路示圖 10.4 歐拉圖與哈密爾頓圖第132頁/共237頁 構造一個有個結點的有向圖G（圖10.4.8）。 其結點分別記為位二進制數000、001、010、 011、100、101、110、111。從結點123出發可引出兩條有向邊，其終點分別 是23 和23 ， 記 這 兩 條 有 向 邊 為123和123。 這樣圖G就有16條邊。 由于G中每點的入度等于出度都等于，故在圖中可找到一條歐拉回路。 10.4 歐拉圖與哈密爾頓圖第133頁/共237頁 例如（僅寫出邊的序列）e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8。 根據鄰接邊的標號記法， 這16個二進制數可

60、寫成對應的二進制序列0000100110101111， 把這個序列排成環狀， 與所求的鼓輪相對應， 如圖10.4.6所示。 該例可推廣到鼓輪有n個觸點的情況。 10.4 歐拉圖與哈密爾頓圖第134頁/共237頁 圖 10.4.8 具有 8 個結點的有向圖G 第135頁/共237頁 10.4.2 哈密爾頓圖 與歐拉回路類似的是哈密爾頓回路問題。 它是1859年哈密爾頓首先提出的一個 關 于 1 2 面 體 的 數 學 游 戲 ： 能 否 在 圖10.4.9中找到一個回路，使它含有圖中所有結點一次且僅一次？ 若把每個結點看成一座城市，連接兩個結點的邊看成是交通線，那么這個問題就變成能否找到一條旅行路線，使