離散數(shù)學(xué) 第6-8章

第6章圖的基本概念圖論〔GraphTheory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。

圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過(guò)。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問(wèn)題有很強(qiáng)的實(shí)際背景。哥尼斯堡七橋哥尼斯堡（今俄羅斯加里寧格勒）是東普魯士的首都，普萊格爾河橫貫其中。十八世紀(jì)在這條河上建有七座橋，將河中間的兩個(gè)島和河岸聯(lián)結(jié)起來(lái)。有人提出：能不能每座橋都只走一遍，最后又回到原來(lái)的位置。這個(gè)問(wèn)題看起來(lái)很簡(jiǎn)單有很有趣的問(wèn)題吸引了大家，很多人在嘗試各種各樣的走法，但誰(shuí)也沒(méi)有做到。

1736年，有人帶著這個(gè)問(wèn)題找到了當(dāng)時(shí)的大數(shù)學(xué)家歐拉，歐拉經(jīng)過(guò)一番思考，很快就用一種獨(dú)特的方法給出了解答。歐拉把這個(gè)問(wèn)題首先簡(jiǎn)化，他把兩座小島和河的兩岸分別看作四個(gè)點(diǎn)，而把七座橋看作這四個(gè)點(diǎn)之間的連線。那么這個(gè)問(wèn)題就簡(jiǎn)化成，能不能用一筆就把這個(gè)圖形畫(huà)出來(lái)。經(jīng)過(guò)進(jìn)一步的分析，歐拉得出結(jié)論——不可能每座橋都走一遍，最后回到原來(lái)的位置。并且給出了所有能夠一筆畫(huà)出來(lái)的圖形所應(yīng)具有的條件。這是拓?fù)鋵W(xué)的“先聲”。

四色問(wèn)題著名的“四色問(wèn)題”也是與拓?fù)鋵W(xué)發(fā)展有關(guān)的問(wèn)題。四色問(wèn)題又稱(chēng)四色猜想，是世界近代三大數(shù)學(xué)難題之一。四色猜想的提出來(lái)自英國(guó)。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯.格思里來(lái)到一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái)，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都被著上不同的顏色?！?/p>

1872年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問(wèn)題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問(wèn)題。世界上許多一流的數(shù)學(xué)家都紛紛參加了四色猜想的大會(huì)戰(zhàn)。1878～1880年兩年間，著名律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理。但后來(lái)數(shù)學(xué)家赫伍德以自己的精確計(jì)算指出肯普的證明是錯(cuò)誤的。不久，泰勒的證明也被人們否定了。于是，人們開(kāi)始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題（當(dāng)n>2時(shí)，xn+yn=zn，n為奇素?cái)?shù)，X，Y，Z沒(méi)有正整數(shù)解。）進(jìn)入20世紀(jì)以來(lái)，科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行。電子計(jì)算機(jī)問(wèn)世以后，由于演算速度迅速提高，加之人機(jī)對(duì)話的出現(xiàn)，大大加快了對(duì)四色猜想證明的進(jìn)程。1976年，美國(guó)數(shù)學(xué)家阿佩爾與哈肯在美國(guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明。不過(guò)不少數(shù)學(xué)家并不滿足于計(jì)算機(jī)取得的成就，他們認(rèn)為應(yīng)該有一種簡(jiǎn)捷明快的書(shū)面證明方法。

哈密頓問(wèn)題1859年，英國(guó)數(shù)學(xué)家哈密頓發(fā)明了一種游戲：用一個(gè)規(guī)則的實(shí)心十二面體，它的20個(gè)頂點(diǎn)標(biāo)出世界著名的20個(gè)城市，要求游戲者找一條沿著各邊通過(guò)每個(gè)頂點(diǎn)剛好一次的閉回路，即「繞行世界」。用圖論的語(yǔ)言來(lái)說(shuō)，游戲的目的是在十二面體的圖中找出一個(gè)生成圈。這個(gè)問(wèn)題后來(lái)就叫做哈密頓問(wèn)題。由於運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問(wèn)題都可以化為哈密頓問(wèn)題，從而引起廣泛的注意和研究。

§1基本定義一個(gè)圖G定義為一個(gè)三元組<V，E，φ>，記作G=<V，E，φ>。其中V是個(gè)非空有限集合，它的元素稱(chēng)為結(jié)點(diǎn)；E也是個(gè)有限集合，其元素稱(chēng)為邊，而φ是從E到V中的有序?qū)驘o(wú)序?qū)Φ挠成?。由定義可知，圖G中的每條邊都與圖中的無(wú)序或有序結(jié)點(diǎn)對(duì)相聯(lián)系的。若邊e∈E與無(wú)序結(jié)點(diǎn)對(duì)(vi，vj)相聯(lián)系，則φ(e)=(vi，vj)，這時(shí)邊e稱(chēng)為無(wú)向邊，有時(shí)簡(jiǎn)稱(chēng)為邊；若邊e∈E與有序結(jié)點(diǎn)對(duì)<vi，vj>相聯(lián)系，則φ(e)=<vi，vj>，此時(shí)邊e稱(chēng)為有向邊或弧，vi稱(chēng)為弧e的始結(jié)點(diǎn)，vj稱(chēng)為弧e的終結(jié)點(diǎn)。若結(jié)點(diǎn)vi與vj由一條邊(或弧)e所聯(lián)結(jié)，則稱(chēng)結(jié)點(diǎn)vi和vj是邊(或弧)e的端結(jié)點(diǎn)；同時(shí)也稱(chēng)結(jié)點(diǎn)vi與vj是鄰接結(jié)點(diǎn)，記作vi

adjvj關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊或弧稱(chēng)為鄰接邊或鄰接弧。而聯(lián)結(jié)一結(jié)點(diǎn)與它自身的一條邊，稱(chēng)為環(huán)。環(huán)的方向是無(wú)意義的。如果把圖G中的弧或邊總看作聯(lián)結(jié)兩個(gè)結(jié)點(diǎn)，則圖G可簡(jiǎn)記為G=<V，E>，其中V是非空結(jié)點(diǎn)集，E是聯(lián)結(jié)結(jié)點(diǎn)的邊集或弧集。在圖G=<V，E>中，如果每條邊都是弧，該圖稱(chēng)為有向圖；若每條邊都是無(wú)向邊，該圖G稱(chēng)為無(wú)向圖；如果有些邊是有向邊，另一些邊是無(wú)向邊，圖G稱(chēng)為混合圖。在圖G=<V，E>中，如果任何兩結(jié)點(diǎn)間不多于一條邊(對(duì)于有向圖中，任何兩結(jié)點(diǎn)間不多于一條同向弧)，并且任何結(jié)點(diǎn)無(wú)環(huán)，則圖G稱(chēng)為簡(jiǎn)單圖；若兩結(jié)點(diǎn)間多于一條邊(對(duì)于有向圖中，兩結(jié)點(diǎn)間多于一條同向弧)圖G稱(chēng)為多重圖，并把聯(lián)結(jié)兩結(jié)點(diǎn)之間的多條邊或弧，稱(chēng)為平行邊或平行弧，平行邊或弧的條數(shù)稱(chēng)為重?cái)?shù)。給每條邊或弧都賦予權(quán)的圖G=<V，E>，稱(chēng)為加權(quán)圖，記為G=<V，E，W>，其中W表示各邊之權(quán)的集合。加權(quán)圖在實(shí)際中有許多應(yīng)用，如在輸油管系統(tǒng)圖中權(quán)表示單位時(shí)間流經(jīng)管中的石油數(shù)量；在城市街道中，權(quán)表示表示通行車(chē)輛密度；在航空交通圖中，權(quán)表示兩城市的距離等等。在一個(gè)圖中，如果一個(gè)結(jié)點(diǎn)不與任何其他結(jié)點(diǎn)鄰接，則該結(jié)點(diǎn)稱(chēng)為孤立結(jié)點(diǎn)。僅有孤立結(jié)點(diǎn)的圖稱(chēng)為零圖。顯然，在零圖中邊集為空集。若一個(gè)圖中只含一個(gè)孤立結(jié)點(diǎn)，該圖稱(chēng)為平凡圖。2.頂點(diǎn)的度數(shù)頂點(diǎn)v的度數(shù)d(v):即與頂點(diǎn)v關(guān)聯(lián)的邊數(shù)。有向圖中頂點(diǎn)v的出度d+(v):即從頂點(diǎn)v引出的邊數(shù)。有向圖中頂點(diǎn)v的入度d_(v):即進(jìn)入頂點(diǎn)v的邊數(shù)。有向圖中頂點(diǎn)v的度數(shù)d(v)=d+(v)+d_(v)圖G=〈V,E〉的最大度

(G)：

(G)=max﹛d(v)︳v

V﹜圖G=〈V,E〉的最小度

(G)：

(G)=min﹛d(v)︳v

V﹜abcded(a)=5d(b)=4d(c)=3d(e)=1

(G)=5

(G)=1握手定理定理：任意圖中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。即

∑d（v）=2

E

在有向圖中所有頂點(diǎn)的出度（入度）之和等于邊數(shù)。即

∑d+（v）=∑d－（v）=

E

推論：圖中奇度數(shù)頂點(diǎn)的個(gè)數(shù)必為偶數(shù)。v

Vv

Vv

V

無(wú)向完全圖Kn：任兩個(gè)頂點(diǎn)間都有邊的無(wú)向簡(jiǎn)單圖.Kn的每個(gè)頂點(diǎn)的度數(shù)都是n-1.Kn共有n(n-1)/2條邊.競(jìng)賽圖：將無(wú)向完全圖中的每條邊添上任意方向得到的有向圖.正則圖：每個(gè)頂點(diǎn)的度數(shù)都相等的無(wú)向圖.K5競(jìng)賽圖3-正則圖給定圖G=<V，E>，若存在圖G1=<V，E1>，并且E1∩E=

和圖<V，E1∪E>是完全圖，則G1稱(chēng)為相對(duì)于完全圖的G的補(bǔ)圖，簡(jiǎn)稱(chēng)G1是G的補(bǔ)圖§2子圖與同構(gòu)設(shè)G=（V，E），G′=（V′，E′）G′是G的子圖：若V′

V，E′

E

G′是G的真子圖：若G′是G的子圖且V′

V′或

E′E

G′是G的生成子圖：若G′是G的子圖且V=V′V1V2V3V4V5V1V2V4V1V2V3V4V5GG的真子圖G的生成子圖同構(gòu)設(shè)G=（V，E），G′=（V′，E′）G與G′同構(gòu)：若存在雙射f：V→V′使得

u，v

V有

﹤u,v﹥

E當(dāng)且僅當(dāng)﹤f（u）,f（v）﹥

E′v1v2v3v4v1′v3′v4′v2′v1v2v3v4v1′v2′v3′v4′G′GG′G同構(gòu)的性質(zhì)設(shè)G=（V，E），G′=（V′，E′），若G與G′同構(gòu)，則（1）

V

=

V′，E

=

E′

（2）對(duì)任意的k，G中度數(shù)為k的頂點(diǎn)數(shù)等于G′中度數(shù)為k的頂點(diǎn)數(shù)。反之不成立。如圖的同構(gòu)判定算法關(guān)聯(lián)度序列法。黃金分割關(guān)聯(lián)度序列法。計(jì)算時(shí)間復(fù)雜性遠(yuǎn)遠(yuǎn)低于2N(N為圖的頂點(diǎn)數(shù)),已接近于多項(xiàng)式時(shí)間復(fù)雜性.該算法可應(yīng)用于很多能用圖來(lái)描述的模式識(shí)別等實(shí)際問(wèn)題?！?通路與回路通路

：給定無(wú)向圖(或有向圖)G=<V，E>。令v0，v1，…，vm∈V，邊(或弧)e1，e2，…，em∈E，其中vi-1，vi是ei的結(jié)點(diǎn)，交替序列v0e1v1e2v2…emvm稱(chēng)為連接v0到vm的鏈(或路)。v0和vm分別稱(chēng)為鏈(或路)的始結(jié)點(diǎn)和終結(jié)點(diǎn)，而邊(或弧)的數(shù)目稱(chēng)為鏈(或路)的長(zhǎng)度。若v0=vm時(shí)，該鏈(或路)稱(chēng)為圈(或回路)。通路的起點(diǎn)：第一條邊的起點(diǎn)。通路的終點(diǎn)：最后一條邊的終點(diǎn)。

回路:指起點(diǎn)與終點(diǎn)為同一頂點(diǎn)的通路?；就罚簺](méi)有重復(fù)頂點(diǎn)的通路。簡(jiǎn)單通路：沒(méi)有重復(fù)邊的通路。類(lèi)似定義基本回路，簡(jiǎn)單回路。最短路：長(zhǎng)度最短的通路。頂點(diǎn)間的距離d（u，v）：最短路的長(zhǎng)度。d（u，v）≥0d（u，u）=0d（u，v）+d（v，w）≥d（u，w）

n個(gè)頂點(diǎn)的圖中的基本通路的長(zhǎng)度至多為n-1。n個(gè)頂點(diǎn)的圖中的基本回路的長(zhǎng)度至多為n。頂點(diǎn)v到u是可達(dá)的：若v到u有通路。頂點(diǎn)v的可達(dá)集R（v）：指﹛u︱v到u是可達(dá)的﹜例：如圖中

（v1，v2，

v5）是基本通路。（v1，v3，

v6）是簡(jiǎn)單通路。（v1，v2，

v5，v6，

v1）是基本回路也是簡(jiǎn)單回路R（v1）=﹛v1，

v2，

v3，

v5，

v6﹜v1v2v3v4v5v6§4最短路算法1.Moor算法用于求無(wú)向圖G中的兩頂點(diǎn)u到v的最短路.標(biāo)號(hào)法:將u標(biāo)號(hào)為0，若頂點(diǎn)w標(biāo)號(hào)為i，則將與w相鄰的尚未標(biāo)號(hào)的頂點(diǎn)標(biāo)號(hào)為i+1，重復(fù)此過(guò)程直到v標(biāo)上號(hào)。此時(shí)v的標(biāo)號(hào)即u到v的最短路的長(zhǎng)度，u到v的最短路可通過(guò)v的標(biāo)號(hào)回溯其前驅(qū)頂點(diǎn)直到u即得例uv011223232.Dijkstra算法GIS因其強(qiáng)大的功能得到日益廣泛和深入的應(yīng)用。網(wǎng)絡(luò)分析作為GIS最主要的功能之一，在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計(jì)中發(fā)揮了重要的作用，而網(wǎng)絡(luò)分析中最基本最關(guān)鍵的問(wèn)題是最短路徑問(wèn)題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如時(shí)間、費(fèi)用、線路容量等。由于最短路徑問(wèn)題在實(shí)際中常用于汽車(chē)導(dǎo)航系統(tǒng)以及各種應(yīng)急系統(tǒng)等（如110報(bào)警、119火警以及醫(yī)療救護(hù)系統(tǒng)），這些系統(tǒng)一般要求計(jì)算出到出事地點(diǎn)的最佳路線的時(shí)間應(yīng)該在1s～3s內(nèi)，在行車(chē)過(guò)程中還需要實(shí)時(shí)計(jì)算出車(chē)輛前方的行駛路線，這就決定了最短路徑問(wèn)題的實(shí)現(xiàn)應(yīng)該是高效率的。經(jīng)典的最短路徑算法——Dijkstra算法是目前多數(shù)系統(tǒng)解決最短路徑問(wèn)題采用的理論基礎(chǔ)，只是不同系統(tǒng)對(duì)Dijkstra算法采用了不同的實(shí)現(xiàn)方法，目前提出的此類(lèi)最短路徑的算法大約有17種。總體來(lái)說(shuō)，這些算法采用的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)方法由于受到當(dāng)時(shí)計(jì)算機(jī)硬件發(fā)展水平的限制，將空間存儲(chǔ)問(wèn)題放到了一個(gè)很重要的位置，以犧牲適當(dāng)?shù)臅r(shí)間效率來(lái)?yè)Q取空間節(jié)省。目前，空間存儲(chǔ)問(wèn)題已不是要考慮的主要問(wèn)題，因此有必要對(duì)已有的算法重新進(jìn)行考慮并進(jìn)行改進(jìn)，可以用空間換時(shí)間來(lái)提高最短路徑算法的效率。

2.Dijkstra算法

用于求帶權(quán)無(wú)向圖G中從頂點(diǎn)v到其它各頂點(diǎn)的最短路帶權(quán)無(wú)向圖G中的通路的長(zhǎng)度是此通路上每條邊的權(quán)之和.兩個(gè)頂點(diǎn)間的最短路是指長(zhǎng)度最短的通路.§5圖的連通性對(duì)于無(wú)向圖G來(lái)說(shuō)，不難證明結(jié)點(diǎn)間的可達(dá)性是結(jié)點(diǎn)集合上的等價(jià)關(guān)系。因此它將結(jié)點(diǎn)集合給出一個(gè)劃分，并且劃分中的每個(gè)元素形成一個(gè)誘導(dǎo)子圖；兩結(jié)點(diǎn)之間是可達(dá)的當(dāng)且僅當(dāng)它們屬于同一個(gè)子圖，稱(chēng)這種子圖為圖G的連通分圖，圖G的連通分圖的個(gè)數(shù)，記為ω(G)。(1)無(wú)向圖的連通性無(wú)向圖G是連通圖:若G的任兩個(gè)頂點(diǎn)間都有通路.否則為非連通圖.非連通圖有兩個(gè)以上的連通分支(最大的連通子圖).圖G的連通分支個(gè)數(shù)記為ω(G).連通圖w(G)=1非連通圖w(G)=3在圖的研究中，常常需要考慮刪去與增加結(jié)點(diǎn)、結(jié)點(diǎn)集、邊和邊集（或弧集）的問(wèn)題。從圖G=<V,E>中刪去結(jié)點(diǎn)集S，是指作V-S以及從E中刪去與S中的全部結(jié)點(diǎn)相聯(lián)結(jié)的邊而得到的子圖，記作G-S；從圖G=<V,E>中刪去邊集（或弧集）T，是指作E-T，且T中的全部邊所關(guān)聯(lián)的結(jié)點(diǎn)仍在V中而得到的子圖，記為G-T割集與連通度

設(shè)無(wú)向圖G＝<V，E>為連通圖，若有點(diǎn)集V1

V，使圖G刪除了V1的所有結(jié)點(diǎn)后，所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得到的子圖仍是連通圖，則稱(chēng)V1是G的一個(gè)點(diǎn)割集

。若某一個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱(chēng)該結(jié)點(diǎn)為割點(diǎn)。圖(a)中移去割點(diǎn)s后，成為有兩個(gè)連通分支的非連通圖(b)

若G不是完全圖，我們定義

(G)=min﹛

S

︱S是G的點(diǎn)割集﹜為圖G的結(jié)點(diǎn)連通度，它表明產(chǎn)生不連通圖而需要?jiǎng)h去結(jié)點(diǎn)的最少數(shù)目。于是，對(duì)于分離圖G，

(G)=0；對(duì)于存在割點(diǎn)的連通圖G，

(G)=1。思考：完全圖的

(G)=？設(shè)無(wú)向圖G＝<V，E>為連通圖，若有邊集E1

E，使圖G中刪除了E1中的所有邊后得到的子圖是不連通圖，而刪除了E1的任一真子集后得到的子圖是連通圖，則稱(chēng)E1是G的一個(gè)邊割集

。若某一個(gè)邊構(gòu)成一個(gè)邊割集，則稱(chēng)該邊為割邊(或橋)。

與點(diǎn)連通度相似，我們定義非平凡圖G的邊連通度為：λ(G)＝min{∣E1∣

|E1是G的邊割集}，邊連通度λ(G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的邊的最少數(shù)目。對(duì)平凡圖G可定義λ(G)＝0，此外一個(gè)不連通圖也有λ(G)＝0。下面是由惠特尼(H.Whitney)于1932年得到的關(guān)于結(jié)點(diǎn)連通度、邊連通度和最小度的不等式聯(lián)系的定理：對(duì)于任何一個(gè)無(wú)向圖G，

(G)≤

(G)≤δ(G)。證明若G不連通，則k(G)＝λ(G)＝0，故上式成立。

若G連通，

1)證明λ(G)≤δ(G)

如果G是平凡圖，則λ(G)＝0≤δ(G)，若G是非平凡圖，則因每一結(jié)點(diǎn)的所有關(guān)聯(lián)邊必含一個(gè)邊割集，故λ(G)≤δ(G)。2)再證k(G)≤λ(G)

(a)設(shè)λ(G)＝1，即G有一割邊，顯然這時(shí)k(G)＝1，上式成立。

(b)設(shè)λ(G)≥2，則必可刪去某λ(G)條邊，使G不連通，而刪去其中λ(G)-1條邊，它仍是連通的，且有一條橋e＝(u，v)。對(duì)λ(G)-1條邊中的每一條邊都選取一個(gè)不同于u，v的端點(diǎn)，把這些端點(diǎn)刪去，則必至少刪去λ(G)-1條邊。若這樣產(chǎn)生的圖是不連通的，則k(G)≤λ(G)-1＜λ(G)，若這樣產(chǎn)生的圖是連通的，則e仍是橋，此時(shí)再刪去u或v，就必產(chǎn)生一個(gè)不連通圖，故k(G)≤λ(G)。

由1)和2)得k(G)≤λ(G)≤δ(G)k(G)＝2，λ(G)＝3，δ(G)＝4

例veGG′e是G′的割邊

(G′)=1

(G′)=1

(G)=2V是G的割點(diǎn)

(G)=1

(G)=2

(G)=2

定理一個(gè)連通無(wú)向圖G中的結(jié)點(diǎn)v是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn)u和w，使得結(jié)點(diǎn)u和w的每一條路都通過(guò)v

證明若結(jié)點(diǎn)v是連通圖G＝<V，E>的一個(gè)割點(diǎn)，設(shè)刪去v得到子圖G′，則G′至少包含兩個(gè)連通分支。設(shè)其為G1＝<V1，El>，G2＝<V2，E2>，任取u∈V1，w∈V2，因?yàn)镚是連通的，故在G中必有一條連結(jié)u和w的路C，但u和w在G′中屬于兩個(gè)不同的連通分支，故u和w必不連通，因此C必須通過(guò)v，故u和w之間的任意一條路都通過(guò)v。

反之，若連接圖G中某兩個(gè)結(jié)點(diǎn)的每一條路都通過(guò)v，刪去v得到子圖G′，在G′中這兩個(gè)結(jié)點(diǎn)必然不連通，故v是圖G的割點(diǎn)。

(2)有向圖的連通性有向圖G是弱連通的：忽略G的每條邊的方向得到的無(wú)向圖是連通圖。有向圖G是單向連通的：對(duì)G的任兩個(gè)頂點(diǎn)u，v，或有u到v的通路，或有v到u的通路。有向圖G是強(qiáng)連通的：對(duì)G的任兩個(gè)頂點(diǎn)u，v，既有u到v的通路，又有v到u的通路。例單向連通的不是強(qiáng)連通的弱連通的不是單向連通的強(qiáng)連通的在簡(jiǎn)單有向圖中，具有強(qiáng)連通性質(zhì)的最大子圖，稱(chēng)為強(qiáng)分圖

；具有單側(cè)連通性質(zhì)的最大子圖，稱(chēng)為單側(cè)分圖；具有弱連通性質(zhì)的最大子圖，稱(chēng)為弱分圖

。在圖(a)中，由{v1，v2，v3，v4}或{v5}導(dǎo)出的子圖都是強(qiáng)分圖，由{v1，v2，v3，v4，v5}導(dǎo)出的子圖是單側(cè)分圖也是弱分圖。

在圖(b)中，強(qiáng)分圖可由{v1}，{v2}，{v3}，{v4}導(dǎo)出，單側(cè)分圖可由{v1，v2，v3}，{v1，v3，v4}導(dǎo)，弱分圖可由{v1，v2，v3，v4}導(dǎo)出?！?圖的矩陣表示(1)圖G=〈V，E〉的鄰接矩陣：

設(shè)V＝﹛v1,v2,…,vn﹜，圖G=〈V，E〉的鄰接矩陣為：AG＝(aij)n×n，其中aij＝1，若〈

vi,vj〉

E0，若〈

vi,vj〉

Ev1

v2v3v4如圖的鄰接矩陣AG＝0010100101010000鄰接矩陣的性質(zhì)設(shè)V＝﹛v1,v2,…,vn﹜，

圖G=〈V，E〉的鄰接矩陣為AG＝(aij)n×n,則

∑aij=d+（vi），每行的元素之和等于對(duì)應(yīng)頂點(diǎn)的出度?！芶ij=d－（vj），每列的元素之和等于對(duì)應(yīng)頂點(diǎn)的出度。∑∑aij=

E，所有元素之和等于G的邊數(shù)。

AG2中的元素aij（2）表示G中vi到vj長(zhǎng)度為2的通路條數(shù)。

AGk中的元素aij（k）表示G中vi到vj長(zhǎng)度為k的通路條數(shù)。無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)矩陣j＝1ni＝1ni＝1j＝1nn

(2)

圖G=〈V，E〉的可達(dá)矩陣：

設(shè)V＝﹛v1,v2,…,vn﹜，圖G=〈V，E〉的可達(dá)矩陣為：DG＝(dij)n×n，其中

dij＝1，若vi到vj可達(dá)0，若vi到vj不可達(dá)如圖的可達(dá)矩陣DG＝1111111111110001v1v2v3v4

01100000010101010001000000101100000100020110000000可達(dá)矩陣的求法舉例

v1v2v3v4v5鄰接矩陣AG＝AG2＝100020000001100010110000001100000000101110002000001111101001111111111100001AG3＝AG4＝Bn-1

＝I+AG

+AG2+AG3+AG4(I為單位矩陣）1321301001131232211400001DG

＝＝（將Bn-1中非零元素改為1）

（2）關(guān)聯(lián)矩陣：設(shè)V＝﹛v1,v2,…,vn﹜，E＝﹛e1,e2,…,em﹜，圖G=〈V，E〉的關(guān)聯(lián)矩陣為：AG＝(aij)n×m，其中

（3）多重圖的矩陣：圖G=〈V，E〉可用矩陣為AG＝(aij)n×n，其中aij為vi到

vj的邊的條數(shù)。（4）帶權(quán)圖的矩陣：圖G=〈V，E〉可用矩陣為AG＝(aij)n×n，其中aij為vi到

vj的邊的權(quán)值。

aij＝1，若vi與ej關(guān)聯(lián)0，若vi與ej不關(guān)聯(lián)aij＝1，若vi是ej的起點(diǎn)0，若vi與ej不關(guān)聯(lián)－1，若vi是ej的終點(diǎn)G為有向圖G為無(wú)向圖第6章小結(jié)1.圖、子圖、圖同構(gòu)2.頂點(diǎn)的度數(shù)與握手定理3.通路與回路最短路算法5.圖的連通性6.圖的矩陣表示第7章樹(shù)(數(shù)據(jù)結(jié)構(gòu)講解)§1無(wú)向樹(shù)§2根樹(shù)§3二元樹(shù)與前綴碼樹(shù)§4生成樹(shù)§5最小生成樹(shù)算法§1無(wú)向樹(shù)1.無(wú)向樹(shù)的定義無(wú)向樹(shù)：連通無(wú)回路的無(wú)向圖.森林:每個(gè)連通分支都是無(wú)向樹(shù)的無(wú)向圖.樹(shù)葉:度數(shù)為1的頂點(diǎn).分支點(diǎn):度數(shù)不為1的頂點(diǎn).2.無(wú)向樹(shù)的性質(zhì)定理T是樹(shù)當(dāng)且僅當(dāng)T連通而且無(wú)回路.當(dāng)且僅當(dāng)T連通而且m=n-1.當(dāng)且僅當(dāng)T無(wú)回路而且m=n-1.當(dāng)且僅當(dāng)T任兩個(gè)頂點(diǎn)間有唯一的一條通路.當(dāng)且僅當(dāng)T無(wú)回路而且添加一條邊后行成唯一的一條回路.定理

多于兩個(gè)頂點(diǎn)的樹(shù)至少有兩個(gè)葉子.§2根樹(shù)有向樹(shù):將無(wú)向樹(shù)的每條邊加上任意一個(gè)方向得到的有向圖.根樹(shù):有一個(gè)頂點(diǎn)的入度為0而其它頂點(diǎn)的入度均為1的有向樹(shù).根葉子層高度子樹(shù)兒子父親兄弟祖先后代有序樹(shù):每個(gè)分支點(diǎn)的兒子標(biāo)上次序的根樹(shù).二元樹(shù)二元樹(shù)：每個(gè)分支點(diǎn)至多有兩個(gè)兒子（左兒子和右兒子）的有序樹(shù)。完全二元樹(shù)：每個(gè)分支點(diǎn)均有兩個(gè)兒子的有序樹(shù)。完全正則二元樹(shù)：根到每個(gè)葉子的通路長(zhǎng)度均相等的完全二元樹(shù)。多元樹(shù)轉(zhuǎn)化成二元樹(shù)的方法把多元樹(shù)的根作為二元樹(shù)的根，對(duì)每個(gè)頂點(diǎn)v，若v有一個(gè)兒子u，就將這唯一的兒子u做為v的左兒子；若v有多個(gè)兒子，就將v的左兒子做為v的左兒子，將v的其它兒子做為的左兒子的右兒子。112233445566778899101011111212算術(shù)表達(dá)式的二元樹(shù)表示如（a*b）+（c/d-e*f）+（*ab）-（/cd）（*ef）（ab*）（（cd/）（ef*）-）++*/*-abcdef二元樹(shù)的周游（遍歷）二元樹(shù)的周游：訪問(wèn)二元樹(shù)的頂點(diǎn)一次而且僅一次中序周游：中序周游左子樹(shù)，根，中序周游右子樹(shù)。前序周游：根，前序周游左子樹(shù)，前序周游右子樹(shù)。后序周游：后序周游左子樹(shù)，后序周游右子樹(shù)，根。abcdefghi中序周游：dbgiehafc前序周游：abdegihcf后序周游：dighebfca§3二元樹(shù)與前綴碼前綴碼：字符串的集合，每個(gè)字符串均不是其它字符串的前綴。如∑=﹛0，1﹜﹛0，10﹜，﹛00，01，10，111﹜,﹛00，11，100，101﹜都是前綴碼﹛00，01，001，11，101﹜不是前綴碼二元前綴碼與二元樹(shù)一一對(duì)應(yīng)。000000000111111101000011011100100111011最優(yōu)二元樹(shù)（huffman樹(shù)）帶權(quán)樹(shù)：每個(gè)葉子帶有權(quán)值的樹(shù)。帶權(quán)樹(shù)的權(quán)：每個(gè)葉子的權(quán)wi與其通路長(zhǎng)度li之積的和。即最優(yōu)二元樹(shù):給定n個(gè)葉子的權(quán)的二元樹(shù)中權(quán)值最小的二元樹(shù)。最佳前綴碼：最優(yōu)二元樹(shù)對(duì)應(yīng)的前綴碼?！苭i*

lii=1n235625362356000001011Huffman算法求給定n個(gè)權(quán)w1≤w2≤…≤wn的最優(yōu)二元樹(shù)----Huffman算法

連接權(quán)最小的兩個(gè)結(jié)點(diǎn)w1,w2作為一個(gè)權(quán)為w1+w2分支點(diǎn)；重復(fù)此步驟n-1次，每次連接余下的權(quán)最小的兩個(gè)結(jié)點(diǎn)得到一個(gè)分支點(diǎn)，直到行成n-1個(gè)即得最優(yōu)二元樹(shù).例：求給定6個(gè)權(quán)2，4，6，8，10，12的最優(yōu)二元樹(shù)及其權(quán)值24681012612182442其權(quán)為（2+4）×4+6×3+（8+10+12）×2=102§4生成樹(shù)G的生