第10章圖論

06/14/2013

原版教學(xué)配套課件

學(xué)習(xí)目標(biāo):

通過(guò)本章的學(xué)習(xí)，要掌握如下內(nèi)容,

活運(yùn)用的程度:

基本概念

路與回路

圖的矩陣表示

有向圖和可達(dá)性矩陣

歐拉圖與哈密爾頓圖

?樹(shù)

根樹(shù)及其應(yīng)用

二部圖和平面圖

06/14/2013*^^^

2013-3-13

原版教學(xué)配套課件

10.1基本概念

f10.1.1圖的基本概念

現(xiàn)實(shí)世界中很多狀態(tài)可以用某種圖形來(lái)描述，這種圖形

是由一些點(diǎn)和一些連接兩點(diǎn)間的連線所組成，對(duì)于點(diǎn)的

位置及連線的長(zhǎng)度無(wú)關(guān)緊要。

例如，有〃、b、C、d四個(gè)足球隊(duì)進(jìn)行友誼比賽。為了描

述4個(gè)隊(duì)之間比賽的情況，可以用圖104來(lái)表示。

在圖104中4個(gè)小圓圈分別表示這

四個(gè)足球隊(duì)，稱之為結(jié)點(diǎn)。如果兩

隊(duì)進(jìn)行過(guò)比賽，則在表示這兩隊(duì)的

結(jié)點(diǎn)之間用一條線連接起來(lái)，稱之

為邊。

06/14/2013*^^^^

2013-3-133

原版教學(xué)配套課件

10.1基本概念

設(shè)A,5為任意的｛(a,八〃￡5｝兩個(gè)集合，稱為A

和5的無(wú)序偶集。同理，｛<a,A〃￡5｝為A和5

為有序偶集。

定義10-1一個(gè)圖G是一個(gè)三元組，G=<V(G),E(G),

66,其中V(G)是一個(gè)非空的結(jié)點(diǎn)集合，￡(G)是邊的集

合，0G是從邊集合￡到結(jié)點(diǎn)無(wú)序偶集或有序偶集合上的

函數(shù)。

一般情況下，G=<V(G),￡(G),簡(jiǎn)寫(xiě)為G=vV(G),

￡(G)>或G=<匕E>

以上是無(wú)向圖與有向圖的集合定義，若用圖形表示它

們，即用小圓圈(或?qū)嵭狞c(diǎn))表示結(jié)點(diǎn)，用結(jié)點(diǎn)之間的連

線表示無(wú)向邊，用有方向的連線表示有向邊。

()6/14/201

2013-3-134

原版教學(xué)配套課件

<?例10”圖舉例。

⑴給定無(wú)向圖G=vHG),E(G),0G>,其中b,

c,d}9E(G)={g,e2,eve5,e6],0G(4)=(〃，

0G應(yīng))=(〃，b),久(——(a,c),<^G(e4)=(a,d),

0G⑷8，或，0G(%)=(。，砌。

(2)給定有向圖。=vV(O),E(D),①金,其中V心)={〃,

b,c,d,e,f},E(D)={et,e2,e4,e5,e6,勺},

0o(eP=va,a>,①D(e)=〈a,b>,(^3)=<b,a>,

<c

①D(Q)=<d,〃>,①口&)-，b>,①0儲(chǔ)6)-<c'd>，

%(C7)=vc，d>,(^8)=</,,f>o

()6/14/201

2013-3-135

原版教學(xué)配套課件

?畫(huà)出G與O的圖形。

解圖10?2中3),S)分別給出了無(wú)向圖G和有向圖。的圖

形。

()6/14/201

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

定義10?2如果兩個(gè)結(jié)點(diǎn)之間有多條邊(對(duì)于有向圖，則有

多條同方向的邊)，則稱這些邊為平行邊，兩相結(jié)點(diǎn)〃，b

間平行邊的條數(shù)稱為邊的重?cái)?shù)。含有平行邊的圖稱為多

重圖，不含平行邊和自回路的圖稱為簡(jiǎn)單圖。

10.1.2圖中結(jié)點(diǎn)的度數(shù)

我們常常需要關(guān)心圖中有多少條邊與某一結(jié)點(diǎn)關(guān)聯(lián)，這

就引出了圖的一個(gè)重要概念一一結(jié)點(diǎn)的度。

定義10?3設(shè)圖G是無(wú)向圖，u是圖G中的結(jié)點(diǎn)，所有與u關(guān)

聯(lián)的邊的條數(shù)(有自回路時(shí)計(jì)算兩次)，稱為點(diǎn)u的度數(shù)，

記作deg")。

如圖10-2(〃)中，deg(a)=59deg(b)=2,deg(c)=2,deg(d)

=3o06/14/2013*^^^^

2013-3-137

原版教學(xué)配套課件

算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

定理104設(shè)圖G=vV(G),E(G),0G＞是具有〃個(gè)點(diǎn)，m條

邊的無(wú)向圖，其中結(jié)點(diǎn)集合為{匕，v2,vn},貝！J

工deg(匕)=2m

證明因?yàn)镚中每條邊都與兩個(gè)結(jié)點(diǎn)關(guān)聯(lián)，每條邊均提供2

度，所以在計(jì)算G所有結(jié)點(diǎn)度數(shù)之和時(shí)，加條邊共提供了

2見(jiàn)度，由此結(jié)論成立。

定理10?2設(shè)圖G=vV(G),E(G),①G＞是具有n個(gè)點(diǎn)，m

條邊的有向圖，其中結(jié)點(diǎn)集合為V={vl,v2,vn),

貝IJ

〃nn

ydeg(v,)=2幾且￡deg+(v,)=^deg一(匕)nn

如圖10.2(辦)甲，deg+(a)—2,deg“8)=3,deg+(b)=1,deg"

(A)=2,deg+(c)=3,deg-(c)=0,deg+(d)=1,deg(d)=

+

2,deg+(e)=0,deg(e)=0,deg(f)=1,deg(f)=lo

()6/14/20

2013-3-138

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

推論圖G中度數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。

證明設(shè)G二vV(G),E(G)＞為任意圖，VI和V2分別是G中

奇數(shù)度數(shù)和偶數(shù)度數(shù)的結(jié)點(diǎn)集，VIUV2=V,

VinV2=O,由定理10?1知

Z〃g(v)=Z〃g(v)+Zdeg(v)=2m

由于是寓數(shù)之和二必為偶教？而21ml也為偶數(shù)，故是偶

數(shù)。由此IV1I必為偶數(shù)。

定義10?4在圖中，度數(shù)為0的結(jié)點(diǎn)稱為孤立點(diǎn)。

如圖101(b)中，結(jié)點(diǎn)e為0度，是一個(gè)孤立點(diǎn)。

10.1.3幾種常見(jiàn)的圖

定義10?5具有〃個(gè)結(jié)點(diǎn)和機(jī)條邊的圖稱為(〃，帆)圖。一個(gè)

(〃，0)圖稱為零圖(即該圖只有〃個(gè)孤立結(jié)點(diǎn))。只有一個(gè)

結(jié)點(diǎn)的圖，即(1,0)圖稱為平凡圖。06/14/2013*^^^^

2013-3-139

原版教學(xué)配套課件

定義10?6任意兩個(gè)不同的結(jié)點(diǎn)都是鄰接的簡(jiǎn)單圖稱為完

全圖?！▊€(gè)結(jié)點(diǎn)的無(wú)向完全圖記為屋〃其邊的條數(shù)為〃（小

1）/2o

從圖10?3中的嗎和（看出嗎有3條邊，（有6條邊。容

易證明（有n（n?l）/2條邊。

定義10?7設(shè)G=vV（G）,E（G）＞是一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單

圖。以V為結(jié)點(diǎn)集，以從完全圖（中刪去G的所有邊后得

到的圖稱為G的補(bǔ)圖（或稱為G的補(bǔ)），記為。G

如圖10?4給出了一個(gè)圖G和G的補(bǔ)3。

()6/14/201

2013-3-1310

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

定義10?8給每條邊賦以一個(gè)實(shí)數(shù)(稱為該邊的權(quán))的圖叫

有權(quán)圖。邊e的權(quán)常記為沙G(e)。有權(quán)圖G=vV(G),

￡(G)＞中所有邊的權(quán)之和稱作圖G的權(quán)，記為WG(G)O

例10?2證明在任何一個(gè)有6個(gè)人的小組中，存在3個(gè)人

互相認(rèn)識(shí)，或者存在3個(gè)人互相不認(rèn)識(shí)(拉姆齊問(wèn)題)。

分析用6個(gè)結(jié)點(diǎn)來(lái)代表人，并用鄰接性來(lái)表示兩人之間

認(rèn)識(shí)關(guān)系。這樣一來(lái)，該例就是要證明：任意一個(gè)有6

個(gè)結(jié)點(diǎn)的圖G中，或者有3個(gè)互相鄰接的點(diǎn)，或者有3

個(gè)互相不鄰接的點(diǎn)。即，對(duì)任何一個(gè)有6個(gè)結(jié)點(diǎn)的圖

G,G或中含有一個(gè)三角形(即()。

()6/14/20

2013-3-1311

原版教學(xué)配套課件

證明^G=<V(G),E(G)>,\V\=6,u是G中一結(jié)點(diǎn)。因?yàn)?/p>

u與G的其余5個(gè)結(jié)點(diǎn)或者在G中鄰接，或者在中鄰接。

故可假定，有3個(gè)結(jié)點(diǎn)匕，v2,匕在G中與u鄰接。

如果這3個(gè)結(jié)點(diǎn)中有兩個(gè)結(jié)點(diǎn)(如匕，匕)鄰接，則它們與u

就是G中一個(gè)三角形的3個(gè)頂點(diǎn)。如果這3個(gè)結(jié)點(diǎn)中任意

兩個(gè)在G中均不鄰接，貝Wi，v2,匕就是G中一個(gè)三角形

的3個(gè)頂點(diǎn)。

10.1.4子圖

在描述和研究圖的性質(zhì)時(shí)，還涉及到另一重要概念子

圖。

定義10.9設(shè)有圖G=vV,和圖G=vH,E，>。

(1)若V，V,E，E,則稱G是G的子圖。

(2)若G是G的子圖，且?中E,則稱G是G的真子圖。

(3)若v，=y,E'E,則稱G，是G的生成子圖。()6/14/201

2013-3-1312

原版教學(xué)配套課件

圖10?5給出了圖G以及它的真子圖5和生成子圖G2。

V\V4p.P4

G&G?

圖10-5圖G以及其具干圖&和生成千圖俏

()6/14/201

2013-3-1313

原版教學(xué)配套課件

定義10.10如果圖G中的一個(gè)子圖是通過(guò)刪去圖G的結(jié)點(diǎn)集V的一個(gè)

子集匕的所有結(jié)點(diǎn)及與其關(guān)聯(lián)的所有邊得到的，則將該子圖記為G-

匕。

?如圖10如中,G7=G-{V4}O

定義10-11如果圖G中的一個(gè)子圖是通過(guò)刪去圖G的邊集￡的一個(gè)子

集約的所有邊，而不刪去它們的端點(diǎn)而得到的，則將該子圖記為G-

EjO

如圖10-5中，G2=G-{(vPv5)}o

10.1.5圖的同構(gòu)

從圖的定義可以看出，圖的最本質(zhì)的內(nèi)容是結(jié)點(diǎn)與結(jié)點(diǎn)的鄰接關(guān)

系。例如圖也可以用圖10-6中幾種不同形狀的圖形表示。它們

與圖10-1一樣，都同樣表示4個(gè)隊(duì)之間的比賽情況。從這個(gè)意義上

講，我們說(shuō)它們是同一個(gè)圖，并稱圖10-1與圖10-6的(加和(b)是同

構(gòu)的。

()6/14/201

2013-3-1314

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

圖10-6圖同料示例

()6/14/201

■B1LH2013-3-1315

原版教學(xué)配套課件

定義1042設(shè)有圖G=vV,和圖G，=vV"球＞。如果

存在雙射g：使得e=（〃，v）eE,?，=（&（〃），

1一））￡￡',且包,刃與（g（〃），g⑺）有相同的重?cái)?shù)，則

稱G與G，同構(gòu)。記作G2G、

例10?3考察圖例，中的兩個(gè)圖G=（V,￡）和G，=（—,

很容易看出，定義g：g（匕?）=吟，可以驗(yàn)證g

滿足定義10?12的雙射，所以GgG，。

()6/14/201

16

/10.2.1路、路和連通性

定義10?13給定圖G=(V,E)o設(shè)%,匕，…，vkey,

辦，。2，…，/￡￡,其中G是關(guān)聯(lián)于結(jié)點(diǎn)匕1和匕的邊，稱

交替序列%々呼2…冬也為連接％到雁的路，路中邊的數(shù)目

女稱作路的長(zhǎng)度。

定義又?14設(shè)〃=%產(chǎn)及2…7限是圖G中連接以0到限的路。

(1)若｛=限，則稱路〃為回路；

(2)若與，⑦，…，叫都不相同，則稱路〃為跡；

(3)若為，匕，…，也都不相同，則稱路〃為通路；

(4)長(zhǎng)度大于2的閉的通路(即除嗎=咋外，其余結(jié)點(diǎn)均

不相同的路)〃稱作回路。

.

例如在圖10?8,其中，連接匕到女的路有喔。6y/，5,

這也是一條跡，還是一條通路；

路V/O47V是一條回路，但不是回路；

路U/O4為是一條回路，也是回路。

在簡(jiǎn)單圖中，一條路與e產(chǎn)/與…,唳完全由它的結(jié)點(diǎn)序列

與匕…唳確定。所以簡(jiǎn)單圖的路可由結(jié)點(diǎn)序列表示。

如圖10.l表示的簡(jiǎn)單圖中,

路可寫(xiě)成O

06/14/20LW

2013-3-1318

原版教學(xué)配套課件

（下面我們利用通路的概念解決一個(gè)古老的著名問(wèn)題。

例10?4（渡河問(wèn)題）一個(gè)擺渡人，要把一只狼、一只羊和

一捆干草運(yùn)過(guò)河去，河上有一只木船，每次除了人以

夕卜，只能帶一樣?xùn)|西。并且，如果人不在旁時(shí)，狼就要

吃羊，羊就要吃干草。問(wèn)這人應(yīng)該怎樣才能把它們運(yùn)過(guò)

河去？

解用F表示擺渡人，W表示狼，S表示羊，H表示干

草。

如果用尸表示人和其他三樣?xùn)|西在河的左岸。這

樣，在FWSFWHFSH

FSFH

磔WHSHF

WSH

()6/14/201

2013-3-1319

原版教學(xué)配套課件

這里0表示左岸是空集，即人、狼、羊、干草都已運(yùn)到

右岸去了O

根據(jù)題意，考查一下這16種情況就可以知道，其中有6

種情況不允許出現(xiàn)。它們分別是：WSH.FW.FH、

WS.SH、Fo如尸H表示人和干草在左岸，而羊和狼在

右岸，狼要吃羊，這當(dāng)然是不行的。因此，允許出現(xiàn)的

情況只有10種，如圖10?9所示。

WH

圖10.9河在你允許世去

定義10-15在圖G中，若結(jié)點(diǎn)匕到匕有路連接（這時(shí)稱匕和匕是連通的），

則其中長(zhǎng)度最短的路稱為從匕到匕的短程。短程的長(zhǎng)度稱為匕到匕的距

離，用符號(hào)〃（匕，嚀）表示。

?例如在圖10-8中，d（yv匕）=2。

定理10-3設(shè)G是具有〃個(gè)結(jié)點(diǎn)的圖，如果從結(jié)點(diǎn)匕到另一結(jié)點(diǎn)匕存在

一條路，則其短程是一條長(zhǎng)度不大于的通路。

證明設(shè)從結(jié)點(diǎn)匕.到結(jié)點(diǎn)匕存在一條路〃，該路上的結(jié)點(diǎn)序列為

匕.…女…可用反證法證明，當(dāng)〃是短程時(shí)，〃一定是通路。

推論設(shè)圖G=（V,E）,\V\=n,則G中任一回路長(zhǎng)度不大于〃。

定義10-17如果一個(gè)圖的任何兩個(gè)結(jié)點(diǎn)之間都有一條路，那么我們稱

這個(gè)圖是連通的，否則是不連通的。

()6/14/201

2013-3-1321

原版教學(xué)配套課件

定義10?18圖G的一個(gè)連通的子圖（稱為連通子圖）若不包

含在G的任何更大的連通子圖中，它就被稱作G的連通分

支，常把圖G的連通分支數(shù)記作W（G）。

在圖10?10中，G是不連通的，W（G）=2,而G，是連通

的，W（G，）=L

任何一個(gè)圖都可劃分為若干個(gè)連通分支。顯然，僅當(dāng)圖

G的連通分支數(shù)W（G）=1時(shí)，圖G是連通的。

S10-10圖連遹分文示例

()6/14/201

2013-3-1322

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

(10.2.2有權(quán)圖的最短路徑問(wèn)題

有權(quán)圖經(jīng)常出現(xiàn)在圖的應(yīng)用中。如在交通圖中，權(quán)可以

表示兩地的距離；在通訊圖中，權(quán)可以表示各種通訊線

路的建造或維修費(fèi)用等等。

定義1049有權(quán)圖G中，連接兩個(gè)結(jié)點(diǎn)匕和，的路〃的權(quán)是

〃中各邊的權(quán)之和，記為WG(〃)。

首先，用反證法證明邊權(quán)為正的最短路徑有這樣的性

U

質(zhì)：若〃0%…是從〃。到〃加的最短路徑，則〃…m-

7是從〃。到〃3］的最短路徑。

這樣，假設(shè)S為圖G中按長(zhǎng)度遞增的次序已求出的最短路

徑的終點(diǎn)的集合，則下一條長(zhǎng)度較長(zhǎng)的最短路徑的終點(diǎn)〃

(如下:06/14/20^^^^^

2013-3-1323

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

令二對(duì)于考慮每個(gè)七es,若有這樣的邊，將從

結(jié)點(diǎn)壬到結(jié)點(diǎn)，的邊連接在從〃。到天的最短路徑后面，這樣

就構(gòu)成了從〃。至〃的1條不同的路（若圖中有邊（即,則

是其中的一條路）。選出這1條路中的最短路，并設(shè)該

路長(zhǎng)為0（，令0（〃）=加質(zhì){￡＞（，）〃￡},則由上面所述性質(zhì)

知，〃即為所求結(jié)點(diǎn)。由此可知，即到所求結(jié)點(diǎn)〃的最短

路徑或是路〃0〃，或是以S中的點(diǎn)作為中間結(jié)點(diǎn)的路。

綜上所述，可得迪克斯特拉算法步驟如下：

（1）把V分成兩個(gè)子集3和=%3,初始時(shí)S={〃。},

?令D①昨）為

WG(〃0,i)(〃0,/)eE=

■M1LH

其中WG(〃o,i)是G中的邊(“0,i)的權(quán)，而為表示某個(gè)足夠大的數(shù)。

(2)找中的點(diǎn)〃，使。(〃)=機(jī)加{。⑶植右，則。(〃)就是〃。到〃的最短路徑

長(zhǎng)度。

(3)將點(diǎn)〃從中刪除并加入集合S中，即置S為SU{〃/置為-{u}。

(4)若SWV,則修改的值，其方法是：若有(〃，￡)￡￡(〃是由

步驟2選出的)，則置為相加{。(。，O(〃)+WG(〃，/)},轉(zhuǎn)2。

?(5)若8=匕則算法結(jié)束。

因?yàn)樵撍惴繄?zhí)行一次(以執(zhí)行算法步驟2?4一遍為一次)，選取一

個(gè)有最短路徑的結(jié)點(diǎn)U,所以圖中結(jié)點(diǎn)全部處理完要執(zhí)行IVI-1次。

為清楚起見(jiàn)，將本算法用流程圖表示，見(jiàn)圖10-11。

()6/14/201

2013-3-1325

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

圖10-11他克斯特技算法流程圖

()6/14/201

2013-3-1326

原版教學(xué)配套課件

例10?5在圖1042所示的有權(quán)圖中，用迪克斯特拉算法求

結(jié)點(diǎn)vO到其余各點(diǎn)的最短路徑。

解初始狀態(tài)為

?S={vO},

?S={vl,v2,v3,v4,v5,v6},

?D(vl)=2,

?D(v2)=3,

?D(v3)=5,

?D(V4)=8,

?D(v5)=°°,

?D(v6)=5o

BIO-12例io4品短骼役

()6/14/201

2013-3-1327

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

算法共執(zhí)行6次，求解示意圖如圖1043所示。

?第1次

?(1)S中有最小D值的結(jié)點(diǎn)為vL選=丫1。置S為SU{u}

={v0,vl)；

?⑵置S為S?{u}={v2,v3,v4,v5,v6}o

?⑶修改S中諸元素的D值如下：

?D(v2)-min{D(v2),D(vl)+WG(vl,v2)}=min{3,

2+00}=3

?D(v3)-min{D(v3),D(vl)+WG(vl,v3)}=min{5,

2+2}=4

?D(v4)-min{D(v4),D(vl)+WG(vl,v4)}=min{0°,

2+oo}=°o

06/14/2013*^^^^

?同理有D(v5)=9,D(v6)=5o

2013-3-1328

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

v.(s)

S?%ls-I**.?1Is”、??.?*!

(5)

()6/14/201

■BILH2013-3-1329

原版教學(xué)配套課件

vt（2）

v/））

-k*?.、AC

第2次（6）

圖10-13例10-5農(nóng)解

?(1)S中有最小D值的結(jié)點(diǎn)為V2,選U=V2。

?⑵置S為SU{u}={vO,vl,v2},置S為S-{u}={v3,

v4,v5,v6}o

?⑶修改S中諸元素的D值，求得

?D(v3)=4,D(v4)=8,D(v5)=9,D(v6)=5o

第3次到第6次的過(guò)程請(qǐng)讀者自己試著補(bǔ)出來(lái)。

（）6/14/2叩）

2013-3-1330

原版教學(xué)配套課件

10.3圖的矩陣表示

上面介紹了圖的一種表示方法一一用圖形表示圖。它的

優(yōu)點(diǎn)是形象直觀，但是這種表示在結(jié)點(diǎn)與邊的數(shù)目很多

時(shí)是不方便的。下面介紹另一種表示方法一一用矩陣表

示圖。利用這種方法，可以把圖用矩陣存儲(chǔ)在計(jì)算機(jī)

中，利用矩陣的運(yùn)算還可以了解到它的一些有關(guān)性質(zhì)。

定義10?20設(shè)G=(V,E)是有n個(gè)結(jié)點(diǎn)的圖，貝!jn階方陣A

=(%)稱為G的鄰接矩陣。其中

1(V.,V;)GE

(J..=<

0(vz.,vy)E

06/14/2013^^^^

j2013-3-1331

原版教學(xué)配套課件

如圖1044所示的圖G,其鄰接矩陣A為

,01010、

1o111

A=01001

11000

"1100,

顯然，無(wú)向圖的鄰接矩陣一定是對(duì)稱的。

在鄰接矩陣A的幕A2,A3,…矩陣中，每個(gè)元素有特定

的含義，下面定理10?4進(jìn)行了說(shuō)明。

()6/14/201

2013-3-1332

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

定理10-4設(shè)G是具有n個(gè)結(jié)點(diǎn)集｛vLv2,vn｝的圖，其鄰接矩陣

為A,則A1(1=L2,…)的(i,j)項(xiàng)元素a(l)ij是從vi到vj的長(zhǎng)度等于1

的路的總數(shù)。

證明對(duì)1用數(shù)學(xué)歸納法。

當(dāng)1=1時(shí)，A1=A,由A的定義，定理顯然成立。

若l=k時(shí)定理成立，則當(dāng)l=k+l時(shí)，Ak+l=AkXA,所以

?若包=￡d)%

r=l

由定理10-4和定理10-3可得出以下結(jié)論：

(1)如果對(duì)1=1,2,???,n-1,Al的(i,j)項(xiàng)元素(i#j)都為零,那么

vi和vj之間無(wú)任何路相連接，即vi和vj不連通。因此，vi和vj必屬

于G的不同的連通分支。

(2)結(jié)點(diǎn)vi到vj(iWj)間的距離d(vi,vj)是使A1(1=L2,n?l)的

(i,j)項(xiàng)元素不為零的最小整數(shù)1。

⑶A1的(i,i)項(xiàng)元素a(l)ii表示開(kāi)始并結(jié)束于vi長(zhǎng)度為1的回路的數(shù)

目。

()6/14/20

2013-3-1333

原版教學(xué)配套課件

例10?6圖G=（匕￡）的圖形如圖10?15,求鄰接矩陣A和

A2,A3,A4,并分析其元素的圖論意義。

?解：

(01000、,01000、’01oooWi0100、

10100101001010002000

A=01000A2=01000X0100010100

00001000010000100001

00107<00010,<0001070010,

'02000、(20200、

2020004000

A'=02000AJ20200

0000100010

^00010；(.00001；

()6/14/201

2013-3-1334

原版教學(xué)配套課件

(1)由A中〃⑴12=1知，匕和-是鄰接的;由43中〃(3)12=2

知，匕到匕長(zhǎng)度為3的路有兩條，從圖中可看出是u產(chǎn)217產(chǎn)2

和U產(chǎn)2y3y2。

(2)由A2的主對(duì)角線上元素可知，每個(gè)結(jié)點(diǎn)都有長(zhǎng)度為2

的回路，其中結(jié)點(diǎn)匕有兩條：U2V產(chǎn)2和叱匕乙，其余結(jié)點(diǎn)只

有一條。

(3)由于A3的主對(duì)角線上元素全為零，所以山

為3的回路。/u

(4)由于屈1)34=/2)34=〃(3)34=〃")34=。，所L

無(wú)路，它們屬于不同的連通分支。⑸或匕，I1,

對(duì)于其他元素讀者自己找出其意義。\

VJ

圖10-15米錦結(jié)矩陣

()6/14/203

原版教學(xué)配套課件

10.4有向圖和可達(dá)性矩陣

/10.4.1有向圖

在動(dòng)態(tài)狀態(tài)中，例如計(jì)算機(jī)的流程系統(tǒng)中，有向圖常常

比無(wú)向圖更有應(yīng)用價(jià)值。因此，了解有向圖的相關(guān)概念

和性質(zhì)是非常必要的。

定義10?21設(shè)G是一個(gè)有向圖，結(jié)點(diǎn)u的出度和入度分別

是以u(píng)為弧尾和以u(píng)為弧頭的弧的條數(shù)，分別記作"空+⑺

與血夕⑴)。結(jié)點(diǎn)u的出度和入度之和稱作結(jié)點(diǎn)u的度，記作

deg")°

06/14/2013*^^^

2013-3-1336

原版教學(xué)配套課件

如在圖10?16所表示的有向圖中，有

血夕(匕)=2,deg-(y^=l,4"(匕)=3

deg+(>2)=l，degiy^)=1,deg(v2)=2

+

deg(y^=1,deg,(匕)=1,deg(y3)=2

deg+W/=l,%(乙)=2,deg(v^=3

無(wú)向圖中的路、跡、通路和回路的

概念都適用于有向圖中，只是弧的

方向必須與路的方向相一致。即有

向圖G中一條（有向）路是結(jié)點(diǎn)和弧

的交替序列

W=r0eirie2V2--ekVkf使得每條弧《從

匕」開(kāi)詔匕處結(jié)束。圖10-16有向圖示例

06/14/2QU/

2013-3-1337

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

定義10-22在有向圖中，若有一條從結(jié)點(diǎn)匕到結(jié)點(diǎn)匕的路，則稱匕到匕

是可達(dá)的。

例如，圖10-16中結(jié)點(diǎn)匕到結(jié)點(diǎn)』有匕』和匕2匕/兩條路，故匕到匕可

達(dá)的。

?定義10-23設(shè)有有向圖G,

(1)若略去弧的方向后，G成為連通的無(wú)向圖，則稱G是弱連通的；

(2)若G中任意兩個(gè)結(jié)點(diǎn)之間，至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)

的，則稱G是單向連通的；

(3)若G中任意兩個(gè)結(jié)點(diǎn)之間是相互可達(dá)的，則稱G是強(qiáng)連通的。

從定義可知：若圖G是單向連通的，則必是弱連通的；若圖G是強(qiáng)連

通的，則必是單向連通的，且也是弱連通的。但反之不成立。

06/14/2013*^^^^

■M1LH2013-3-1338

原版教學(xué)配套課件

如圖1047所示，根據(jù)定義10?23可以得出3個(gè)有向圖中:

（加是強(qiáng)連通的，是單向連通的，（c）是弱連通的。

S10-17育同圖連遹性的示例

()6/14/201

2013-3-1339

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

定理10?5一個(gè)有向圖G是強(qiáng)連通的，當(dāng)且僅當(dāng)G中有一個(gè)

(有向)回路，它至少包含每個(gè)結(jié)點(diǎn)一次。

?證明

(1)必要性：如果有向圖G是強(qiáng)連通的，則任意兩個(gè)結(jié)點(diǎn)

都是相互可達(dá)的。故必有一回路經(jīng)過(guò)圖中所有各結(jié)點(diǎn)。

否則，必有一條回路不包含某一結(jié)點(diǎn)匕。這樣，匕與回路

上各結(jié)點(diǎn)就不能相互可達(dá)，這與G是強(qiáng)連通矛盾。

(2)充分性：如果G中有一個(gè)回路，那么它至少包含每個(gè)

結(jié)點(diǎn)一次，則G中任意兩個(gè)結(jié)點(diǎn)是相互可達(dá)的，故G是強(qiáng)

連通的。

例如，圖中圖(〃)是強(qiáng)連通的，有一回路為

匕方匕匕，它包含圖中所有結(jié)點(diǎn)。06/14/2013*^^^^

2013-3-1340

原版教學(xué)配套課件

定義10.24在有向圖G=（V,￡）中，設(shè)G，是G的子圖。若

G，是強(qiáng)連通的（單向連通的、弱連通的），G中沒(méi)有包含G，

的更大的子圖是強(qiáng)連通的（單向連通的、弱連通的），則稱

G，是G的強(qiáng)分圖（單向分圖、弱分圖）。

在圖10?18的有向圖中，因?yàn)榻Y(jié)點(diǎn)訶與任何別的結(jié)點(diǎn)都不

相互可達(dá)，也可稱為（｛%｝,。）是一個(gè)強(qiáng)分圖。

可以看出該有向圖的強(qiáng)分圖的集是：

｛（｛匕/2/3｝，｛與《2，％｝），（｛也｝，°），（｛%｝，0），（｛如，°）｝；

?弱分圖的集是：人飛.引

｛（｛》，叱，勺匕，%與｝，。/'\打

算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

若在結(jié)點(diǎn)集V上定義關(guān)系。為：匕夕！當(dāng)且僅當(dāng)4和匕?在同

一強(qiáng)(弱)分圖中。容易證明，。是一個(gè)等價(jià)關(guān)索。這

種等價(jià)關(guān)系把V中的結(jié)點(diǎn)分成若干個(gè)等價(jià)類，等價(jià)類的集

合是V上的一個(gè)劃分。每一個(gè)等價(jià)類的結(jié)點(diǎn)以及相應(yīng)的邊

導(dǎo)出一個(gè)強(qiáng)(弱)分圖。由此有下面的定理。

定理10?6在有向圖6=(V,E)中，G的每一個(gè)結(jié)點(diǎn)都

在也只在一個(gè)強(qiáng)(弱)分圖中。

10.4.2有向圖的可達(dá)性

下面用矩陣來(lái)研究有向圖的可達(dá)性。

與無(wú)向圖一樣，有向圖也能用相應(yīng)的鄰接矩陣4=(4.)

表示，其中p(<匕，勺〉￡均

“"jo(<vz.,vy>^E)

注意，這里A不一定是對(duì)稱的。

()6/14/201A

2013-3-1342

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

則〃階方陣。=%）稱為圖G的可達(dá)性矩陣。其中

1（匕到v-可達(dá)）

IzJ

Pij\o（匕到匕不可達(dá)）

IJ

根據(jù)可達(dá)性矩陣，可知圖中任意兩個(gè)結(jié)點(diǎn)之間是否至少

存在一條路以及是否存在回路。

由10.2節(jié)定理10?3及其推論可知，利用有向圖的鄰接矩陣

A,分以下兩步可得到可達(dá)性矩陣。

?（1）令5〃=A+A2+…+4%

（2）將矩陣3〃中不為零的元素均改為1,為零的元素

不變，所得的矩陣P就是可達(dá)性矩陣。

（）6/14/2013<^^

2013-3-1343

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

一種簡(jiǎn)便的方法。

因?yàn)榭蛇_(dá)性矩陣是一個(gè)元素僅為I或0的矩陣（稱為布

爾矩陣），而在研究可達(dá)性問(wèn)題時(shí)，對(duì)兩個(gè)結(jié)點(diǎn)間有路

的數(shù)目并不感興趣，所關(guān)心的只是兩結(jié)點(diǎn)間是否存在

路，所以，可將矩陣A,A2,A"分別改為布爾矩陣A

⑴，A⑵，…，A⑻o

說(shuō)明集合｛0,1｝中的二元運(yùn)算八和V定義如下：

0V0=0OV1=1VO=1V1=1

1A1=11AO=OA1=OAO=O

分別稱八、V為布爾加和布爾乘積運(yùn)算。

()6/14/20

2013-3-1344

原版教學(xué)配套課件

定義10?26兩個(gè)布爾矩陣中，若將矩陣運(yùn)算中元素的相加

和相乘均規(guī)定為布爾加和布爾乘，則這種矩陣運(yùn)算稱為

布爾矩陣運(yùn)算，相應(yīng)的矩陣加法和乘法稱為矩陣的布爾

加V和布爾乘八。

?由此有

A⑵=A(1)AA(1)=AAA

A(3)=A(2)AA(0

A(n)=A(n-1)AA⑴

P=A⑴VA⑵V...VA⑺

例10?7求出圖10?19所示圖的可達(dá)性矩陣。

解該根據(jù)圖示，可得鄰接矩陣為：

"0100"

0010

A=

1100

J110,

A⑴-A圖10-19戲可達(dá)矩陣

<0100］僅100、'0010、,1100、'0110、

0100010110001101110

A心=4（釣=

1001100011011101110

11?U110?J110；U1107(1110,

‘1110、

人心+人⑵+心+心二1,10

1110

U11oj

()6/14/201

2013-3-1346

原版教學(xué)配套課件

計(jì)算機(jī)應(yīng)用數(shù)學(xué)基礎(chǔ)

定理10?7有向圖G是強(qiáng)連通的當(dāng)且僅當(dāng)其可達(dá)性矩陣P除

主對(duì)角線外，其他元素均為1。

下面介紹如何利用一個(gè)圖的可達(dá)性矩陣，求出這個(gè)圖的

強(qiáng)分圖。

設(shè)尸=(pQ是圖G的〃階可達(dá)性矩陣，P'是P的轉(zhuǎn)置矩

陣，定義矩陣運(yùn)算P尸為

由定義，如果從結(jié)點(diǎn)匕到，是可達(dá)的，則應(yīng)有

〃=1；如果從結(jié)點(diǎn)，到匕是可達(dá)的，則應(yīng)有P7=1o因

此，結(jié)點(diǎn)匕.和匕.是相互可達(dá)的，當(dāng)且僅當(dāng)矩陣PO尸的

(i,J)項(xiàng)元素(，壬/)PijPji=1。這樣，若矩陣PP的第

i行的非零元素在第打…，/洌，則結(jié)點(diǎn)匕，%，

vj2,力為強(qiáng)連通子圖的結(jié)點(diǎn)。

()6/14/20

2013-3-1347

原版教學(xué)配套課件

(p〃p…PQP：Pl2P21…PP

12(%P2I…P3lnnl

P21022…P2nP12022P〃2P21Pl2P；…02"尸"2

Pop'=0—

????????.?????????

<Pn2…PJHI><^2n??P〃n>5//〃Pn2P2”…「I

如對(duì)本節(jié)圖10?18的圖可求出的可達(dá)性矩陣P為:

’111110、q11110、111000、q11000、

111110111110111000111000

111110111110111000111000

P°P=0——

000010000010111000000000

000000000000111101000000

、000010,<000010)、000000,00000,

由此也可求出該有向圖的強(qiáng)分圖點(diǎn)集是：

V9

｛匕，2匕｝，仇｝'｛也｝'｛中O

()6/14/201

2013-3-1348

原版教學(xué)配套課件

例10?8在操作系統(tǒng)中，設(shè)在時(shí)亥！有多道程序尸「

尸2,…，尸皿運(yùn)行，系統(tǒng)的資源，J々，…，〃被運(yùn)行中的

程序所占用。若占用八的程序尸及又對(duì)資源勺提出要求時(shí)，

則從結(jié)點(diǎn)外出發(fā)引一秦有向邊寫(xiě)0相連，用〃個(gè)結(jié)點(diǎn)占，

々，…，卻分別表示〃個(gè)資源，這伴得到有〃個(gè)結(jié)點(diǎn)的有向

圖，它是某一時(shí)刻機(jī)器內(nèi)的資源分配狀態(tài)圖。

假如有資源分配狀態(tài)如圖10?20所示，對(duì)該圖討論“死鎖”

問(wèn)題。

圖10.如計(jì)算機(jī)和謳分配伏態(tài)圖

()6/14/2￡J.

2013-3-1349

原版教學(xué)配套課件

在該圖中，4占有也對(duì)6提出要求；尸2占有，2,對(duì)

心，Q提出要象；尸3占有，3，對(duì)rpQ提出要求;尸4占有

Q，對(duì)0，提出要求。這時(shí)資嬴勺，心，Q無(wú)法從被

占有的狀態(tài)中釋放出來(lái)，我們說(shuō)此刻系統(tǒng)處于“死鎖”狀

O

可以看出，當(dāng)且僅當(dāng)資源分配狀態(tài)圖G包含多于一個(gè)結(jié)

點(diǎn)的強(qiáng)分圖時(shí)，系統(tǒng)才在，時(shí)刻發(fā)生“死鎖”，故可用前述

的矩陣方法去識(shí)別是否包含多于一個(gè)結(jié)點(diǎn)的強(qiáng)分圖，從

而檢查出“死鎖”狀態(tài)。

()6/14/20LW

2013-3-1350

原版教學(xué)配套課件

10.5歐拉圖與哈密爾頓圖

/10?5.1歐拉圖

哥尼斯堡七橋問(wèn)題是歷史上著名的圖論問(wèn)題。

問(wèn)題是這樣的：在18世紀(jì)的東普魯士的個(gè)哥尼斯堡城

市，有條橫貫全城的普雷格爾河和兩個(gè)島嶼，在河的兩

岸與島嶼之間架設(shè)了7座橋，把它們連接起來(lái)（如圖

21所示）。

每逢假日，城中居民進(jìn)行環(huán)城游玩，人們對(duì)此提出了一

個(gè)“遍游”問(wèn)題：能否設(shè)計(jì)一種走法，使得從某地出發(fā)通

過(guò)且只通過(guò)每座橋一次后又回到原地呢？

可以將圖10.21中的哥尼斯堡城的4塊陸地分別標(biāo)以A,

B,C,D,將陸地設(shè)想為圖的結(jié)點(diǎn)，而把橋畫(huà)成相應(yīng)的

l連接邊，所以，圖10-21可簡(jiǎn)化為圖10.22所示。06/14/2013*^^^^

2013-3-1351

原版教學(xué)配套課件

c

于是，七橋“遍游”問(wèn)題等價(jià)于在圖io?22中，從某一結(jié)點(diǎn)

出發(fā)找到一條跡，通過(guò)它的每條邊一次且僅一次，并回

到原來(lái)的結(jié)點(diǎn)。

下面通過(guò)介紹幾個(gè)定義和定理來(lái)討論七橋問(wèn)題的求解。

()6/14/201

2013-3-1352

原版教學(xué)配套課件

定義10?27給定無(wú)孤立結(jié)點(diǎn)的圖G,若存在一條經(jīng)過(guò)G中

每邊一次且僅一次的回路，則該回路為歐拉回路。具有

歐拉回路的圖稱為歐拉圖。

例如，給出如圖10?23所示的兩個(gè)圖，根據(jù)定義10?25可以

得出，（〃）是歐拉圖，而S不是歐拉圖。

S10-23次位圖示例

()6/14/201

2013-3-1353

原版教學(xué)配套課件

定理10.8連通圖G是歐拉圖的充要條件是G的所有結(jié)點(diǎn)的

度數(shù)都是偶數(shù)（這樣的結(jié)點(diǎn)稱為偶度結(jié)點(diǎn)）。

證明

?必要性：設(shè)G是一歐拉圖，a是G中的一條歐拉回

路。當(dāng)a通過(guò)G的任一結(jié)點(diǎn)時(shí)，必通過(guò)關(guān)聯(lián)于該點(diǎn)的

兩條邊。又因?yàn)镚中的每條邊僅出現(xiàn)一次，所以a所

通過(guò)的每個(gè)結(jié)點(diǎn)必定是偶度結(jié)點(diǎn)。

?充分性：我們可以這樣來(lái)作一個(gè)封閉的跡萬(wàn)，假設(shè)它

從某結(jié)點(diǎn)Z開(kāi)始，沿著一條邊到另一結(jié)點(diǎn)，接著再?gòu)?/p>

這個(gè)結(jié)點(diǎn)，沿著沒(méi)有走過(guò)的邊前進(jìn)，如此繼續(xù)走下

去。因?yàn)榭偸茄刂惹皼](méi)有走過(guò)的新邊走，又由于圖

?邊數(shù)有限，所以