計算機應用數(shù)學基礎(chǔ) 王學軍 計算機應用數(shù)學 第10章 圖論

第10章圖論

教學課件

學習目標:

通過本章的學習，要掌握如下內(nèi)容,

活運用的程度:

基本概念

路與回路

圖的矩陣表示

有向圖和可達性矩陣

歐拉圖與哈密爾頓圖

?樹

根樹及其應用

二部圖和平面圖

\/

教笳3裳昔

2

10.1基本概念

f10.1.1圖的基本概念

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

是由一些點和一些連接兩點間的連線所組成，對于點的

位置及連線的長度無關(guān)緊要。

例如，有〃、b、C、d四個足球隊進行友誼比賽。為了描

述4個隊之間比賽的情況，可以用圖104來表示。

在圖104中4個小圓圈分別表示這

四個足球隊，稱之為結(jié)點。如果兩

隊進行過比賽，則在表示這兩隊的

結(jié)點之間用一條線連接起來，稱之

為邊。

y

教著泌

3

10.1基本概念

設A,5為任意的｛(〃，八〃￡5｝兩個集合，稱為A\

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

為有序偶集。

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

①加其中V(G)是一個非空的結(jié)點集合，￡(G)是邊的集

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

函數(shù)。

一般情況下，G=<V(G),E(G),0G>簡寫為G=vV(G),

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

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

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

線表示無向邊，用有方向的連線表示有向邊。

教著泌

4

（?例10」圖舉例。\

⑴給定無向圖G=vV（G）,E（G）,0G>,其中HG）={-b,

c,d},E（G）={e19e2,e3,e5,e6],0G（4）=（〃，

0G應）=（〃，b）,久（■）=（〃,c）,0G（。4）二（〃,砌，

0G（/）=（〃，或，0G&）=?砌。

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

b,c,d,e,f},E（D）={et,e2,e4,e5,e6,與},

。0（0]）=<4,a>9①D（Q=va,b>,a>,

<c

①D（Q）="，〃>，①口&）-，b>,①0（"）=<c，d>,

%（C7）=VC，d>,4（.）=4,f>o

k__________________________________________）

?M度I教養(yǎng)13瞭/5

f?畫出G與。的圖形。

解圖10?2中(〃)，(A)分別給出了無向圖G和有向圖。的圖

形。

圖10：無向圖育向圖舉例

y

教著13喙19

6

計算機應用數(shù)學基礎(chǔ)

定義10?2如果兩個結(jié)點之間有多條邊(對于有向圖，則有

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

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

重圖，不含平行邊和自回路的圖稱為簡單圖。

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

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

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

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

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

記作deg")。

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

=3oy

教

?TIH7

計算機應用數(shù)學基礎(chǔ)

定理104設圖G=vV(G),E(G),0G＞是具有〃個點，m條

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

工deg(匕)=2m

證明因為G中每條邊都與兩個結(jié)點關(guān)聯(lián)，每條邊均提供2

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

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

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

條邊的有向圖，其中結(jié)點集合為V={vLv2,vn},

貝(J

〃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)=A,d啥⑦=1,deg-⑺=1。

?網(wǎng)舊教

8

計算機應用數(shù)學基礎(chǔ)

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

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

奇數(shù)度數(shù)和偶數(shù)度數(shù)的結(jié)點集，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é)點稱為孤立點。

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

10.1.3幾種常見的圖

定義10?5具有〃個結(jié)點和機條邊的圖稱為(〃，帆)圖。一個

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

結(jié)點的圖，即(1,0)圖稱為平凡圖。

教Bn-ill9

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

全圖?！▊€結(jié)點的無向完全圖記為屋〃其邊的條數(shù)為〃(〃?

1)/2o

從圖10?3中的馬和(看出《有3條邊，(有6條邊。容

易證明(有n(n?l)/2條邊。

定義10?7設G=vV(G),E(G)＞是一個具有n個結(jié)點的簡單

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

到的圖稱為G的補圖(或稱為G的補)，記為。G

如圖10?4給出了一個圖G和G的補3。

△區(qū)XL

G_G

圖107笈與五宗意圖圖10-4G和G小意圖

教而患1堂

計算機應用數(shù)學基礎(chǔ)

定義10?8給每條邊賦以一個實數(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證明在任何一個有6個人的小組中，存在3個人

互相認識，或者存在3個人互相不認識(拉姆齊問題)。

分析用6個結(jié)點來代表人，并用鄰接性來表示兩人之間

認識關(guān)系。這樣一來，該例就是要證明：任意一個有6

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

個互相不鄰接的點。即，對任何一個有6個結(jié)點的圖

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

V7

教

11

證明^G=<V(G),E(G)>,\V\=6,u是G中一結(jié)點。因為

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

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

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

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

兩個在G中均不鄰接，貝Wjv2，匕就是G中一個三角形

的3個頂點。

10.1.4子圖

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

圖。

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

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

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

(3)若^=4好E,則稱G，是G的生成干圖。

?網(wǎng)舊教Bn-ill12

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

定義10-10如果圖G中的一個子圖是通過刪去圖G的結(jié)點集V的一個

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

匕。

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

定義10-11如果圖G中的一個子圖是通過刪去圖G的邊集￡的一個子

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

EjO

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

10.1.5圖的同構(gòu)

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

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

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

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

構(gòu)的。

教

14

計算機應用數(shù)學基礎(chǔ)

圖10.6圖同構(gòu)示例

I)

?Jtd教113111115

定義10.12設有圖G=v匕￡＞和圖G，=v—,琢＞。如果

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

g(y))￡￡',且,,刃與(g(〃)，g"))有相同的重數(shù)，則

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

例10-3考察圖10.7中的兩個圖G=(V,￡)和G，=(V"

很容易看出，定義g：g(vz)=v\,可以驗證g

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

圖10-7例10.3圖同梅

教Bn-ill16

10.2路與回路

/10.2.1路、回路和連通性

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

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

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

女稱作路的長度。

定義10,4設〃=為?產(chǎn)/2…。盧々是圖G中連接與到腺的路。

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

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

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

(4)長度大于2的閉的通路(即除為=咋外，其余結(jié)點均

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

<_____________________/

?匕1回教養(yǎng)13嚎/17

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

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

路V/。47V是一條回路，但不是回路；

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

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

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

如圖10-1表示的簡單圖中,

路可寫成O

教B13-11I18

下面我們利用通路的概念解決一個古老的著名問題。

例10?4（渡河問題）一個擺渡人，要把一只狼、一只羊和

一捆干草運過河去，河上有一只木船，每次除了人以

夕卜，只能帶一樣東西。并且，如果人不在旁時，狼就要

吃羊，羊就要吃干草。問這人應該怎樣才能把它們運過

河去？

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

草。

如果用尸WSH表示人和其他三樣東西在河的左岸。這

樣，在FWSFWHFSH

FSFH

磔WHSHF

WSHy

教赤3喙昔

19

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

右岸去了O

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

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

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

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

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

HFSH

WH

郎FWS

圖10.9河在你允許世去

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

則其中長度最短的路稱為從匕到匕的短程。短程的長度稱為匕到匕的距

離，用符號〃（匕，嚀）表示。

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

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

一條路，則其短程是一條長度不大于的通路。

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

匕.…女…可用反證法證明，當〃是短程時，〃一定是通路。

推論設圖G=（V,E）,\V\=n,則G中任一回路長度不大于〃。

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

這個圖是連通的，否則是不連通的。

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

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

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

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

的，W(G')=L

任何一個圖都可劃分為若干個連通分支。顯然，僅當圖

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

S10-10圖連遹分文示例

教

22

計算機應用數(shù)學基礎(chǔ)

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

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

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

路的建造或維修費用等等。

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

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

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

U

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

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

這樣，假設S為圖G中按長度遞增的次序已求出的最短路

徑的終點的集合，則下一條長度較長的最短路徑的終點〃

(如下:y

教

23

計算機應用數(shù)學基礎(chǔ)

令二對于考慮每個七es,若有這樣的邊，將從

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

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

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

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

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

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

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

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

?令D①昨）為

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

8否則y

教著泌H

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

(2)找中的點〃，使。(〃)=機加則。(〃)就是人到〃的最短路徑

長度。

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

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

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

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

因為該算法每執(zhí)行一次(以執(zhí)行算法步驟2?4一遍為一次)，選取一

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

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

y

教

25

計算機應用數(shù)學基礎(chǔ)

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

教赤3喙昔

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

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

解初始狀態(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

教

27

計算機應用數(shù)學基礎(chǔ)

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

?第1次

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

={vO,vl)；

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

?(3)修改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{°°,

2+oo}=°o

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

oy

計算機應用數(shù)學基礎(chǔ)

v.(s)

S-I**.?1I

(5)y

■BILH教113111129

v/））

-1%*?.、AC

第2次（6）

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

?(1)S中有最小D值的結(jié)點為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次的過程請讀者自己試著補出來。y

?回回教B13-11I30

10.3圖的矩陣表示

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

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

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

示圖。利用這種方法，可以把圖用矩陣存儲在計算機

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

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

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

1(V.,V;)GE

a..=<

U

0(vz.,vy)E

y

j教Bn-ill31

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

，01010、

10111

A=01001

11000

1100,

顯然，無向圖的鄰接矩陣一定是對稱的。

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

的含義，下面定理10?4進行了說明。

y

教

32

計算機應用數(shù)學基礎(chǔ)

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

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

的路的總數(shù)。

證明對1用數(shù)學歸納法。

當1=1時，A1=A,由A的定義，定理顯然成立。

若l=k時定理成立，則當l=k+l時，Ak+l=AkXA,所以

?若包=￡d)%

r=l

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

⑴如果對1=1,2,n-1,Al的(i,j)項元素(i#j)都為零,那么

vi和vj之間無任何路相連接，即vi和vj木連通。國此，vi和vj必屬

于G的不同的連通分支。

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

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

(3)A1的(i,i)項元素a(l)ii表示開始并結(jié)束于vi長度為1的回路的數(shù)

目。

教B13-11I33

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

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

解：

'01000、,010o0、g1000、"10100、

10100101001010002000

A=01000A2=01000x0100010100

00001000010000100001

W0010,W0010(0001001

92000、"20200、

2020004000

A，=02000AJ20200

0000100010

00010,<0000L

y

教B13-11I34

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

知，匕到喔長度為3的路有兩條，從圖中可看出是V產(chǎn)2y產(chǎn)2

和U產(chǎn)2y3“2。

(2)由A2的主對角線上元素可知，每個結(jié)點都有長度為2

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

有一條。

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

為3的回路。/w

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

無路，它們屬于不同的連通分支。⑸或匕，

對于其他元素讀者自己找出其意義。\'

VJ

圖10J5京錦結(jié)矩陣

教B13-11I

10.4有向圖和可達性矩陣

(10.4.1有向圖

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

比無向圖更有應用價值。因此，了解有向圖的相關(guān)概念

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

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

是以u為弧尾和以u為弧頭的弧的條數(shù)，分別記作deg+(y)

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

deg(v)o

?-------->

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

deg+(%)=2,deg(vl)=l,deg(v1)=3

欣夕仇)=Ldeg(v2)=l9degiy^l

deg+(%)=L。(匕)=1,deg(y^=2

+

deg(v4)=1,deg(v4)=29deg(y^=3

無向圖中的路、跡、通路和回路的

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

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

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

的交替序列

W=VereVeVf

0ii22---kk使得每條弧力從圖10-16有向圖示例

ql開始匕處結(jié)束。y

教

37

計算機應用數(shù)學基礎(chǔ)

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

達的。

?定義10-23設有有向圖G,

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

(2)若G中任意兩個結(jié)點之間，至少有一個結(jié)點到另一個結(jié)點是可達

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

(3)若G中任意兩個結(jié)點之間是相互可達的，則稱G是強連通的。

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

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

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

（加是強連通的，是單向連通的，（c）是弱連通的。

教著13喙19

39

計算機應用數(shù)學基礎(chǔ)

定理10?5一個有向圖G是強連通的，當且僅當G中有一個

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

?證明

(1)必要性：如果有向圖G是強連通的，則任意兩個結(jié)點

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

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

上各結(jié)點就不能相互可達，這與G是強連通矛盾。

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

結(jié)點一次，則G中任意兩個結(jié)點是相互可達的，故G是強

連通的。

例如，圖中圖(a)是強連通的，有一回路為

V,它包含圖中所有結(jié)點。

1W1y

?教養(yǎng)13喙香

40

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

G，是強連通的（單向連通的、弱連通的），G中沒有包含G，

的更大的子圖是強連通的（單向連通的、弱連通的），則稱

G，是G的強分圖（單向分圖、弱分圖）。

在圖10?18的有向圖中，因為結(jié)點訶與任何別的結(jié)點都不

相互可達，也可稱為（｛%｝,。）是一個強分圖。

可以看出該有向圖的強分圖的集是：

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

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

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

圖10-18有向圖示例

算機應用數(shù)學基礎(chǔ)

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

一強(弱)分圖中。容易證明，。是一個等價關(guān)索。這

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

合是V上的一個劃分。每一個等價類的結(jié)點以及相應的邊

導出一個強(弱)分圖。由此有下面的定理。

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

在也只在一個強(弱)分圖中。

10.4.2有向圖的可達性

下面用矩陣來研究有向圖的可達性。

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

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

“"[o(<Vj,Vj>^E)

注意，這里A不一定是對稱的。y

教

42

計算機應用數(shù)學基礎(chǔ)

定義10?25設6=（V,E）是一個有〃個結(jié)點的有向圖,

貝碗階方陣P=（pQ稱為圖G的可達性矩陣。其中

1（匕到匕可達）

IJ

Pij\o（匕到匕不可達）

IJ

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

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

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

A,分以下兩步可得到可達性矩陣。

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

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

不變，所得的矩陣P就是可達性矩陣。y

教

43

計算機應用數(shù)學基礎(chǔ)

當〃很大時，這種方法求可達性矩陣很復雜。下面再介紹

一種簡便的方法。

因為可達性矩陣是一個元素僅為I或0的矩陣（稱為布

爾矩陣），而在研究可達性問題時，對兩個結(jié)點間有路

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

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

⑴，A⑵，??.，A⑺o

說明集合｛0,1｝中的二元運算八和V定義如下：

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

1A1=11AO=OA1=OAO=O

分別稱A、V為布爾加和布爾乘積運算。

<）

教

44

定義10?26兩個布爾矩陣中，若將矩陣運算中元素的相加

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

布爾矩陣運算，相應的矩陣加法和乘法稱為矩陣的布爾

加V和布爾乘八。

?由此有

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

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

(n)

A=A(ml)AA(1)

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

I■匕1隹1教養(yǎng)13%」，45)

例10?7求出圖10?19所示圖的可達性矩陣。Vf

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

"0100"

0010

A=

1100

J110,

A⑴-A圖10-19戲可達矩陣

fo100］僅io0、（0010、<1100、fo110、

010001Oil0001101110

Aa=4（釣=

1001100-011011101110

11?u110J11110JJ11（Lu11

‘1110、

人心+人⑵+心+心:1110

1110

J110,y

教113-ill46

計算機應用數(shù)學基礎(chǔ)

定理10?7有向圖G是強連通的當且僅當其可達性矩陣P除

主對角線外，其他元素均為1。

下面介紹如何利用一個圖的可達性矩陣，求出這個圖的

強分圖。

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

陣，定義矩陣運算P尸為

由定義，如果從結(jié)點匕到,是可達的，則應有

P=1；如果從結(jié)點,到匕是可達的，則應有P.尸1o因

此，結(jié)點匕.和,是相互可達的，當且僅當矩陣PO尸的

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

i行的非零元素在第…，。列，則結(jié)點匕，叼，

%2，…,4波為強連通子圖的結(jié)束。

教

47

(p〃p…PQP：Pl2P21…PP

12(%P2I…P3lnnl

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

Pop'=0—

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

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

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

’111110、q11110、111000、q11000、

111110111110111000111000

111110111110111000111000

P°P=0——

000010000010111000000000

000000000000111101000000

、000010,<000010)、000000,00000,

由此也可求出該有向圖的強分圖點集是：

V9

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

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

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

程序所占用。若占用八的程序尸及又對資源勺提出要求時，

則從結(jié)點外出發(fā)引一秦有向邊寫0相連，用〃個結(jié)點G，

卻分別表示〃個資源，這伴得到有〃個結(jié)點的有向

???,

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

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

問題。

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

教

49

在該圖中，號占有也對七，七提出要求；尸2占有，2,對

心，Q提出要象；尸3占有，3，對.，Q提出要求;P4占有

Q，對「1，々提出要求。這時資嬴勺，小，Q無法從被

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

yQi>o

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

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

的矩陣方法去識別是否包含多于一個結(jié)點的強分圖，從

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

?--------/

10.5歐拉圖與哈密爾頓圖

/10?5.1歐拉圖

哥尼斯堡七橋問題是歷史上著名的圖論問題。

問題是這樣的：在18世紀的東普魯士的個哥尼斯堡城

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

岸與島嶼之間架設了7座橋，把它們連接起來（如圖

21所示）。

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

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

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

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

B,C,D,將陸地設想為圖的結(jié)點，而把橋畫成相應的

l連接邊，所以，圖10-21可簡化為圖10.22所示。y

■M1LH教Bn-ill51

c

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

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

到原來的結(jié)點。

下面通過介紹幾個定義和定理來討論七橋問題的求解。

定義10.27給定無孤立結(jié)點的圖G,若存在一條經(jīng)過G中

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

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

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

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

S10-23次位圖示例y

教Bn-ill53

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

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

證明

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

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

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

通過的每個結(jié)點必定是偶度結(jié)點。

?充分性：我們可以這樣來作一個封閉的跡萬，假設它

從某結(jié)點Z開始，沿著一條邊到另一結(jié)點，接著再從

這個結(jié)點，沿著沒有走過的邊前進，如此繼續(xù)走下

去。因為總是沿著先前沒有走過的新邊走，又由于圖

?邊數(shù)有限，所以這個過程一定會停止。但是，因

為每一個結(jié)點都與偶數(shù)條邊關(guān)聯(lián)，而當沿f前進到達

結(jié)點時，若沒4￡走過了與戌聯(lián)的奇數(shù)條邊，這

樣在讓總還有一條沒有走過的邊。因此，￡必定返

口回停止在2（見圖10工4；|田

54

10-24吠位圖江明示意

如果￡走遍了G的所有邊，那么就得到了一條歐拉回

路。如果不是這樣，那么在￡上將有某一結(jié)點5,與它關(guān)

聯(lián)的一些邊尚未被￡走過（因G連通）。但是，實際

上，因為￡走過了與5關(guān)聯(lián)的偶數(shù)條邊，因此不屬于￡的

與5關(guān)聯(lián)的邊也是偶數(shù)條。對于其他有未走過邊所關(guān)聯(lián)的

所有結(jié)點來說，上面的討論同樣正確。于是若設Gi是G?

￡的包含點5的一個連通分支，則區(qū)的結(jié)點都是偶度結(jié)

點。

教

計算機應用數(shù)學基礎(chǔ)

根據(jù)上面的討論，在Gi中得到一個從5點出發(fā)的一條閉

跡￡1。這樣就得到了一條更大的閉跡，它是從A點出發(fā)

沿￡前進到達員然后沿閉跡￡1回到5,最后再沿￡由6

走到4。如果我們?nèi)匀粵]有走遍整個圖，那么再次把閉跡

擴大，以此類推，直到最后得到一個歐拉回路。

由于在七橋問題的圖10?22中，有4個點是奇度結(jié)點，故

不存在歐拉回路，七橋問題無解。

在圖10?23中，（°）圖的每個結(jié)點的度數(shù)都為4,所以

它是歐拉圖；"）圖不是歐拉圖。但我們繼續(xù)考察

（b）圖可以發(fā)現(xiàn)，該圖中有一條路乙匕乙％乙匕匕，它經(jīng)

過（。）圖中的每條邊一次且僅一次，我們把這樣的路稱

為歐拉路。

V7

?HJ回教養(yǎng)泌甘56

計算機應用數(shù)學基礎(chǔ)

定義10?28通過圖G的每條邊一次且僅一次的路稱為圖G

的歐拉路。

一個圖中是否存在歐拉路，可以采用如下定理判定。

定理10?9連通圖G具有一條連接結(jié)點匕?和力的歐拉路，當

且僅當匕和,是G中僅有的奇度結(jié)點。

證明將邊（匕，vz.）加于圖G上，令其所得的圖為G，（可

能是多重圖）。

由定理10?8知:

G有連接結(jié)點匕和耳的歐拉路，

1J

(1)G，有一條歐拉回路；

(2)G，的所有結(jié)點均為偶度結(jié)點;

（3）G的所有結(jié)點除匕和，外均為偶度結(jié)點;

（4）匕.和,是G中僅有的奇度結(jié)點。y

?網(wǎng)舊教

57

計算機應用數(shù)學基礎(chǔ)

我國民間很早就流傳一種與七橋問題類似“一筆畫”游

戲，要判定一個圖G是否一筆畫出，由定理10.8和定理

10?9可知，有兩種情況可以一筆畫。

(1)如果圖中所有結(jié)點是偶度結(jié)點，則可以任選一點

作為始點一筆畫完；

(2)如果圖中只有兩個奇度結(jié)點，則可以選擇其中一

個奇度結(jié)點作為始點也可一筆畫完。

例10?9圖10?25(〃)是一幢房子的平面圖形，前門進入

一個客廳，由客廳通向4個房間。如果要求每扇門只能進

出一次，現(xiàn)在你由前門進去，能否通過所有的門走遍所

有的房間和客廳，然后從后門走出。

V/

?HJ回教養(yǎng)泌甘58

圖10-25床位路舉例

解將4個房間和一個客廳及前門外和后門外都作為結(jié)

點，若兩結(jié)點有邊相連就表示該兩結(jié)點所表示的位置有

一扇門相通。由此得圖10?25(Z>)o由于圖中有4個結(jié)點

是奇度結(jié)點，故由定理10?9知本題無解。

類似于無向圖的結(jié)論，對有向圖有以下結(jié)果。y

教

59

計算機應用數(shù)學基礎(chǔ)

定理10,0一個連通有向圖，具有（有向）歐拉回路的充

要條件是，圖中每個結(jié)點的入度等于出度。

定理一個連通有向圖，具有有向歐拉路的充要條件

是，最多除兩個結(jié)點外的每個結(jié)點的入度等于出度，但

在這兩個結(jié)點中，一個結(jié)點的入度比出度大1,另一個結(jié)

點的入度比出度少1。

例判斷在圖10.26中所示的各圖中，哪些有歐拉通

路？哪些是歐拉圖？

解在圖10?26中，（a）、（d）、（/）中均存在歐拉通

路，其中（a）中的歐拉通路還是歐拉回路，所以（a）

為歐拉圖。（e）為非連通圖，因而不可能有歐拉通路，

更無歐拉回路。（b）、（c）中，均存在入度比出度大

2,和出度比入度2的結(jié)點，因而它們不可能存在歐拉通

路，當然也無歐拉回路。y

?網(wǎng)舊教B13-11I60

計算機應用數(shù)學基礎(chǔ)

(1052哈密爾頓圖

與歐拉回路類似的有哈密爾頓回路問題。它是1859年哈

密爾頓首先提出的一個關(guān)于12面體的數(shù)學游戲：能否在

圖10?29中找到一個回路，使它含有圖中所有結(jié)點且僅一

次？

若把每個結(jié)點看成一座城市，連接兩個結(jié)點的邊看成是

交通線，那么這個問題就變成能否找到一條旅游路線，

使得沿著該路線經(jīng)過每座城市恰好一次，/J"、

再回到原來的出發(fā)地呢？因此，這個問乙