左孝凌離散數(shù)學(xué)課件7-圖論

1、7.1 圖的基本概念7.2 路與回路7.3 圖的矩陣表示7.4 歐拉圖與漢密爾頓圖7.5 樹與生成樹7.6 根樹及其應(yīng)用習(xí)題七,第七章 圖論,7.1.1 圖的基本概念7.1.2 圖的結(jié)點的度數(shù)及其計算7.1.3 子圖和圖的同構(gòu),第七章 圖論7.1 圖的基本概念,7.1.1 圖的基本概念,1.圖的定義 現(xiàn)實世界中許多現(xiàn)象能用某種圖形表示,這種圖形是由一些點和一些連接兩點間的連線所組成。

2、 【例7.1.1】a，b，c，d4個籃球隊進(jìn)行友誼比賽。為了表示４個隊之間比賽的情況，我們作出圖7.1.1的圖形。在圖中４個小圓圈分別表示這４個籃球隊，稱之為結(jié)點。如果兩隊進(jìn)行過比賽，則在表示該隊的兩個結(jié)點之間用一條線連接起來，稱之為邊。這樣利用一個圖形使各隊之間的比賽情況一目了然。,第七章 圖論7.1 圖的基本概念,圖7.1.1,第七章 圖論7.1 圖的基本概念,第七章 圖論7.1 圖的基本

3、概念,如果圖7.1.1中的４個結(jié)點a，b，c，d分別表示４個人，當(dāng)某兩個人互相認(rèn)識時，則將其對應(yīng)點之間用邊連接起來。這時的圖又反映了這４個人之間的認(rèn)識關(guān)系。 我們也可以點代表工廠,以連接兩點的連線表示這兩工廠間有業(yè)務(wù)往來關(guān)系。這樣便可用圖形表示某一城市中各工廠間的業(yè)務(wù)往來關(guān)系。這種用圖形來表示事物之間的某種關(guān)系的方法我們也曾經(jīng)在第三章中使用過。對于這種圖形,我們的興趣在于有多少個點和哪些點對間有線連接,至于連線的長短曲直和點

4、的位置都無關(guān)緊要。對它們進(jìn)行數(shù)學(xué)抽象我們就得到以下作為數(shù)學(xué)概念的圖的定義。,定義7.1.1一個圖G是一個序偶〈V(G),E(G)〉，記為G＝〈V(G),E(G)〉。其中V(G)是非空結(jié)點集合，E(G)是邊集合，對E(G)中的每條邊，有V(G)中的結(jié)點的有序偶或無序偶與之對應(yīng)。 若邊e所對應(yīng)的結(jié)點對是有序偶,則稱e是有向邊。a叫邊e的始點,b叫邊e的終點,統(tǒng)稱為e的端點。若邊e所對應(yīng)的結(jié)點對是無序偶(a,b),則稱e是

5、無向邊。這時統(tǒng)稱e與兩個結(jié)點a和b互相關(guān)聯(lián)。我們將結(jié)點a、b的無序結(jié)點對記為(a，b)，有序結(jié)點對記為<a，b〉。 一個圖G可用一個圖形來表示且表示是不唯一的。,第七章 圖論7.1 圖的基本概念,【例7.1.2】設(shè)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

6、),e5=(d,c),e6=(a,d),e7=(b,b)。則圖G可用圖7.1.2(a)或(b)表示。,第七章 圖論7.1 圖的基本概念,圖7.1.2,第七章 圖論7.1 圖的基本概念,圖7.1.2,第七章 圖論7.1 圖的基本概念,2.圖G的結(jié)點與邊之間的關(guān)系鄰接點:同一條邊的兩個端點。孤立點:沒有邊與之關(guān)聯(lián)的結(jié)點。鄰接邊:關(guān)聯(lián)同一個結(jié)點的兩條邊。孤立邊:不與任何邊相鄰接的邊。自回路（環(huán)）：關(guān)聯(lián)

7、同一個結(jié)點的一條邊（（v，v）或〈v，v〉）。平行邊(多重邊):關(guān)聯(lián)同一對結(jié)點的多條邊。,第七章 圖論7.1 圖的基本概念,如例7.1.1中的圖，結(jié)點集V＝{a，b，c，d}，邊集E＝{e1，e2，e3，e4，e5}，其中e1＝（a，b），e2＝（a，c），e3＝（a，d），e4＝（b，c），e5＝（c，d）。d與a、d與c是鄰接的，但d與b不鄰接，邊e3與e5是鄰接的。,第七章 圖論7.1 圖的基本概念,【

8、例7.1.3】設(shè)圖G＝〈V,E〉如圖7.1.3所示。這里V＝{v1，v2，v3}，E＝{e1，e2，e3，e4，e5}，其中e1＝（v1，v2），e2＝（v1，v3），e3＝（v3，v3），e4＝（v2，v3），e5＝（v2，v3）。在這個圖中，e3是關(guān)聯(lián)同一個結(jié)點的一條邊,即自回路；邊e4和e5都與結(jié)點v2、v3關(guān)聯(lián)，即它們是多重邊。,第七章 圖論7.1 圖的基本概念,圖7.1.3,第七章 圖論7.1

9、圖的基本概念,3.圖G的分類按G的結(jié)點個數(shù)和邊數(shù)分為(n,m)圖,即n個結(jié)點,m條邊的圖;特別地,(n,0)稱為零圖,(1,0)圖稱為平凡圖。(2)按G中關(guān)聯(lián)于同一對結(jié)點的邊數(shù)分為多重圖和簡單圖;多重圖:含有平行邊的圖（如圖7.1.3）。簡單圖:不含平行邊和自環(huán)的圖。(3)按G的邊有序、無序分為有向圖、無向圖和混合圖;有向圖：每條邊都是有向邊的圖稱為有向圖（圖7.1.4(b))；無向圖：每條邊都是無向邊的圖稱為無向圖；

10、混合圖：既有無向邊，又有有向邊的圖稱為混合圖。本書主要研究無向圖和有向圖。,(a)(b)(4)按G的邊旁有無數(shù)量特征分為邊權(quán)圖(如圖7.1.4(a))、無權(quán)圖;(5)按G的任意兩個結(jié)點間是否有邊分為完全圖Kn(如圖7.1.5)和不完全圖(如圖7.1.6)。,圖7.1.4,圖7.1.6,完全圖：任意兩個不同的結(jié)點都是鄰接的簡單圖稱為完全圖。n個結(jié)點的無向完全圖記為Kn。圖7.1.5給出了K3和K4。從圖中可以看出K3有３條邊，

11、K4有６條邊。容易證明Kn有條邊。,圖7.1.5K3與K4示意圖,第七章 圖論7.1 圖的基本概念,給定任意一個含有n個結(jié)點的圖G,總可以把它補(bǔ)成一個具有同樣結(jié)點的完全圖,方法是把那些缺少的邊添上。 定義7.1.2設(shè)G＝〈V,E〉是一個具有n個結(jié)點的簡單圖。以V為結(jié)點集，以從完全圖Kn中刪去G的所有邊后得到的圖（或由G中所有結(jié)點和所有能使G成為完全圖的添加邊組成的圖）稱為G的補(bǔ)圖，記為。

12、 例如，零圖和完全圖互為補(bǔ)圖。 圖7.1.6給出了一個圖G和G的補(bǔ)圖。,第七章 圖論7.1 圖的基本概念,【例7.1.4】（拉姆齊問題）試證在任何一個有６個人的組里，存在３個人互相認(rèn)識，或者存在３個人互相不認(rèn)識。 我們用６個結(jié)點來代表人，并用鄰接性來代表認(rèn)識關(guān)系。這樣一來，該例就是要證明：任意一個有６個結(jié)點的圖G中，或者有３個互相鄰接的點，或者有３個互相不鄰接的點。即，對任何一個有６

13、個結(jié)點的圖G，G或中含有一個三角形（即K3）。,第七章 圖論7.1 圖的基本概念,證明:設(shè)G＝〈V,E〉，|V|＝6，v是G中一結(jié)點。因為v與G的其余５個結(jié)點或者在中鄰接，或者在G中鄰接。故不失一般性可假定，有３個結(jié)點v1，v2，v3在G中與v鄰接。 如果這３個結(jié)點中有兩個結(jié)點（如v1，v2）鄰接，則它們與v3就是G中一個三角形的３個頂點。如果這3個結(jié)點中任意兩個在G中均不鄰接，則v1，v2，v3就是中一

14、個三角形的３個頂點。,第七章 圖論7.1 圖的基本概念,7.1.2圖的結(jié)點的度數(shù)及其計算 我們常常需要關(guān)心圖中有多少條邊與某一結(jié)點關(guān)聯(lián)，這就引出了圖的一個重要概念——結(jié)點的度數(shù)。 定義7.1.3圖中結(jié)點v所關(guān)聯(lián)的邊數(shù)（有自回路時計算兩次）稱為結(jié)點v的度數(shù)，記為deg（v）。 如圖7.1.3中的deg（v1）＝2，deg（v2）＝3，deg（v3）＝5。,第七章

15、 圖論7.1 圖的基本概念,定理7.1.1圖G＝〈V,E〉中結(jié)點度數(shù)的總和等于邊數(shù)的兩倍，即,證明:因為每條邊都與兩個結(jié)點關(guān)聯(lián)，所以加上一條邊就使得各結(jié)點度數(shù)的和增加2，由此結(jié)論成立。推論:圖G中度數(shù)為奇數(shù)的結(jié)點必為偶數(shù)個。,第七章 圖論7.1 圖的基本概念,證明:設(shè)V1和V2分別是G中奇數(shù)度數(shù)和偶數(shù)度數(shù)的結(jié)點集。 由定理7.1.1知,由于 是偶數(shù)之和，必為偶數(shù)，而2|E|也為偶數(shù)

16、，故 是偶數(shù)。由此|V1|必為偶數(shù)。,第七章 圖論7.1 圖的基本概念,定義7.1.4在有向圖中,射入結(jié)點v的邊數(shù)稱為結(jié)點v的入度，記為 ;由結(jié)點v射出的邊數(shù)稱為結(jié)點v的出度，記為 。結(jié)點v的入度與出度之和就是結(jié)點v的度數(shù)。 如圖7.1.4中 ＝1， ＝2。,圖7.1.4,定理7.1

17、.2在任何有向圖G＝〈V,E〉中，有,第七章 圖論7.1 圖的基本概念,7.1.3子圖和圖的同構(gòu)1.子圖在研究和描述圖的性質(zhì)時，子圖的概念占有重要地位。定義7.1.5設(shè)有圖G＝〈V,E〉和圖G′＝〈V′,E′〉。1)若V′?V，E′?E，則稱G′是G的子圖。2)若G′是G的子圖，且E′≠E，則稱G′是G的真子圖。,第七章 圖論7.1 圖的基本概念,3)若V′＝V，E′?E，則稱G′是G的生成子圖。圖7.

18、1.7給出了圖G以及它的真子圖G1和生成子圖G2。,圖7.1.7圖G以及其真子圖G1和生成子圖G2,第七章 圖論7.1 圖的基本概念,2.圖的同構(gòu) 從圖的定義可以看出，圖的最本質(zhì)的內(nèi)容是結(jié)點與結(jié)點的鄰接關(guān)系。例如例7.1.1也可以用圖7.1.8中幾種不同形狀的圖形表示。它們與圖7.1.1一樣，都同樣表示例7.1.1中４個隊之間的比賽情況。從這個意義上講，我們說它們是同一個圖，并稱圖7.1.1與圖7.1.8

19、的(a)和(b)是同構(gòu)的。,第七章 圖論7.1 圖的基本概念,圖7.1.8同構(gòu)的圖,圖7.1.9,圖7.1.1,第七章 圖論7.1 圖的基本概念,定義7.1.6設(shè)有圖G＝〈V,E〉和圖G′＝〈V′,E′〉。如果存在雙射ｇ：V→V′，使得e＝（u，v）∈Eiffe′＝（ｇ(u)，ｇ(v)）∈E′，且（u，v）與（ｇ(u)，ｇ(v)）有相同的重數(shù)，則稱G與G′同構(gòu)。記作G≌G′。 【例7.1.5】考察圖

20、7.1.9中的兩個圖G＝〈V,E〉和G′＝〈V′,E′〉。,第七章 圖論7.1 圖的基本概念,顯然，定義ｇ：V→V′，ｇ（vi）＝vi′，可以驗證ｇ是滿足定義7.1.6的雙射，所以G≌G′。 對于同構(gòu)，形象地說，若圖的結(jié)點可以任意挪動位置，而邊是完全彈性的，只要在不拉斷的條件下，這個圖可以變形為另一個圖，那么這兩個圖是同構(gòu)的。故同構(gòu)的兩個圖從外形上看可能不一樣，但它們的拓?fù)浣Y(jié)構(gòu)是一樣的。,第七章 圖

21、論7.1 圖的基本概念,小結(jié):本結(jié)介紹了圖的基本概念、圖的結(jié)點的度數(shù)及其性質(zhì)以及子圖、生成子圖與圖的同構(gòu)等概念。 重點：圖的結(jié)點的度數(shù)及其性質(zhì)以及生成子圖的概念。,第七章 圖論7.1 圖的基本概念,7.2.1路與回路7.2.2圖的連通性,第七章 圖論7.2 路與回路,定義7.2.1給定圖G＝〈V,E〉,設(shè)v0,v1,…,vk∈V，e1，e2，…，ek∈E，其中ei是關(guān)聯(lián)于結(jié)點vi-1和vi的

22、邊，稱交替序列v0e1v1e2…ekvk為連接v0到vk的路，v0和vk分別稱為路的起點與終點。路中邊的數(shù)目k稱作路的長度。當(dāng)v0=vk時,這條路稱為回路。 在簡單圖中一條路v0e1v1e2…ekvk由它的結(jié)點序列v0v1…vk確定,所以簡單圖的路,可表示為v0v1…vk。如圖7.1.1表示的簡單圖中，路ae1be4ce5d可寫成abcd。,第七章 圖論7.2 路與回路,定義7.2.2設(shè)μ＝v0e1v1e

23、2…ekvk是圖G中連接v0到vk的路。 1)若e1，e2，…，ek都不相同，則稱路μ為跡； 2)若v0，v1，…，vk都不相同，則稱路μ為通路； 3)長度大于２的閉的通路（即除v0＝vk外，其余結(jié)點均不相同的路）μ稱作圈。,圖7.1.1,第七章 圖論7.2 路與回路,例如在圖7.2.1中，有連接v5到v3的路v5e8v4e5v2e6v5e7v3，這也是一條跡

24、；路v1e1v2e3v3是一條通路；路v1e1v2e3v3e4v2e1v1是一條回路，但不是圈；路v1e1v2e3v3e2v1是一條回路，也是圈。 下面我們利用通路的概念解決一個古老的著名問題。,圖7.2.1,第七章 圖論7.2 路與回路,【例7.2.1】（渡河問題）一個擺渡人，要把一只狼、一只羊和一捆干草運過河去，河上有一只木船，每次除了人以外，只能帶一樣?xùn)|西。另外，如果人不在旁時，狼就要吃羊，羊就要吃

25、干草。問這人怎樣才能把它們運過河去？ 【游戲】 解 用F表示擺渡人，W表示狼，S表示羊，H表示干草。,第七章 圖論7.2 路與回路,若用FWSH表示人和其它３樣?xùn)|西在河的左岸的狀態(tài)。這樣在左岸全部可能出現(xiàn)的狀態(tài)為以下16種： FWSH FWS FWH FSH WSH FW FS FH WS

26、 WH SH F W S H φ 這里φ表示左岸是空集，即人、狼、羊、干草都已運到右岸去了。,第七章 圖論7.2 路與回路,根據(jù)題意檢查一下就可以知道，這16種情況中有6種情況是不允許出現(xiàn)的。它們是：WSH、FW、FH、WS、SH、F。如FH表示人和干草在左岸，而狼和羊在右岸，這當(dāng)然是不行的。因此，

27、允許出現(xiàn)的情況只有10種。,第七章 圖論7.2 路與回路,我們構(gòu)造一個圖，它的結(jié)點就是這10種狀態(tài)。若一種狀態(tài)可以轉(zhuǎn)移到另一種狀態(tài)，就在表示它們的兩結(jié)點間連一條邊，這樣就畫出圖7.2.2。本題就轉(zhuǎn)化為找結(jié)點FWSH到結(jié)點φ的通路。從圖中得到兩條這樣的通路，即有兩種渡河方案。,第七章 圖論 7.2 路與回路,圖7.2.2,第七章 圖論 7.2 路與回路,定義7.2.2在圖G中，若結(jié)點vi到vj有路連接（這時稱

28、vi和vj是連通的），其中長度最短的路的長度稱為vi到vj的距離，用符號d(vi,vj)表示。若從vi到vj不存在路徑,則d(vi,vj)=∞。 例如在圖7.2.1中，ｄ（v1，v4）＝２。 注意:在有向圖中,d(vi,vj)不一定等于d(vj,vi),但一般地滿足以下性質(zhì): (1) d(vi,vj)≥0; (2) d(vi,vi)=0;

29、 (3) d(vi,vj)+d(vj,vk)≥d(vi,vk)。,第七章 圖論 7.2 路與回路,定理7.2.1 設(shè)G是具有n個結(jié)點的圖，如果從結(jié)點v1到另一結(jié)點v2存在一條路，則從結(jié)點v1到v2必存在一條路長度不大于n－1的通路。 證明: 假定從v1到v2存在一條路徑,(v1,…,vi,…,v2)是所經(jīng)的結(jié)點,如果其中有相同的結(jié)點vk,例 (v1,…,vi,…,vk,…,vk,…,v2),則刪

30、去從vk到vk的這些邊,它仍是從v1到v2的路徑,如此反復(fù)地進(jìn)行直至(v1,…,vi,…,v2)中沒有重復(fù)結(jié)點為止。此時,所得的就是通路。通路的長度比所經(jīng)結(jié)點數(shù)少1,圖中共n個結(jié)點,故通路長度不超過n-1。 推論 設(shè)圖G＝〈V,E〉，|V|＝n，則G中任一圈長度不大于n。,7.2.2圖的連通性 1.無向圖的連通性 定義7.2.3在無向圖如果一個圖的任何兩個結(jié)點之間都有一條路

31、，那么我們稱這個圖是連通的，否則是不連通的。 定義7.2.4圖G的一個連通的子圖G′（稱為連通子圖）若不包含在G的任何更大的連通子圖中，它就被稱作G的連通分支。我們把圖G的連通分支數(shù)記作W（G）。,第七章 圖論 7.2 路與回路,圖7.2.3圖G與G′,在圖7.2.3中，G是不連通的，W（G）＝２，而G′是連通的，W（G′）＝１。任何一個圖都可劃分為若干個連通分支。顯然，僅當(dāng)圖G的連通分支數(shù)W（G）＝１

32、時，圖G是連通的。,第七章 圖論 7.2 路與回路,2.有向圖的連通性定義7.2.5在有向圖中,如果若從結(jié)點u到v有一條路，則稱u可達(dá)v。定義7.2.6設(shè)有有向圖G，1)若G的任意兩個結(jié)點中,至少從一個結(jié)點可達(dá)另一個結(jié)點,則稱圖G是單向連通的;2)如果G的任意兩個結(jié)點都是相互可達(dá)的,則稱圖G是強(qiáng)連通的;3)如果略去邊的方向后，G成為連通的無向圖，則稱圖G是弱連通的。,從定義可知：若圖G是單向連通的，則必是弱連通的

33、；若圖G是強(qiáng)連通的，則必是單向連通的，且也是弱連通的。但反之不真。 在圖7.2.4中,(a)是強(qiáng)連通的,(b)是單向連通的,(c)是弱連通的。,第七章 圖論 7.2 路與回路,圖7.2.4,第七章 圖論 7.2 路與回路,定理7.2.2 一個有向圖G是強(qiáng)連通的，當(dāng)且僅當(dāng)G中有一個（有向）回路，它至少包含每個結(jié)點一次。 證明:必要性：如果有向圖G是強(qiáng)連通的，則任意兩個結(jié)點都是相互可達(dá)的。故必可作

34、一回路經(jīng)過圖中所有各結(jié)點。否則必有一回路不包含某一結(jié)點v。這樣，v與回路上各結(jié)點就不能相互可達(dá)，這與G是強(qiáng)連通矛盾。 充分性：如果G中有一個回路，它至少包含每個結(jié)點一次，則G中任意兩個結(jié)點是相互可達(dá)的，故G是強(qiáng)連通的。 例如，圖7.2.4(a)中有一回路v1v3v2v1，它包含圖中所有結(jié)點。,定義7.2.6 在有向圖G=〈V,E〉中,G′是G的子圖,若G′是強(qiáng)連通的(單向連通的,弱連通的),沒有包含G′的更大

35、子圖G″是強(qiáng)連通的(單向連通的,弱連通的),則稱G′是G的強(qiáng)分圖(單向分圖,弱分圖)。 在圖7.2.5中,強(qiáng)分圖集合是: {〈{1,2,3},{e1,e2,e3}〉,〈{4},φ〉,〈{5},φ〉,〈{6},φ〉,〈{7,8},{e7,e8}〉},第七章 圖論 7.2 路與回路,單向分圖集合是:{〈{1,2,3,4,5},{e1,e2,e3,e4,e5}〉,〈{6,5},{e6}〉,〈{7,8},{e

36、7,e8}〉}弱分圖集合是:{〈{1,2,3,4,5,6},{e1,e2,e3,e4,e5,e6}〉,〈{7,8},{e7,e8}〉},第七章 圖論 7.2 路與回路,圖7.2.5,第七章 圖論 7.2 路與回路,小結(jié):本結(jié)介紹了路、跡、通路、回路、圈及圖的連通性。,第七章 圖論 7.2 路與回路,7.3.1 鄰接矩陣7.3.2 可達(dá)性矩陣,第七章 圖論 7.3 圖的矩陣表示,7.3.1鄰

37、接矩陣,上面我們介紹了圖的一種表示方法，即用圖形表示圖。它的優(yōu)點是形象直觀，但是這種表示在結(jié)點與邊的數(shù)目很多時是不方便的。下面我們提供另一種用矩陣表示圖的方法。利用這種方法，我們能把圖用矩陣存儲在計算機(jī)中，利用矩陣的運算還可以了解到它的一些有關(guān)性質(zhì)。,第七章 圖論 7.3 圖的矩陣表示,定義7.3.1設(shè)G＝〈V,E〉是有n個結(jié)點的簡單圖，則n階方陣Ａ＝（aij）稱為G的鄰接矩陣。其中,否則,如圖7.3.1所示的圖G，其鄰接矩陣

38、A為,第七章 圖論 7.3 圖的矩陣表示,如圖7.3.1所示的圖G，其鄰接矩陣A為,顯然無向圖的鄰接矩陣必是對稱的。下面的定理說明，在鄰接矩陣A的冪A2，A3，…等矩陣中，每個元素有特定的含義。,圖7.3.1圖G,定理7.3.1設(shè)G是具有n個結(jié)點｛v1,v2,…,vn｝的圖，其鄰接矩陣為A，則Ak（k＝1，2，…）的（i，j）項元素a(k)ij是從vi到vj的長度等于k的路的總數(shù)。證明:施歸納于k。當(dāng)k＝1時，A1＝A，

39、由A的定義，定理顯然成立。若k＝l時定理成立，則當(dāng)k＝l＋1時，Al+1＝Al·A，,所以,根據(jù)鄰接矩陣定義arj是聯(lián)結(jié)vr和vj的長度為1的路數(shù)目,a(l)ir是聯(lián)結(jié)vi和vr的長度為l的路數(shù)目,故上式右邊的每一項表示由vi經(jīng)過l條邊到vr,再由vr經(jīng)過1條邊到vj的總長度為l+1的路的數(shù)目。對所有r求和,即得a(l+1)ij是所有從vi到vj的長度等于l+1的路的總數(shù),故命題對l+1成立。,第七章 圖論 7.3

40、 圖的矩陣表示,由定理7.3.1可得出以下結(jié)論：1)如果對l＝1，2，…，n-1，Al的（i，j）項元素（i≠j）都為零，那么vi和vj之間無任何路相連接，即vi和vj不連通。因此，vi和vj必屬于G的不同的連通分支。2)結(jié)點vi到vj（i≠j）間的距離d（vi，vj）是使Al（l＝1，2，…，n-1）的（i，j）項元素不為零的最小整數(shù)l。3)Al的（i，i）項元素a(l)ii表示開始并結(jié)束于vi長度為l的回路的數(shù)目。,第七章

41、 圖論 7.3 圖的矩陣表示,【例7.3.1】圖G＝〈V,E〉的圖形如圖7.3.2，求鄰接矩陣A和A2，A3，A4，并分析其元素的圖論意義。解:,圖7.3.2,第七章 圖論 7.3 圖的矩陣表示,1)由A中a(1)12＝1知，v1和v2是鄰接的；由A3中a(3)12＝2知，v1到v2長度為3的路有兩條，從圖中可看出是v1v2v1v2和v1v2v3v2。2)由A2的主對角線上元素知，每個結(jié)點都有長度為２的回路，其中結(jié)

42、點v2有兩條：v2v1v2和v2v3v2，其余結(jié)點只有一條。3)由于A3的主對角線上元素全為零，所以G中沒有長度為３的回路。,第七章 圖論 7.3 圖的矩陣表示,4)由于 所以結(jié)點v3和v4間無路，它們屬于不同的連通分支。5)d（v1，v3）＝２。對其他元素讀者自己可以找出它的意義。,7.3.2可達(dá)性矩陣,下面用矩陣來研究有向圖的可達(dá)性。

43、與無向圖一樣，有向圖也能用相應(yīng)的鄰接矩陣A＝（aij）表示，其中,但注意這里A不一定是對稱的。,第七章 圖論 7.3 圖的矩陣表示,定義7.3.2 設(shè)G＝〈V,E〉是一個有n個結(jié)點的有向圖，則n階方陣P＝（pij）稱為圖G的可達(dá)性矩陣。其中,(vi到vj可達(dá)),(否則),根據(jù)可達(dá)性矩陣，可知圖中任意兩個結(jié)點之間是否至少存在一條路以及是否存在回路。由7.2節(jié)定理7.2.1可知，利用有向圖的鄰接矩陣A，分以下兩步可得到可達(dá)性矩

44、陣。,第七章 圖論 7.3 圖的矩陣表示,1)令Bn＝A＋A2＋…＋An,2)將矩陣Ｂn中不為零的元素均改為１，為零的元素不變，所得的矩陣P就是可達(dá)性矩陣。當(dāng)n很大時，這種求可達(dá)性矩陣的方法就很復(fù)雜。下面再介紹一種更簡便的求可達(dá)性矩陣的方法。,第七章 圖論 7.3 圖的矩陣表示,因可達(dá)性矩陣是一個元素僅為１或０的矩陣（稱為布爾矩陣），而在研究可達(dá)性問題時，我們對于兩個結(jié)點間具有路的數(shù)目并不感興趣，所關(guān)心的只是兩結(jié)

45、點間是否有路存在。因此，我們可將矩陣A，A2,…,An,分別改為布爾矩陣A(1)，A(2)，…，A(n)。,第七章 圖論 7.3 圖的矩陣表示,由此有A(2)＝A(1)∧A(1)＝A∧AA(3)＝A(2)∧A(1)……A(n)＝A(n-1)∧A(1)P＝A(1)∨A(2)∨…∨A(n)相應(yīng)的矩陣加法和乘法稱為矩陣的布爾加∨和布爾乘∧。,第七章 圖論 7.3 圖的矩陣表示,圖7.3.3,第七章

46、圖論 7.3 圖的矩陣表示,【例7.3.2】求出圖7.3.3所示圖的可達(dá)性矩陣。解:該圖的鄰接矩陣為,第七章 圖論 7.3 圖的矩陣表示,故,定理7.3.2 有向圖G是強(qiáng)連通的當(dāng)且僅當(dāng)其可達(dá)性矩陣P除主對角線外，其它元素均為１。,第七章 圖論 7.3 圖的矩陣表示,小結(jié)：本節(jié)介紹了圖的鄰接矩陣、可達(dá)性矩陣的概念。重點:掌握鄰接矩陣、可達(dá)性矩陣及由vi到vj長度為k的路徑的條數(shù)的求法。,,,,第七章

47、圖論 7.3 圖的矩陣表示,7.4.1 歐拉圖7.4.2 漢密爾頓圖,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,7.4.1歐拉圖 歷史上的哥尼斯堡七橋問題是著名的圖論問題。 問題是這樣的：18世紀(jì)的東普魯士有個哥尼斯堡城，在橫貫全城的普雷格爾河兩岸和兩個島之間架設(shè)了7座橋，它們把河的兩岸和兩個島連接起來（如圖7.4.1）。,第七章 圖論 7.4 歐拉圖與漢密

48、爾頓圖,每逢假日，城中居民進(jìn)行環(huán)城游玩，人們對此提出了一個“遍游”問題，即能否有這樣一種走法，使得從某地出發(fā)通過且只通過每座橋一次后又回到原地呢？ 我們將圖7.4.1中的哥尼斯堡城的4塊陸地部分分別標(biāo)以A，B，Ｃ，D，將陸地設(shè)想為圖的結(jié)點，而把橋畫成相應(yīng)的連接邊，這樣圖7.4.1可簡化成圖7.4.2。于是七橋“遍游”問題等價于在圖7.4.2中，從某一結(jié)點出發(fā)找到一條回路，通過它的每條邊一次且僅一次，并回到原來

49、的結(jié)點。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,圖7.4.1哥尼斯堡七橋問題示圖,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,圖7.4.2哥尼斯保七橋問題簡化圖,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,定義7.5.1 給定無孤立結(jié)點的圖G，若存在一條經(jīng)過G中每邊一次且僅一次的回路，則該回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖。 例如，給出如圖7.4.3所示的兩個圖，容易

50、看出，(a)是歐拉圖，而(b)不是歐拉圖。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,圖7.4.3,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,定理7.5.1連通圖G是歐拉圖的充要條件是G的所有結(jié)點的度數(shù)都是偶數(shù)。 證明:必要性：設(shè)G是一歐拉圖，α是G中的一條歐拉回路。當(dāng)α通過G的任一結(jié)點時，必通過關(guān)聯(lián)于該點的兩條邊。又因為G中的每條邊僅出現(xiàn)一次，所以α所通過的每個結(jié)點的度數(shù)必定是偶數(shù)。,第

51、七章 圖論 7.4 歐拉圖與漢密爾頓圖,圖7.4.4圖G,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,充分性：我們可以這樣來作一個閉跡β，假設(shè)它從某結(jié)點A開始，沿著一條邊到另一結(jié)點，接著再從這個結(jié)點，沿沒有走過的邊前進(jìn)，如此繼續(xù)下去。因為我們總是沿著先前沒有走過的新邊走，又由于圖G的邊數(shù)有限，所以這個過程一定會停止。但是，因為每一個結(jié)點都與偶數(shù)條邊關(guān)聯(lián)，而當(dāng)沿β前進(jìn)到達(dá)結(jié)點v時，若v≠A，β走過了與v關(guān)聯(lián)的奇數(shù)條邊

52、，這樣在v上總還有一條沒有走過的邊。因此，β必定返回停止在A（見圖7.4.4）。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,如果β走遍了G的所有邊，那么我們就得到所希望的一條歐拉回路。如果不是這樣，那么在β上將有某一結(jié)點B，與它關(guān)聯(lián)的一些邊尚未被β走過（因G連通）。但是，實際上，因為β走過了與B關(guān)聯(lián)的偶數(shù)條邊，因此不屬于β的與B關(guān)聯(lián)的邊也是偶數(shù)條。對于其他有未走過邊所關(guān)聯(lián)的所有結(jié)點來說，上面的討論同樣正確。于是若設(shè)G1是G－

53、β的包含點B的一個連通分支，則G1的結(jié)點全是偶數(shù)度結(jié)點。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,運用上面的討論，我們在G1中得到一個從B點出發(fā)的一條閉跡β1。這樣我們就得到了一條更大的閉跡，它是從A點出發(fā)沿β前進(jìn)到達(dá)B，然后沿閉跡β1回到B，最后再沿β由B走到A。如果我們?nèi)匀粵]有走遍整個圖，那么我們再次把閉跡擴(kuò)大，以此類推，直到最后得到一個歐拉回路。 由于在七橋問題的圖7.4.2中，有４個點是奇

54、數(shù)度結(jié)點，故不存在歐拉回路，七橋問題無解。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,在圖7.2.3中，(a)圖的每個結(jié)點的度數(shù)都為４，所以它是歐拉圖；(b)圖不是歐拉圖。但我們繼續(xù)考察(b)圖可以發(fā)現(xiàn)，該圖中有一條路v2v3v4v5v2v1v5，它經(jīng)過(b)圖中的每條邊一次且僅一次，我們把這樣的路稱為歐拉路(非歐拉回路)。 定義7.5.2 通過圖G的每條邊一次且僅一次的路稱為圖G的歐拉路。對于歐拉

55、路有下面的判定方法。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,定理7.5.2連通圖G具有一條連接結(jié)點vi和vj的歐拉路當(dāng)且僅當(dāng)vi和vj是G中僅有的奇數(shù)度結(jié)點。證明:將邊(vi，vj)加于圖G上，令其所得的圖為G′（可能是多重圖）。由定理7.5.1知：G有連接結(jié)點vi和vj的歐拉路，iffG′有一條歐拉回路，iffG′的所有結(jié)點均為偶度結(jié)點，iffG的所有結(jié)點除vi和vj外均為偶度結(jié)點，iffvi和vj是G中

56、僅有的奇度結(jié)點。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,我國民間很早就流傳一種“一筆畫”游戲。由定理7.5.1和定理7.5.2知，有兩種情況可以一筆畫。 1)如果圖中所有結(jié)點是偶數(shù)度結(jié)點，則可以任選一點作為始點一筆畫完； 2)如果圖中只有兩個奇度結(jié)點，則可以選擇其中一個奇度結(jié)點作為始點也可一筆畫完。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,【例7.4.1】圖7.4.5(a)是一幢房子

57、的平面圖形，前門進(jìn)入一個客廳，由客廳通向4個房間。如果要求每扇門只能進(jìn)出一次，現(xiàn)在你由前門進(jìn)去，能否通過所有的門走遍所有的房間和客廳，然后從后門走出。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,圖7.4.5,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,解:將4個房間和一個客廳及前門外和后門外作為結(jié)點，若兩結(jié)點有邊相連就表示該兩結(jié)點所表示的位置有一扇門相通。由此得圖7.4.5(b)。由于圖中有4個結(jié)點是奇度結(jié)點，故由

58、定理7.5.2知本題無解。類似于無向圖的結(jié)論，對有向圖有以下結(jié)果。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,定理7.5.3一個連通有向圖具有（有向）歐拉回路的充要條件是圖中每個結(jié)點的入度等于出度。一個連通有向圖具有有向歐拉路的充要條件是最多除兩個結(jié)點外的每個結(jié)點的入度等于出度，但在這兩個結(jié)點中，一個結(jié)點的入度比出度大1，另一個結(jié)點的入度比出度少1。下面舉一個有趣的例子是計算機(jī)鼓輪的設(shè)計。,第七章 圖論 7.4

59、 歐拉圖與漢密爾頓圖,【例7.4.1】設(shè)一個旋轉(zhuǎn)鼓的表面被分成24個部分，如圖7-26所示。其中每一部分分別由導(dǎo)體或絕緣體構(gòu)成，圖中陰影部分表示導(dǎo)體，空白部分表示絕緣體，絕緣體部分給出信號0，導(dǎo)體部分給出信號1。根據(jù)鼓輪轉(zhuǎn)動后所處的位置，4個觸頭a，b，c，d將獲得一定的信息。圖中所示的信息為1101，若將鼓輪沿順時針方向旋轉(zhuǎn)一格，則4個觸頭a，b，c，d獲得1010。試問鼓輪上16個部分怎樣安排導(dǎo)體及絕緣體，才能使鼓輪每旋轉(zhuǎn)一格后，

60、4個觸頭得到的每組信息（共16組）均不相同？這個問題也即為：把16個二進(jìn)制數(shù)字排成一個環(huán)形，使得4個依次相連的數(shù)字所組成的16個4位二進(jìn)制數(shù)均不相同。,圖7.4.6,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,解:問題的答案是肯定的。下面談一下解決這個問題的思路。 設(shè)αi∈｛0，1｝（i∈Ｎ16）。每旋轉(zhuǎn)一格，信號從α1α2α3α4轉(zhuǎn)到α2α3α4α5，前者的右3位決定了后者的左3位。于是，我們的想法

61、是將這16個二進(jìn)制數(shù)字的環(huán)形α1α2…α16對應(yīng)一個歐拉有向路，使其邊依次為α1α2α3α4，α2α3α4α5，α3α4α5α6，…（圖7―27）。我們把α2α3α4對應(yīng)一個結(jié)點，它是弧α1α2α3α4的終點也是弧α2α3α4α5的始點。這樣我們的問題就轉(zhuǎn)化為以３位二進(jìn)制數(shù)為結(jié)點作一個有向圖，再在圖中找出歐拉回路。,圖7.4.7歐拉有向路示圖,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,構(gòu)造一個有８個結(jié)點的有向圖G（圖7―28

62、）。其結(jié)點分別記為３位二進(jìn)制數(shù)000、001、010、011、100、101、110、111。從結(jié)點α1α2α3出發(fā)可引出兩條有向邊，其終點分別是α2α3０和α2α3１，記這兩條有向邊為α1α2α3０和α1α2α3１。這樣圖G就有16條邊。由于G中每點的入度等于出度都等于２，故在圖中可找到一條歐拉回路。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,例如（僅寫出邊的序列）e0e1e2e4e9e3e6e13e10e5e11e7e1

63、5e14e12e8。根據(jù)鄰接邊的標(biāo)號記法，這16個二進(jìn)制數(shù)可寫成對應(yīng)的二進(jìn)制序列0000100110101111，把這個序列排成環(huán)狀，與所求的鼓輪相對應(yīng)，如圖7.4.6所示。 該例可推廣到鼓輪有n個觸點的情況。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,圖7.4.8具有8個結(jié)點的有向圖G,7.4.2漢密爾頓圖 與歐拉回路類似的是漢密爾頓回路問題。它是1859年漢密爾頓首先提出的一個關(guān)于12面體

64、的數(shù)學(xué)游戲：能否在圖7.4.9中找到一個回路，使它含有圖中所有結(jié)點一次且僅一次？若把每個結(jié)點看成一座城市，連接兩個結(jié)點的邊看成是交通線，那么這個問題就變成能否找到一條旅行路線，使得沿著該旅行路線經(jīng)過每座城市恰好一次，再回到原來的出發(fā)地呢？為此，這個問題也被稱作周游世界問題。,圖7.4.9 12面體游戲示圖,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,對圖7.4.9，圖中粗線給出了這樣的回路。 定義

65、7.5.3 給定圖G，若有一條路通過G中每個結(jié)點恰好一次，則這樣的路稱為漢密爾頓路；若有一個圈，通過G個每個結(jié)點恰好一次，這樣的圈稱為漢密爾頓回路（或漢密爾頓圈）。具有漢密爾頓回路的圖稱為漢密爾頓圖。 盡管漢密爾頓回路與歐拉回路問題在形式上極為相似，但是到目前為止還不知道一個圖為漢密爾頓圖的充要條件，尋找該充要條件仍是圖論中尚未解決的主要問題之一。下面先給出一個簡單而有用的必要條件。,第七章 圖論 7

66、.4 歐拉圖與漢密爾頓圖,定理7.5.4設(shè)圖G＝〈V,E〉是漢密爾頓圖，則對于V的每個非空子集S，均有W（G－S）≤|S|成立，其中W（G－S）是圖G－S的連通分支數(shù)。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,證明:設(shè)α是G的漢密爾頓回路，S是V的任一非空子集。在G－S中，α最多被分為|S|段，所以W（G－S）≤|S|利用本定理可判別某些圖不為漢密爾頓圖。如在圖7.4.10中，若取S＝｛v1，v4｝，則G－S有

67、3個連通分支，故該圖不是漢密爾頓圖。判斷漢密爾頓圖的充分條件很多，我們僅介紹其中一個。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,圖7.4.10,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,定理7.5.5設(shè)G＝〈V,E〉是有n個結(jié)點的簡單圖，1）如果任兩結(jié)點u，v∈V，均有deg(u)＋deg(v)≥n－1，則在G中存在一條漢密爾頓路；2）如果對任兩結(jié)點u，v∈V，均有deg(u)＋deg(v)≥n，

68、則G是漢密爾頓圖。證明略。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,【例7.4.2】某地有５個風(fēng)景點。若每個景點均有兩條道路與其他景點相通，問是否可經(jīng)過每個景點恰好一次而游完這５處？解將景點作為結(jié)點，道路作為邊，則得到一個有５個結(jié)點的無向圖。由題意，對每個結(jié)點vi，有deg(vi)＝2（i∈Ｎ5）。則對任兩點vi，vj（i，j∈Ｎ5）均有deg(vi)＋deg(vj)＝2＋2＝4＝5－1可知此圖一定有一條漢密爾頓

69、路，本題有解。,第七章 圖論 7.4 歐拉圖與漢密爾頓圖,我們再通過一個例子，介紹一個判別漢密爾頓路不存在的標(biāo)號法?！纠?.4.3】證明圖7―31所示的圖沒有漢密爾頓路。證明:任取一結(jié)點如v1，用A標(biāo)記，所有與它相鄰的結(jié)點標(biāo)B。繼續(xù)不斷地用A標(biāo)記所有鄰接于B的結(jié)點，用B標(biāo)記所有鄰接于A的結(jié)點，直到圖中所有結(jié)點全部標(biāo)記完畢。如果圖中有一條漢密爾頓路，則必交替通過結(jié)點A和B。因此或者結(jié)點A和B數(shù)目一樣，或者兩者相差１個。,