計算機(jī)數(shù)學(xué)17PPT課件

1、基本要求、重點(diǎn)難點(diǎn)17.1 圖的基本概念 17.2 無向圖的連通性 17.4 無向圖的矩陣表示 17.5 有向圖的矩陣表示 17.3 有向圖的連通性 17.6 歐拉圖與哈密頓圖 17.7 樹 第1頁/共58頁基本要求 掌握圖的基本概念； 掌握圖的連通性； 掌握樹的定義與應(yīng)用。第2頁/共58頁重點(diǎn)難點(diǎn)重點(diǎn)：圖的基本概念； 圖的連通性； 樹的定義與應(yīng)用。 第3頁/共58頁17.1 圖的基本概念 圖是指一個離散集與其某些兩元素子集的集合構(gòu)作的一種數(shù)學(xué)結(jié)構(gòu)，它的數(shù)學(xué)形象是，在紙上畫幾個(頂)點(diǎn)，再把其中一些點(diǎn)對用曲線段或直線段連接起來，如此形成的一維網(wǎng)絡(luò)，其中點(diǎn)的位置與連線的曲直長短可以任意。圖顯示的

2、是點(diǎn)與點(diǎn)之間的二元關(guān)系。 哥尼斯堡七橋問題拉姆齊(Ramsey)問題第4頁/共58頁哥尼斯堡(Konigsberg)七橋問題 繼續(xù)第5頁/共58頁著名數(shù)學(xué)家歐拉仔細(xì)研究了這個問題，他將上述四塊陸地與七座橋的關(guān)系用一個抽象圖形來描述(如圖17.1.2)，其中四塊陸地分別由四個點(diǎn)表示，而陸地之間有橋相聯(lián)者則用連接兩個點(diǎn)的弧邊表示。 于是問題就變成：從圖中任一點(diǎn)出發(fā)，通過每條邊一次而返回原點(diǎn)的回路是否存在? 在此基礎(chǔ)上，歐拉找到了存在這樣一條回路的充要條件。由此推得哥尼斯堡七橋問題無解。歐拉的研究奠定了圖論的基礎(chǔ)。目前，他被公認(rèn)為圖論之父。 返回第6頁/共58頁拉姆齊(Ramsey)問題 可以用圖形

3、來描述。用6個小圓點(diǎn)a，b，c，d，e，f 來表示任意六個人，若某兩個人彼此認(rèn)識，則相應(yīng)的兩點(diǎn)用實(shí)線連接，若兩人彼此不認(rèn)識，則在相應(yīng)兩點(diǎn)之間畫一條虛線。因此，任兩點(diǎn)之間若不存在實(shí)線，就必存在虛線，反之亦然。于是，在圖論中此命題則為：六個點(diǎn)的圖形中一定存在一個實(shí)三角形，或一定存在一個虛三角形。 繼續(xù)第7頁/共58頁任取一點(diǎn)，比如a，顯然在其余五點(diǎn)之中，存在三點(diǎn)與a用實(shí)線連接，或者，存在三點(diǎn)與a用虛線連接，并且，只存在一種可能。若a與三點(diǎn)用實(shí)線相聯(lián)，比如b，c，d三點(diǎn)，如下圖(a)所示?？疾靊，c，d 三點(diǎn)，若有兩點(diǎn)用實(shí)線連接，比如b與c，則a，b，c構(gòu)成一實(shí)線三角形。若b，c，d三點(diǎn)之間均用虛線

4、連接，則b，c，d已構(gòu)成一虛線三角形。即b，c，d之間的任何一種情況都將導(dǎo)致出現(xiàn)實(shí)線三角形或虛線三角形。上圖反之，若a對b，c，d均由虛線連接，如下圖(b)所示，可用同樣方法證明必然存在實(shí)線三角形或者虛線三角形。因此，原命題得證。 由以上例子可以看出，通過用圖形來描述，問題就顯得簡潔多了。同時，所得結(jié)論更深刻，其應(yīng)用更廣泛.在這里，我們感興趣的是圖形中有哪些點(diǎn)以及點(diǎn)與點(diǎn)之間是否有線連接，而并不關(guān)心這些點(diǎn)具體代表什么，它們之間的連接方式如何。這種由點(diǎn)集和邊集組成的整體稱為一個圖。返回第8頁/共58頁 17.1.2 圖的基本概念 .定義17.1 圖G是由非空結(jié)點(diǎn)集合V=v1，v2，vn以及邊集合E

5、=l1，l2，lm兩部分所組成，其中每條邊可用一個結(jié)點(diǎn)對表示，即Li=(vi1，vi2)(i=1，2，m). 這樣一個圖G記為G=V，E。 圖可以用圖形來表示。結(jié)點(diǎn)也稱頂點(diǎn)，或簡稱點(diǎn)，在圖形中用一圓點(diǎn)表示。而邊在圖形中用線段或曲線段表示，所以也可稱為弧。有時我們?yōu)榱藬⑹龇奖?，不區(qū)分圖與其圖形兩個概念。具有n個結(jié)點(diǎn)，m個邊所組成的圖稱為(n，m)圖。第9頁/共58頁例17.1.3 有四個城市v1，v2，v3，v4。其中v1與v2間、v1與v4間、v2與v3間開辦了民航客運(yùn)業(yè)務(wù)。此事實(shí)用圖的方法表示，則為G=V，E，其中V=v1，v2，v3，v4，E=(v1，v2)，(v1，v4)，(v2，v3)

6、。如下圖(a)所示。 例17.1.4 有四個程序p1，p2，p3，p4。它們之間有一些調(diào)用關(guān)系：p1能調(diào)用p2；p2能調(diào)用p3；p2能調(diào)用p4；p3能調(diào)用p2。此事實(shí)用圖的方法表示，則為D=V，E。其中V=p1，p2，p3，p4，E=(p1，p2)，(p2，p3)，(p2，p4)，(p3，p2)。如圖17.1.4(b)所示。第10頁/共58頁 以上兩例中，對于結(jié)點(diǎn)對的概念，可有兩種不同的理解。例17.1.3中，兩城市間的航空業(yè)務(wù)是雙向的，也就是說(v1，v2)與(v2，v1)具有相同的含義，亦即結(jié)點(diǎn)對(v1，v2)與次序無關(guān)。這種結(jié)點(diǎn)對叫做無序結(jié)點(diǎn)對，它所對應(yīng)的邊稱為無向邊。但在例17.1.4

7、中，程序的調(diào)用關(guān)系則是單向的，比如p1能調(diào)用p2不能保證p2也一定能調(diào)用p1.此時(p1，p2)與(p2，p1)具有不同的含義，即結(jié)點(diǎn)對與次序有關(guān)。這種結(jié)點(diǎn)對叫做有序結(jié)點(diǎn)對，它所對應(yīng)的邊稱為有向邊。有向邊可在邊上加箭頭用來表示邊的方向，而無向邊則邊上不須加箭頭。 利用圖中邊的有向與無向性可將圖分成兩種類型.即 有向圖：圖中的所有邊均為有向邊。 無向圖：圖中的所有邊均為無向邊。 例17.1.3、例17.1.4所給出的圖分別為無向圖與有向圖。 在有向邊lk=(vi，vj)中，vi稱為lk的起點(diǎn)，vj稱為lk的終點(diǎn)。而不管lk為有向邊還是無向邊，我們均稱邊lk與結(jié)點(diǎn)vi，vj相關(guān)聯(lián)，稱vi與vj為鄰

8、接的。若干條邊關(guān)聯(lián)于同一個結(jié)點(diǎn)，則這些邊稱為鄰接的。例如，在圖17.1.4中，p1與p2分別為邊(p1，p2)的起點(diǎn)與終點(diǎn)，結(jié)點(diǎn)p1，p2與有向邊(p1，p2)相關(guān)聯(lián)，結(jié)點(diǎn)v1，v2與邊(v1，v2)相關(guān)聯(lián)，結(jié)點(diǎn)v1與v2是鄰接的，邊(v1，v2)與邊(v2，v3)是鄰接的。第11頁/共58頁例17.1.5 一個圖中某點(diǎn)不與任何邊關(guān)聯(lián)，稱此點(diǎn)為孤立點(diǎn)。 圖17.1.5 一個圖可以沒有邊，所有點(diǎn)均為孤立點(diǎn)，這種圖稱為零圖。圖17.1.5(a)所示的圖為4個結(jié)點(diǎn)的零圖。 只有一個點(diǎn)也構(gòu)成圖，稱為平凡圖。它是點(diǎn)數(shù)最小的零圖。 各點(diǎn)之間都有邊相聯(lián)的無向圖是一種特殊圖，叫做完全圖。有n個點(diǎn)的完全圖用Kn

9、表示。如圖17.1.5(b)所示的圖為K5。 容易證明，完全圖Kn具有（1/2）n(n-1)條邊。各點(diǎn)之間都有兩條相向的邊連接的有向圖，也叫做完全圖。它為有向完全圖。圖17.1.5(c)所示的圖為3個結(jié)點(diǎn)的有向完全圖。第12頁/共58頁定義17.2 圖G=V，E與G=V，E間如果有V V及E E，則稱G是G的子圖。若G是G的子圖，并且V=V，則稱G為G的生成子圖。若G=V，E是G的非空子圖，并且邊集E為二端點(diǎn)均在V中的邊的全體所組成的集合，則稱G為G的導(dǎo)出子圖。 例17.1.6 圖17.1.6中，圖G與G均為G的子圖，G為G的生成子圖，G為G的導(dǎo)出子圖。 圖17.1.6 第13頁/共58頁定義

10、17.3 設(shè)G=V，E與G=V，E是兩個圖。若在V和V之間存在雙射，使得(vi，vj)E當(dāng)且僅當(dāng)(vi)，(vj)E，其中vi，vjV，則稱G與G是同構(gòu)的圖。 例17.1.7 圖17.1.7中，圖G=V，E與圖H=P，L是同構(gòu)的。其中V=1，2，3，4，5，P=a，b，c，d，e。 圖17.1.7 第14頁/共58頁 在點(diǎn)集V與點(diǎn)集P之間可建立雙射如下：(1)=a，(2)=c，(3)=e，(4)=b，(5)=d. 則滿足如下性質(zhì)：對任意(vi，vj)E，當(dāng)且僅當(dāng)(vi),(vj)L。 兩個同構(gòu)的圖，除了圖中各點(diǎn)的名字或符號不同外，本質(zhì)上是一樣的?？梢园阉鼈冇猛耆嗤膱D形表示出來，因此，今后我

11、們主要研究不同構(gòu)的圖。第15頁/共58頁 17.1.3 圖中結(jié)點(diǎn)的度數(shù) 定義17.4 在有向圖中，以結(jié)點(diǎn)v為起點(diǎn)的邊的條數(shù)叫v的出度，記為 (v)。以v為終點(diǎn)的邊的條數(shù)叫v的入度，記為 (v)。v的入度與出度之和稱為v的度數(shù)，記為deg(v)。在無向圖中，結(jié)點(diǎn)v的度數(shù)就是與v相關(guān)聯(lián)的邊的條數(shù)，它也用deg(v)表示。 零圖中各點(diǎn)度數(shù)均為0。完全圖Kn各點(diǎn)的度數(shù)均為n-1。 在圖中，每條邊必與兩個結(jié)點(diǎn)相關(guān)聯(lián)，這就導(dǎo)致圖中所有結(jié)點(diǎn)的度數(shù)之和為偶數(shù)，且必為圖中邊數(shù)的兩倍，故我們有下面的定理。 定理17.1 設(shè)圖G=V，E為(n，m)圖。則有 換句話說，有限圖G的各點(diǎn)度數(shù)總和是邊數(shù)的兩倍。第16頁/共

12、58頁推論：一個圖中度數(shù)為奇數(shù)的點(diǎn)的個數(shù)為偶數(shù)。 定理17.2 在有向圖中，各結(jié)點(diǎn)出度之和等于各結(jié)點(diǎn)入度之和。 例17.1.8 圖G=V，E為(n，m)圖，、分別是 G 中點(diǎn)的最小度與最大度，即 第17頁/共58頁 17.1.4 多重圖與帶權(quán)圖 在實(shí)際問題中，有時會遇到與圖的定義不完全相同的特殊的圖，在這里，我們作簡單介紹。若一個邊連接同一個點(diǎn)，我們將其稱為圈，允許有圈的圖稱為帶圈圖。 在無向圖中，若兩個或兩個以上的邊連接同一對點(diǎn)，我們將其稱為平行邊。在有向圖中，若兩個或兩個以上方向相同的有向邊連接同一對點(diǎn)，我們亦將其稱為平行邊。允許有平行邊的圖稱為多重圖。例如，在哥尼斯堡七橋問題中的圖就為多

13、重圖。 既不包含圈，又不包含平行邊的圖，叫做簡單圖。在以后的討論中，不特別指出的話，我們討論的圖均指簡單圖。 有時，在一個圖中邊的旁側(cè)附加一些數(shù)字以刻畫此邊的某些數(shù)量特征，這些數(shù)字叫做邊的權(quán)。根據(jù)實(shí)際問題的需加，可以賦予權(quán)不同的含義，它可以表示距離、費(fèi)用、時間等。而具有有權(quán)邊的圖叫做帶權(quán)圖。第18頁/共58頁研究圖的性質(zhì)，最重要一點(diǎn)，就是其連通性。 17.2 無向圖的連通性 定義17.5 在無向圖G=V，E中，設(shè)li是關(guān)聯(lián)于結(jié)點(diǎn)vi-1和vi的邊，交替序列v0l1vil2lnvn稱為連接v0到vn點(diǎn)的一條通道。通道可簡記為(vn，v1，vn)。通道中邊的個數(shù)稱為通道的長。若v0=vn，稱之為閉

14、通道。 直觀地說，通道就是通過相連的若干條邊從一點(diǎn)到達(dá)另一點(diǎn)的路線。通道上的點(diǎn)、邊均可以重復(fù)出現(xiàn)。定義17.6 無重復(fù)邊的通道稱為跡。無重復(fù)邊的閉通道則稱為閉跡。 第19頁/共58頁定義17.7 無重復(fù)點(diǎn)的通道稱為路。若一條長為n的閉通道上n個點(diǎn)各不相同，且n3，則稱之為一條回路。 如果長為n的通道上n+1個點(diǎn)各不相同，則相應(yīng)的n條邊也必然各不相同，因此，路一定是跡。相反地，長為n的通道上n條邊各不相同時，卻仍可能有重復(fù)點(diǎn)出現(xiàn)，因此跡不一定是路。同樣，閉跡不一定是回路，而回路則一定是閉跡。例 17.2.1 圖17.2.1中，(1，2，3，4，5，1，2)為一條長為6的通道，但不是跡，當(dāng)然也不是

15、路；(1，2，4，1，2，4，1)為一條長為6的閉通道，但不是閉跡，當(dāng)然也不是回路；(1，2，3，4，2)為一條長為4的跡，但不是路；這樣一通道(1，5，4，3，2，4，1)為一條長為6的閉跡，但不是回路；(1，2，3，4)為長為3的路；(1，2，3，4，1)為長為4的回路。 (1，2，1)為長為2的閉通道，盡管兩點(diǎn)不同，兩條邊卻相同，它不構(gòu)成回路，也不是閉跡。 圖17.2.1 第20頁/共58頁例17.2.2 證明：一條通道不是路，當(dāng)且僅當(dāng)此通道中有一子序列構(gòu)成一條閉通道。 證 “必要性” 若(vi1，vin)不是路，則在vij(j=1，n)中必存在某兩點(diǎn)相同，設(shè)為vik，vim。(vi1，

16、vin)的子序列(vik，vim)，由于vik=vim，可得此子序列為一條閉通道。 “充分性” 若(vi1，vin)中有一子序列構(gòu)成閉通道，設(shè)其為(vik，vim)，其中vik=vim。 所以，(vi1，vin)中有重復(fù)的點(diǎn)，因此不是路。原命題得證。證畢。 第21頁/共58頁定理17.3 在一個具有n個結(jié)點(diǎn)的圖中，任一條路的長度均不大于n-1，任一回路的長度均不大于n. 第22頁/共58頁17.2.2 連通性 定義17.8 G=V，E是一無向圖。u，vV，uv，若G中存在從u至v的通道，則稱u與v是可達(dá)的。否則，稱u，v不可達(dá)。并定義圖中任一點(diǎn)與其自身是可達(dá)的。 定義17.9 G=V，E是一無

17、向圖，u，vV，若u，v是可達(dá)的，稱u與v連通。若圖中任兩點(diǎn)連通，則G稱為連通圖。否則G稱為非連通圖。 第23頁/共58頁 如果我們將結(jié)點(diǎn)的連通視為圖中點(diǎn)集上的一個關(guān)系，由定義顯然可以得到此關(guān)系滿足自反性、對稱性和傳遞性，即連通關(guān)系是等價關(guān)系。此等價關(guān)系必然惟一地將v劃分成k(k1)個等價類，記為V1，V2，V3，Vk。由它們導(dǎo)出的導(dǎo)出子圖(V1，E1)，(V2，E2)，(Vk，Ek)稱為G的連通分圖。連通分圖是連通圖。一個連通分圖中的任一點(diǎn)與其他連通分圖中的點(diǎn)不連通。連通圖的連通分圖只有一個，就是它本身。 例17.2.4 圖17.2.2(a)所示，G為連通圖。 圖17.2.2(b)所示，G為

18、非連通圖。G有兩個連通分圖，它們分別是由V1=10，9，1，2，6，5和V2=4，3，7，8，11導(dǎo)出的子圖。 第24頁/共58頁定義17.10 在連通無向圖G中： (1) 如果去掉一個結(jié)點(diǎn)v及與v關(guān)聯(lián)的邊，圖將不連通，則稱結(jié)點(diǎn)v為圖的割點(diǎn)或關(guān)節(jié)點(diǎn)； (2) 如果去掉一條邊，圖將不連通，則稱這條邊為圖的割邊或橋； (3) 若S為圖G中若干邊的非空集合，圖G去掉S 則不連通，而去掉S 的任一真子集仍連通，則稱S為圖G的一個割集。即割集S是G的最少邊的集合，除去它將使G分割為兩個連通子圖。 例17.2.6 考慮七個城市的交通。由于種種原因，這七個城市有的可直達(dá)，有的不能直達(dá)。如圖17.2.3所示，

19、點(diǎn)a，b，c，d，e，f，g代表城市，邊代表兩城市之間可直達(dá)。圖17.2.3顯然，此圖為連通圖，即任兩點(diǎn)是可達(dá)的，也就是說，七個城市中任兩城市均可通過交通聯(lián)系。但此交通系統(tǒng)是不理想的，因?yàn)樗倪B通程度并不高，一旦某些環(huán)節(jié)出了問題，系統(tǒng)就會中斷。比如，城市a，b任一城市交通堵塞或被破壞，或者，ab之間交通堵塞或被破壞，整個交通系統(tǒng)將會中斷。可見，點(diǎn)a，b，邊(a，b)對于圖17.2.3的連通性具有特殊意義，我們稱之為割點(diǎn)及橋。 第25頁/共58頁 在圖17.2.3所示圖中，有兩個割點(diǎn)：a、b。一條邊是橋：(a，b)。割集有(a，b)，(a，d)，(a，e)，(a，d)，(d，e)，(a，e)，(

20、e，d)，(b，c)，(b，f )，(b，g)，(b，c)，(c，g)，(b，f)，(f，g)，(c，g)，(b，g)，(f，g)。其他邊集則不是割集，比如：(a，b)，(a，d)，(b，c)，(b，f )等。 第26頁/共58頁定義17.11 圖G為一無向連通圖： (1) 圖G的點(diǎn)連通度(G)，是為了由G產(chǎn)生一個不連通圖或平凡圖，而需從G中去掉的最少的點(diǎn)數(shù)； (2) 圖G的邊連通度(G)，是為了由G產(chǎn)生一個不連通圖或平凡圖，而需從G中去掉的最少的邊數(shù)。 定理17.4 無向圖G中，(G)為點(diǎn)連通度，(G)為邊連通度，(G)為最小度，則(G)(G)(G)。第27頁/共58頁17.3 有向圖的連通

21、性 無向圖中無長為2的回路，有向圖中卻可能有長為2的有向回路。這是因?yàn)?，無向圖中，兩個不同點(diǎn)之間只能有一條邊，而有向圖中兩不同點(diǎn)之間可以有一對相向的邊。 定義17.12 有向圖D中一個點(diǎn)、有向邊交替的序列：v0，(v0，v1)，v1，(v1，v2)，vn稱為一條長為n的有向通道，記為(v0，v1，vn)。有向閉通道、有向跡、有向閉跡和有向路可類似定義。有向回路是無重復(fù)出現(xiàn)的點(diǎn)的有向閉通道。 第28頁/共58頁 有向通道是有方向性的，所以在有向圖中，u可達(dá)v時，不一定有v可達(dá)u。即使u可達(dá)v且v可達(dá)u，從u到v的有向通道與從v到u的有向通道也是不同的。對于有向圖，由于其邊有方向性，可達(dá)關(guān)系不一定

22、是對稱的。因此有向圖的連通性比無向圖的連通性包含了更多的內(nèi)容。 定義17.13 在有向圖D中，若存在從點(diǎn)u到點(diǎn)v的有向通道，則稱點(diǎn)u可達(dá)點(diǎn)v。 第29頁/共58頁 例 17.3.1 圖17.3.1中有八個結(jié)點(diǎn)數(shù)為3的有向圖。其中(a) 中是兩個非連通圖；(b) 中是兩個弱連通圖；(c) 中是兩個單向連通圖；(d) 中是兩個強(qiáng)連通圖。 定義17.14 一個有向圖D=V，E，若忽略其邊的方向后，得到的無向圖是連通的，則稱D是弱連通的。否則稱D為非連通的。若D中任意兩點(diǎn)u，v都有從u可達(dá)v、或從v可達(dá)u，則稱D 是單向連通的；若D 中每一點(diǎn)u均可達(dá)其他任一點(diǎn)v，則稱D是強(qiáng)連通的。 很顯然，在有向圖中

23、，強(qiáng)連通圖是單向連通的，也是弱連通的。同樣，一個單向連通圖必是弱連通的。但反之則不然，弱連通圖不一定是單向連通的或強(qiáng)連通的，單向連通圖也不一定是強(qiáng)連通的。 第30頁/共58頁定義17.15 在有向圖D中，具有極大強(qiáng)連通的子圖，稱為D的一個強(qiáng)分圖；具有極大單向連通性的子圖，稱為D的一個單向分圖；具有極大弱連通性的子圖，稱為D的一個弱分圖。強(qiáng)分圖的定義中，“極大”的含義是：對該子圖再加入其他結(jié)點(diǎn)，它便不再具有強(qiáng)連通性。對單向分圖、弱分圖也類似。 例17.3.2 圖17.3.2中，點(diǎn)集c，f，g，d，h的導(dǎo)出子圖為強(qiáng)分圖。a，b，e的導(dǎo)出子圖僅為單向分圖。弱分圖只有一個就是圖自身。 第31頁/共58

24、頁定理17.5 有向圖D是強(qiáng)連通的，當(dāng)且僅當(dāng)D中存在一條包含D中所有點(diǎn)的有向閉通道。證 (1) “充分性”D中有一條包含了D中所有點(diǎn)的有向閉通道，則D中任一點(diǎn)u沿此通道前進(jìn)，可達(dá)其他任一點(diǎn)v，因此D是強(qiáng)連通的。(2) “必要性”若D是強(qiáng)連通的，從D中任一點(diǎn)v1出發(fā)，可達(dá)其他點(diǎn)v2，再從v2可達(dá)v3，至最后一點(diǎn)vn，最后從vn可達(dá)v1，這就是一條包含了所有點(diǎn)的有向閉通道。故，定理得證。證畢.定理17.6 有向圖D中，它的每個結(jié)點(diǎn)位于且只位于一個強(qiáng)連通分圖中。 第32頁/共58頁17.4 無向圖的矩陣表示 定義17.16 設(shè)無向圖G=V，E的結(jié)點(diǎn)集V=v1，v2，vn.若n階方陣A(G)=(aij

25、)n滿足條件： 則稱A(G)為圖G的點(diǎn)鄰接矩陣，簡稱鄰接矩陣。 鄰接矩陣可以完全描述一個圖。給定一個鄰接矩陣，就能夠確定一個圖。由于無向圖中，點(diǎn)的鄰接關(guān)系是對稱的，鄰接矩陣一定是對稱陣。我們所研究的圖為簡單圖，所以鄰接矩陣主對角線上元素全為0。無向圖的鄰接矩陣中，行元素之和等于相應(yīng)點(diǎn)的度。通過以下例題我們可以明顯看出，鄰接矩陣的這些特點(diǎn)。 第33頁/共58頁定理17.7 若A(G)是無向圖G的鄰接矩陣，Y=(A(G)k(kN)，則Y中元素yij表示從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的長為k的通道的數(shù)目。 定義：17.17 G=V，E為無向圖，V=v1，v2，vn，E=l1，l2，ln。若nm的矩陣M(G)=

26、(bij)nm滿足 則矩陣M(G)稱為圖G的點(diǎn)邊關(guān)聯(lián)矩陣，簡稱關(guān)聯(lián)矩陣。 關(guān)聯(lián)矩陣也可以完全描述一個圖。關(guān)聯(lián)矩陣中的每一行對應(yīng)圖中的一個點(diǎn)，每一列對應(yīng)圖中的一條邊。每行元素之和為相應(yīng)點(diǎn)的度，每列則恰有兩個非0元素。第34頁/共58頁17. 5 有向圖的矩陣表示 定義：17.18 D=V，E是有向圖，V=v1，v2，vn，若n階方陣A(D)=(aij) n滿足 則稱A(D)為D的鄰接矩陣。 與無向圖的鄰接矩陣相同，有向圖的鄰接矩陣完全描述了一個有向圖。由于有向圖中邊為有向邊，故其鄰接矩陣不一定是對稱陣，只有兩點(diǎn)間的邊均成對出現(xiàn)，矩陣才是對稱的。D的鄰接矩陣A(D)中每一行元素之和，表示相應(yīng)點(diǎn)的出

27、度，每一列元素的和表示相應(yīng)點(diǎn)的入度。只有當(dāng)?shù)趇行、i 列元素全為0時，所對應(yīng)點(diǎn)vi不與任何邊關(guān)聯(lián)，即孤立點(diǎn)。第35頁/共58頁 例17.5.1 有向圖D=V，E的關(guān)聯(lián)矩陣為 則有向圖的圖形可見圖17.5.1。 與無向圖的鄰接矩陣類似，我們也可通過有向圖的鄰接矩陣來研究有向圖中兩點(diǎn)之間通道的數(shù)量。第36頁/共58頁定理17.8 若A(D)是有向圖D=V，E的鄰接矩陣，Y=(A(D)k，(kN)，則Y中元素yij表示從點(diǎn)vi至點(diǎn)vj的長為k的有向通道的數(shù)目。 例 17.5.1 中的有向圖D=V，E的鄰接矩陣為A(D)， 由此可見，從v1至v3的長度為2的通道有一條，從v3至v1的長度為3的通道有2

28、條，通過v3點(diǎn)長度為4的閉通道有2條。 第37頁/共58頁定義：17.19 D=V，E是有向圖，V=v1，v2，vn，E=l1，l2，lm。若nm矩陣M(D)=(bij)nm滿足 則稱M(D)為D的關(guān)聯(lián)矩陣。 在有向圖的關(guān)聯(lián)矩陣中，非0元的值可以是1或-1。因?yàn)槊苛袑?yīng)一條有向邊，所以每列恰有兩個非零元1和-1。每行對應(yīng)一個點(diǎn)，所以每行元素的絕對值之和為對應(yīng)點(diǎn)的度數(shù)，1的個數(shù)為出度，-1的個數(shù)為入度。矩陣的所有元素的代數(shù)和為0，1的個數(shù)等于-1的個數(shù)等于有向圖的邊數(shù)。這些特征均可在如下例題中看出。 第38頁/共58頁定義：17.20 若D=V，E為有向圖，V=v1，v2，vn。若n階方陣P(D

29、)=(cij)n滿足 則稱P(D)為D的可達(dá)性矩陣。 根據(jù)圖的圖形寫出圖的可達(dá)性矩陣并不是我們的目的，因?yàn)樗匀幻撾x不開對圖形的依賴性。下面介紹一種求可達(dá)性矩陣的算法.我們先來定義一種特殊的運(yùn)算：布爾運(yùn)算。 若a，bN，則定義： 第39頁/共58頁 17.6 歐拉圖與哈密頓圖 17.6.1 歐拉圖定義：17.21 在一個無向圖中(也可以是無向多重圖)，包含了所有邊的一條跡稱為歐拉跡，包含了所有邊的閉跡稱為歐拉閉跡.具有歐拉閉跡的圖稱為歐拉圖。 定理：17.9 非平凡無向圖G據(jù)有一條歐拉跡，當(dāng)且僅當(dāng)G是連通的，且有零個或兩個奇度數(shù)結(jié)點(diǎn)。若有兩個奇度數(shù)結(jié)點(diǎn)，它們是G中每條歐拉跡的端點(diǎn)。推論 非平凡

30、無向圖為歐拉圖，當(dāng)且僅當(dāng)G連通，且所有結(jié)點(diǎn)度數(shù)均為偶數(shù)。 這個定理給出了判別歐拉圖的一個非常簡單有效的方法。利用這個方法可以馬上看出哥尼斯堡七橋問題是無解的。因?yàn)楦缒崴贡て邩蛩鶎?yīng)的圖，其每個結(jié)點(diǎn)的度數(shù)均為奇數(shù)。歐拉跡問題是一個實(shí)用性很強(qiáng)的問題。第40頁/共58頁第41頁/共58頁 例17.6.3 判定圖17.6.3中的四個圖形是否可以一筆畫。 解 圖17.6.3(a)中，1，5 兩點(diǎn)為奇度數(shù)點(diǎn)，其余點(diǎn)均為偶度數(shù)點(diǎn).故以1 開始起存在一筆畫路線至5結(jié)束。比如(1，2，4，5，6，3，1，5，2，3，5). 圖17.6.3(b)中有歐拉跡。圖17.6.3(c)(d)均為歐拉圖。所以，均可以一筆畫

31、。第42頁/共58頁定義：17.22 在一個有向圖中，包含了所有有向邊的一條有向跡稱為此有向圖的歐拉跡。包含了所有有向邊的有向閉跡稱為有向圖的歐拉閉跡.具有歐拉閉跡的有向圖為有向歐拉圖。 定理：17.10 一個有向圖D具有歐拉跡，當(dāng)且僅當(dāng)D是連通的，且除兩個結(jié)點(diǎn)外，其余結(jié)點(diǎn)入度等于出度，這兩個例外結(jié)點(diǎn)中，一個入度比出度大1，另一個入度比出度小1。 推論 一個有向圖為歐拉圖，當(dāng)且僅當(dāng)D是連通的，且所有結(jié)點(diǎn)入度等于出度。第43頁/共58頁 17.6.2 哈密頓(Hamilton)圖 哈密頓問題，起源于一種游戲，它是由英國數(shù)學(xué)家哈密頓于1859年提出，這個曾風(fēng)靡一時的游戲名叫周游世界游戲。這個游戲的

32、內(nèi)容就是，用一個正十二面體的20個頂點(diǎn)代表世界上20個著名的大城市(如圖17.6.5(a)。游玩的人沿正十二面體的棱，從一個城市出發(fā)，經(jīng)過每個城市恰好一次，然后回到出發(fā)點(diǎn)。 如果我們以正十二面體頂點(diǎn)作為點(diǎn)，相應(yīng)的棱作為邊，就可以得到平面上的一個圖(如圖17.6.5(b)?？芍螒蛞獙ふ业氖且粭l通過圖中每個結(jié)點(diǎn)一次的回路。此回路有若干個，稱為哈密頓回路。一般我們在無向圖中研究哈密頓圖問題。 第44頁/共58頁注意 歐拉圖與哈密頓圖研究目的不同，前者要遍歷圖的所有邊，后者要遍歷圖的所有點(diǎn)。雖然都是遍歷問題，兩者的困難程度卻大不相同。我們已較滿意地解決了歐拉圖問題，而哈密頓問題卻是一個至今尚未解決的

33、難題。在大多數(shù)情況下，人們還是采用嘗試的方法來解決。 定義：17.23 通過圖G中每結(jié)點(diǎn)一次的通道定為路，此路稱為哈密頓路。通過圖G中每結(jié)點(diǎn)一次的閉通道為回路，此回路稱為哈密頓回路。具有哈密頓回路的圖叫哈密頓圖。設(shè)G中有n個點(diǎn)，則G 的哈密頓路有n-1條邊，G的哈密頓回路有n條邊。 第45頁/共58頁 例17.6.5 有9個學(xué)生打算幾天都在一個圓桌上共進(jìn)晚餐，并且希望每次晚餐時，每個學(xué)生兩邊鄰座的人都不相同，按照這樣一種要求，他們在一起共進(jìn)晚餐最多幾天? 。 第46頁/共58頁解 以9個學(xué)生為結(jié)點(diǎn)，兩人相鄰而坐，就可看作兩點(diǎn)之間有邊相聯(lián)。因此，相鄰就座的所有可能合在一起，就是9個結(jié)點(diǎn)的完全圖K

34、9，而K9任意一個哈密頓回路，就表示一次晚餐的就座方式。兩個哈密頓回路只要沒有公共邊，就表示對應(yīng)的兩次晚餐的就座中，每個人相鄰就座者都不相同。由于K9共有 條邊，在K9中每條哈密頓回路的長度為9。則沒有公共邊的哈密頓回路數(shù)目至多有36/9=4條。9人的坐法，只由他們之間的相鄰關(guān)系決定。排成圓形時，僅與排列順序有關(guān)。因此對各種坐法，可認(rèn)為一人的座位不變，我們可將其設(shè)作1號，并不妨放于圓心，其余8人可均勻地放在圓周上(如圖17.6.6所示)。于是不同的哈密頓回路，可由圓周上不同編號的旋轉(zhuǎn)而得到。 如果9個人標(biāo)號為1，2，9，則四天中排列情況如下：1 2 3 9 4 8 5 7 6 1；1 3 4

35、2 5 9 6 8 7 1；1 4 5 3 6 2 7 9 8 1；1 5 6 4 7 3 8 2 9 1。 故他們在一起共進(jìn)晚餐最多4天。第47頁/共58頁 例17.6.6 圖17.6.7中，(a)圖有哈密頓路，亦有哈密頓回路。比如：(a，b，c，d，e)為哈密頓路，(a，c，e，b，d，a)為哈密頓回路，此圖為哈密頓圖。 圖(b)若有哈密頓回路，則此回路必通過與1，3，5，7點(diǎn)關(guān)聯(lián)的邊，而這些邊已構(gòu)成回路，但9，10點(diǎn)不在回路中，所以此圖沒有哈密頓回路。事實(shí)上，此圖也無哈密頓路。圖(c)有哈密頓路，沒有哈密頓回路。這是因?yàn)槿舸藞D有哈密頓回路，則此回路必通過邊(a，c)，(a，b)；(f，g

36、)，(c，g)；(d，e)，(e，c)。于是回路中，通過c點(diǎn)有三條邊，這不可能，所以圖(c)無哈密頓回路。第48頁/共58頁17.7 樹 17.7.1 無向樹 定義：17.24 不包含回路的連通無向圖稱為無向樹，簡稱樹。每個連通分圖都是樹的非連通圖稱為林。 例17.7.1 在圖17.7.1中，(a)圖是樹，因?yàn)樗B通又不包含回路。而(b)，(c)圖均不是樹。圖(b)雖連通但有回路，圖(c)雖無回路，但不連通。 在樹中，度數(shù)為1的結(jié)點(diǎn)稱為樹葉，度數(shù)大于1的結(jié)點(diǎn)稱為分支點(diǎn)。如圖17.7.1(a)中，v1，v4，v5點(diǎn)為樹葉，v2，v3點(diǎn)為分支點(diǎn)。 平凡圖(n=1)為樹，稱為平凡樹。 第49頁/共5

37、8頁定理：17.11 在(n，m)樹中必有n=m+1。證 用數(shù)學(xué)歸納法對n進(jìn)行歸納。n=1時，定理成立。設(shè)對所有i(in)定理成立，需求證n時有n=m+1。設(shè)有一(n，m)樹G，因?yàn)镚不包含任何回路，所以G中刪去一邊后就變成兩個互不連通的子圖，每個子圖是連通的且無回路，所以每個子圖均為樹，設(shè)它們分別為(n1，m1)樹及(n2，m2)樹。由于n1n，n2n，由歸納假設(shè)可得：n1=m1+1，n2=m2+1。又因?yàn)閚=n1+n2，m=m1+m2+1。故我們得到 n=m+1，原命題得證。證畢.第50頁/共58頁定理：17.11若無向圖G為(n，m)圖，則下述命題等價： (1) G是樹； (2) G中任意兩點(diǎn)間有惟一一條路； (3) G連通，且去掉一條邊則不連通； (4) G連通，且n=m+1； (5) G中無回路，且n=m+1； (6) G中無回路，且若在任意兩不相鄰結(jié)點(diǎn)間增加一條邊，則恰有一條回路； (7) G連通，且當(dāng)n3時不是