《離散數(shù)學(xué)教程》第9章 圖與樹(shù)

離散數(shù)學(xué)第9章圖與樹(shù)引例哥尼斯堡七橋問(wèn)題Cb1b2

b6Ab5Bb3b4b7Db1b2b6

Bb4b7DAb5Cb3第9章圖與樹(shù)9.1圖9.2路徑、回路及連通圖

9.3圖的矩陣表示9.4樹(shù)9.1圖9.1.1圖的基本概念定義9.1

由以下兩個(gè)部分所組成的離散結(jié)構(gòu)G，稱為圖：（1）非空集合V(G)，稱為圖G的結(jié)點(diǎn)集，其成員稱為結(jié)點(diǎn)或頂點(diǎn)。結(jié)點(diǎn)用拉丁字母或希臘字母來(lái)表示。（2）多重集合E(G)，稱為圖G的邊集，其成員稱為邊。邊用結(jié)點(diǎn)的序偶或結(jié)點(diǎn)的兩元素多重集表示。結(jié)點(diǎn)序偶表示的邊稱為有向邊，兩元素多重集表示的邊稱為無(wú)向邊。當(dāng)圖的邊均為有向邊時(shí)，稱該圖為有向圖；當(dāng)圖的邊均為無(wú)向邊時(shí)，稱該圖為無(wú)向圖。

圖G的表示——二元組<V(G)，E(G)>,或<V，E>。9.1圖9.1.1圖的基本概念定義9.2：（1）邊e=<u,v>時(shí)：稱邊e關(guān)聯(lián)結(jié)點(diǎn)u、v，或u，v為e

的端點(diǎn)，并稱u為e

的起點(diǎn)，v為e

的終點(diǎn)。（2）邊e={u,v}時(shí)：稱邊e關(guān)聯(lián)結(jié)點(diǎn)u、v，并稱u、v為e的端點(diǎn)，這時(shí)u、v為相鄰(接)的結(jié)點(diǎn)。（3）當(dāng)e=<u,v>或{u,v}，u=v時(shí)，<u,v>和{u,v}均稱為環(huán)。例9.1：(1)哥尼斯堡七橋圖，可表示為：<{A,B,C,D},{{A,C},{A,C},{A,D},{A,D},{A,B},{C,B},{D,B}}>(2)左圖為一有向圖，可表示為：<{v1,v2,v3,v4,v5,v6},{<v1,v1>，<v2,v3>，<v3,v2>，<v3,v4>，<v5,v4>，<v5,v5>}>b1b2b6

Bb4b7DAb5Cb39.1圖9.1.1圖的基本概念e1v1v2e3e2v3v6e4e5e6v4v59.1圖9.1.1圖的基本概念定義9.3

設(shè)圖G為<V，E>。

（1）當(dāng)V和E為有限集時(shí)，稱G為有限圖，否則稱G為無(wú)限圖。（2）當(dāng)邊集合中至少有一個(gè)元素的重?cái)?shù)不小于2時(shí)，稱G為重圖，否則稱G為單圖；重?cái)?shù)不小于2的邊稱為重邊，或平行邊。（3）無(wú)環(huán)和重邊的圖稱為簡(jiǎn)單圖。當(dāng)G為簡(jiǎn)單無(wú)向圖時(shí)，也常用

(n,m)表示圖G，其中n=V

，m=E

。9.1圖9.1.1圖的基本概念（4）任何兩個(gè)不同結(jié)點(diǎn)間都有邊關(guān)聯(lián)的簡(jiǎn)單無(wú)向圖，稱為完全圖。

n個(gè)頂點(diǎn)的完全圖常記作Kn。不是任何邊的端點(diǎn)的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)，僅由孤立結(jié)點(diǎn)構(gòu)成的圖K1（E=）稱為零圖。（5）當(dāng)給G賦予映射f：V→W，或g：E→W，W為任意集合，常為實(shí)數(shù)集的子集，此時(shí)稱G為賦權(quán)圖，用<V,E,f>或<V,E,g>或<V,E,f,g>表示之。f(v)稱為結(jié)點(diǎn)v的權(quán)，g(e)稱為邊e的權(quán)。

f(G)稱為圖G的結(jié)點(diǎn)權(quán)和，g(G)稱為圖G的邊權(quán)和。9.1.1圖的基本概念b1b2b6

Bb4b7DAb5Cb3重圖（b1、b2為重邊）有向圖e1為環(huán)，v6為孤立結(jié)點(diǎn)例9.2：9.1圖e1v1v2e3e2v3v6e4e5e6v4v59.1圖9.1.1圖的基本概念

例9.2：(a)簡(jiǎn)單圖(b)完全圖K5(c)賦權(quán)圖f(v1)=9.3，g(e1)=800

f(G)=37.8，g(G)=4580

7209.380010009.986075.6v1e112006.09.1.2結(jié)點(diǎn)的度9.1圖定義9.4

在無(wú)向圖中，結(jié)點(diǎn)v的度d(v)是結(jié)點(diǎn)v作為邊的端點(diǎn)的次數(shù)。在有向圖中，結(jié)點(diǎn)v的出度是v作為有向邊起點(diǎn)的次數(shù)，v的入度是v作為有向邊終點(diǎn)的次數(shù)。結(jié)點(diǎn)v的度d(v)是v的出度d+(v)

與入

度d-(v)

的和。(a)d(v1)=5，環(huán)e兩次以結(jié)點(diǎn)v1為端點(diǎn)例9.3:

v3

v1

e

v2

v3

v1

e

v2(b)d+(v1)=2，d-(v1)=3，d(v1)=d+(v1)+d-(v1)=59.1.2結(jié)點(diǎn)的度9.1圖定理9.1：對(duì)任意圖G，設(shè)其邊數(shù)為m,頂點(diǎn)集為{v1,v2,…，vn}，那么證：當(dāng)一邊關(guān)聯(lián)于兩個(gè)不同結(jié)點(diǎn)時(shí)，它分別使兩結(jié)點(diǎn)各增加一度;當(dāng)一邊為一環(huán)時(shí),它給該結(jié)點(diǎn)增加兩度,因此各結(jié)點(diǎn)的度的總和是邊的數(shù)目的兩倍。當(dāng)G為有向圖時(shí)，可改寫為:9.1.2結(jié)點(diǎn)的度9.1圖定理9.2：圖的奇數(shù)度頂點(diǎn)必為偶數(shù)個(gè)。證：反設(shè)某圖有奇數(shù)個(gè)奇數(shù)度頂點(diǎn)，則它們的度的總和是奇數(shù)。由于其余頂點(diǎn)是偶數(shù)度的，故這些頂點(diǎn)的度的總和是偶數(shù)。于是，圖的所有頂點(diǎn)的度數(shù)總和為奇數(shù)（奇數(shù)＋偶數(shù)），與定理8.1矛盾。命題得證。定理9.3：自然數(shù)序列(a1,a2,…,an)稱為一個(gè)度序列，如果它是一個(gè)圖的頂點(diǎn)的度的序列。(a1,a2,…,an)為一個(gè)度序列，當(dāng)且僅當(dāng)為一偶數(shù)。證必要性由定理9.l立得。證充分性：設(shè)為偶數(shù)，那么（a1,a2,…,an）中的奇數(shù)必定是偶數(shù)個(gè)。建立n個(gè)頂點(diǎn)的圖G，使得（1）當(dāng)ai為偶數(shù)2k時(shí),vi上恰有k個(gè)環(huán)。（2）當(dāng)ai為奇數(shù)2k+1，必有aj為奇數(shù)?？墒箆i上恰有k個(gè)環(huán)及一條非環(huán)的邊，此邊以頂點(diǎn)vj為另一個(gè)端點(diǎn)。由于為奇數(shù)的ai是偶數(shù)個(gè)，上述構(gòu)造過(guò)程是可行的，構(gòu)造得到的圖G滿足d(vi)＝ai。定理得證。9.1.2結(jié)點(diǎn)的度9.1圖9.1.2結(jié)點(diǎn)的度9.1圖定義9.5（1）一度的頂點(diǎn)稱為懸掛點(diǎn)。（2）各頂點(diǎn)的度均相同的圖稱為正則圖。各頂點(diǎn)度均為k的正則圖稱為k-正則圖。完全圖都是正則圖。定義9.6

設(shè)圖G1＝<V1，E1>，G2＝<V2，E2>，如果V1V2，E1E2

且E1≤E2，則稱G1為G2的子圖。如果G1是G2的子圖，且G1不同于G2，則稱G1為G2的真子圖。如果G1是G2的子圖，且V1=V2，則稱G1為G2的生成子圖。定義9.7

設(shè)簡(jiǎn)單無(wú)向圖G1＝<V1，E1>，G2＝<V2，E2>，稱G1與G2

互為補(bǔ)圖，如果V1=V2，E1E2=，且<V1(或V2),E1∪E2>是簡(jiǎn)單完全圖。9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖(a)和(b)關(guān)于(c)互為補(bǔ)圖。(a)(c)的真子圖(b)(c)的真子圖(c)完全圖K5例9.4：定義9.8

設(shè)G1＝<V1，E1>，G2＝<V2，E2>為兩個(gè)簡(jiǎn)單圖，稱G1與G2

同構(gòu)，如果存在一個(gè)雙射h：V1V2，使得對(duì)任意vi，vj

V1<vi,vj>

E1<h(vi),h(vj)>E2或{vi,vj}E1{h(vi),h(vj)}E2

9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖v1abcdefh(v)δγ例9.5(1)：abcdefγδ(a)G1(c)

G2雙射h：9.1.3子圖、補(bǔ)圖及圖同構(gòu)9.1圖

G1，G2不是同構(gòu)的。(a)G1(b)

G2例9.5(2)：dabcδγ例9.6

某人m帶一條狗d，一只貓c和一只兔子r過(guò)河。m每次游過(guò)河時(shí)只能帶一只動(dòng)物，而沒(méi)人管理時(shí)，狗與兔子不能共處，貓和兔子也不能共處。問(wèn)m怎樣才能把三個(gè)動(dòng)物帶過(guò)河去？9.1.4圖的應(yīng)用9.1圖<{d,r},{m,c}><{c},{m,d,r}><{m,c,r},jvd1tr3><{r},{m,c,d}><{c,r},{m,d}><{r},{m,c,d}><{m,d,r},{c}><ndzvxtr,{m,c,r}><{m,d,c,r},><{d,c},{m,r}><{m,d,c},{r}><{m,r},{c,d}><,{m,d,c,r}>例9.7

用有向圖描述識(shí)別符號(hào)串01010的狀態(tài)轉(zhuǎn)換系統(tǒng)。9.1.4圖的應(yīng)用9.1圖0SS1S2S3S4S51010101例9.8

甲乙兩人進(jìn)行乒乓球賽，規(guī)定一方連勝兩局或勝局首先達(dá)到3局者為勝方。問(wèn)甲乙至少、至多要進(jìn)行多少局比賽。9.1.4圖的應(yīng)用9.1圖

1

甲乙

2233

乙甲乙甲終止44終止甲乙甲乙終止55終止甲乙甲乙終止終止終止終止乙甲乙甲比賽至少要進(jìn)行2局，至多要進(jìn)行5局。9.2.1路徑、通路與回路9.2路徑、回路及連通圖定義9.9：圖G的頂點(diǎn)v1到頂點(diǎn)vl的擬路徑是指如下頂點(diǎn)與邊的序列：

v1,e1,v2,e2,v3,…,vl-1,el-1,vl

其中v1,v2,v3,…,vl-1,vl

為G的頂點(diǎn)，e1,e2,…,el-1

為G的邊，且ei

(i=1,2,…,l-1)以vi及vi+1為端點(diǎn)，(對(duì)有向圖G，ei以vi為起點(diǎn)，以vi+1為終點(diǎn))。擬路徑的邊數(shù)l-1稱為該擬路徑的長(zhǎng)度。當(dāng)ei

(i=1,2,…,l-1)各不相同時(shí)，該擬路徑稱為路徑，又當(dāng)vi

(i=1,2,…,l)各不相同時(shí)(除v1與vl)，則稱此路徑為通路。

v1=vl

的路徑稱為閉路徑；v1=vl的通路稱為回路。表示：簡(jiǎn)單圖或無(wú)平行邊的有向圖，擬路徑、路徑、通路等可用頂點(diǎn)序列表示，如（v1,v2,v3,…,vl-1,vl）9.2.1路徑、通路與回路9.2路徑、回路及連通圖

(v2,v3,v1,v2)回路，長(zhǎng)度3例9.9（1）(v1,v2,v3,v1,v2,v5)有重復(fù)邊點(diǎn)，擬路徑，長(zhǎng)度5(v2,v3,v1,v2,v5,v4)無(wú)重復(fù)邊，路徑，長(zhǎng)度5(v2,v3,v4)通路，長(zhǎng)度2(v2,v3,v1,v2,v5,v4,v2)閉路徑，長(zhǎng)度6

v5v2v1v3v4

v5v2v1v3v4

v5v2v1v3v4

v5v2v1v3v4

v5v2v1v3v49.2.1路徑、通路與回路9.2路徑、回路及連通圖例9.9（2）(v1,v2,v5,v4,v3,v1)回路，長(zhǎng)度5

(v2,v3,v4,v5)路徑，長(zhǎng)度3

v5v2v1v3v4

v5v2v1v3v4定理9.4

在有n個(gè)頂點(diǎn)的圖G中，如果有從頂點(diǎn)u到v(u

v)的擬路徑，那么從u到v必有路徑，并且必有長(zhǎng)度不大于n–1的通路。證不失一般性，設(shè)G為一簡(jiǎn)單圖。若G有從u到v的擬路徑(u=v1,v2,v3,…,vl-1,vl

=v)，且沒(méi)有vi＝vj

(i,j=l，2，…,l)，那么它便是一條通路，且l≤n–1；若G的這一擬路徑中有，vi＝vj

,則它可表示為

(u=v1,v2,…,vi,…,vi,…,vl-1,vl

=v)那么從中刪去從vi+1到第二個(gè)vi之間的所有邊及頂點(diǎn)，便得到一條從u到v的更短的擬路徑

(u=v1,v2,…,vi,…,vl-1,vl

=v)然后重復(fù)上述討論，直至沒(méi)有邊重復(fù)出現(xiàn)、沒(méi)有頂點(diǎn)重復(fù)出現(xiàn)，從而得到從u到v的路徑和長(zhǎng)度不超過(guò)n–1的通路。9.2.1路徑、通路與回路9.2路徑、回路及連通圖定理9.5

在具有n個(gè)頂點(diǎn)的圖G中，如果有從v到v的閉路徑，那么必定有一條從v到v的長(zhǎng)度不大于n的回路。9.2.1路徑、通路與回路9.2路徑、回路及連通圖例9.10閉路徑(v2,v3,v1,v2,v5,v4,v2)長(zhǎng)度3的回路(v2,v5,v4,v2)擬路徑(v2,v3,v1,v2,v5,v4)長(zhǎng)度2的通路(v2,v5,v4)

v5v2v1v3v4

v5v2v1v3v4定義9.10

稱圖中頂點(diǎn)u到v是達(dá)可的，如果u=v，或者有u到v的路徑。定義9.11

稱無(wú)向圖G是連通的，如果對(duì)G的任何兩個(gè)頂點(diǎn)u，v，u到

v都是可達(dá)的。稱有向圖G是強(qiáng)連通的，如果G的任何兩個(gè)頂點(diǎn)都是相互可達(dá)的；稱有向圖G是單向連通的，如果G的任何兩個(gè)頂點(diǎn)中，至少?gòu)囊粋€(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)是可達(dá)的；稱有向圖G是弱連通的，如果G的有向邊被看作無(wú)向邊時(shí)是連通的。定義9.12

圖G’稱為無(wú)向圖G的連通分支，如果G’是G的子圖，G’是連通的，并且不存在G的真子圖G’’，使G’’是連通的，且G’’以

G’為其真子圖。9.2.2連通性9.2路徑、回路及連通圖9.2路徑、回路及連通圖(a)連通圖(b)非連通圖(兩連通分支)(c)弱連通圖(d)單向連通圖(e)強(qiáng)連通圖例9.119.2.2連通性9.2路徑、回路及連通圖9.2.2連通性

定義9.13

設(shè)G’為有向圖G的子圖，若G’是強(qiáng)連通的（單向連通的、弱連通的），且G沒(méi)有強(qiáng)連通（單向連通、弱連通）的真子圖

G’’，使G’為其真子圖，那么稱G’為G的一個(gè)強(qiáng)分圖（單向分圖、弱分圖）。9.2路徑、回路及連通圖9.2.2連通性強(qiáng)分圖：

<{1,2,3},{e0,e2,e3}>，<{4},>，<{5},>，<{6},>，<{7,8},{e7,e8}>，<{9},>單向分圖：<{1,2,3,4,5},{e0,e1,e2,e3,e4,e5}>，<{5,6},{e6}>，

<{7,8},{e7,e8}>，<{9},>弱分圖:<{1,2,3,4,5,6},{e0,e1,e2,e3,e4,e5,e6}>，<{7,8},{e7,e8}>，<{9},>例9.12

2e4

4e0e2e1e5e691e335867e7e89.2路徑、回路及連通圖9.2.2連通性定理9.6

一個(gè)圖G是不連通的，當(dāng)且僅當(dāng)G的頂點(diǎn)集V可以分成兩個(gè)不交的非空子集V1和V2，使得任何邊都不以V1的一個(gè)頂點(diǎn)和V2

一個(gè)頂點(diǎn)為其兩端點(diǎn)。證充分性：顯然。必要性：設(shè)G不連通，那么有v1及v2，v2到v1是不可達(dá)的。構(gòu)造V1={v

v到v1是可達(dá)的}

V2=VV1

顯然V1，

V2，因?yàn)関1V1，v2V2。若有邊的兩端點(diǎn)分別在V1和V2中，那么該邊在V2中的端點(diǎn)到v1是可達(dá)的了，這與V2

的定義沖突。9.2路徑、回路及連通圖9.2.2連通性定理9.7

如果圖G恰有兩個(gè)不同的奇數(shù)度的頂點(diǎn)u，v，那么u到v必定是可達(dá)的。證如果u到v不可達(dá)，那么G不是連通的，u與v必分屬于兩個(gè)不連通的子圖G1，G2。從而G1，G2都是圖，且都恰有一個(gè)奇數(shù)度頂點(diǎn)。這是不可能的（定理9.2）。因而u到v是可達(dá)的。9.2路徑、回路及連通圖9.2.2連通性定理9.8：若圖G為具有n個(gè)頂點(diǎn)、k個(gè)連通分支的簡(jiǎn)單圖，那么G

至多有條邊。證明：

設(shè)G的k個(gè)連通分支的頂點(diǎn)數(shù)分別是n1，n2，…，nk，從而，n=n1+n2+…+nk，諸ni≥1。

各連通分支的邊數(shù)不超過(guò)，因此G的邊數(shù)m滿足：現(xiàn)證9.2路徑、回路及連通圖9.2.2連通性證由于，因此從而于是定理得證。

v1v5

v2v4v7

v3v69.2.3連通度9.2路徑、回路及連通圖定義9.14

設(shè)S為連通圖G的頂點(diǎn)集V的子集，稱S為G的點(diǎn)割集,如果從G中刪除S中的所有頂點(diǎn)（注：刪除結(jié)點(diǎn)v時(shí)，同時(shí)要?jiǎng)h掉關(guān)聯(lián)v的所有邊）后得到的圖不連通，但S的任何真子集均無(wú)這一特性。當(dāng)點(diǎn)割集為單元素集合｛v｝時(shí)，v稱為割點(diǎn)。割集{v1，v3}，{v5，v6}，v4是割點(diǎn)，{v1，v3，v4}不是點(diǎn)割集。例9.139.2.3連通度9.2路徑、回路及連通圖定義9.15

χ(G)稱為G的點(diǎn)連通度，定義如下：點(diǎn)連通度1-9.2.3連通度9.2路徑、回路及連通圖定義9.16

設(shè)S為連通圖G邊集E的子集，稱S為G的邊割集，或割集，如果從G中刪除S的所有邊后所得的圖是不連通的，但S的任何真子集均無(wú)這一特性。當(dāng)割集為單元素集｛e｝時(shí)，稱e為割邊。割集{{v1,v2},{v2,v3}}，{{v1,v4},{v3,v4}}等，它沒(méi)有割邊。{{v1,v4},{v3,v4},{v5,v4}}不是割集，其中{v5,v4}是多余的。9.2.3連通度9.2路徑、回路及連通圖定義9.17

λ(G)稱為圖G的邊連通度，定義如下：邊連通度為2

定理9.9

對(duì)任何簡(jiǎn)單無(wú)向圖G，χ(G)≤λ(G)≤δ(G)證若G為不連通圖或單一孤立結(jié)點(diǎn)的圖，那么據(jù)定義知:

χ(G)=λ(G)=0≤δ(G)或χ(G)=λ(G)=δ(G)=0。若G為完全圖Kn，那么χ(G)=λ(G)=δ(G)=n–1。對(duì)其它情況，先證λ(G)≤δ(G)。由于度數(shù)最小的那個(gè)結(jié)點(diǎn)上關(guān)聯(lián)的所有邊被刪除后，

G顯然不再連通，因而λ(G)至多是δ(G)，即λ(G)≤δ(G)。9.2.3連通度9.2路徑、回路及連通圖uvG1G29.2.3連通度9.2路徑、回路及連通圖定理9.9

對(duì)任何簡(jiǎn)單無(wú)向圖G，χ(G)≤λ(G)≤δ(G)再證χ(G)≤λ(G)。當(dāng)在G中刪去構(gòu)成割集的λ(G)條邊，則G不連通，設(shè)產(chǎn)生連通分支G1(n1,m1)，G2(n2,m2)。可證G1，G2中分別有結(jié)點(diǎn)u,v，{u,v}不是割集中的邊。（否則割集中的邊有λ(G)=n1n2n–1δ(G)，從而λ(G)=n–1=δ(G)，G為完全圖）。于是，刪除G1中除u以外的割集中邊的s1個(gè)端點(diǎn)，再刪除G2中與u相鄰的s2個(gè)結(jié)點(diǎn)，即刪除s1+s2≤λ(G)個(gè)結(jié)點(diǎn)，就可使G不連通（結(jié)點(diǎn)u,v不可達(dá)，如圖）。因此G的點(diǎn)連通度χ(G)不超過(guò)λ(G)，即χ(G)≤λ(G)。uvG1G2證因?yàn)?m是圖G各頂點(diǎn)的度數(shù)總和，因此n個(gè)頂點(diǎn)中至少有一個(gè)頂點(diǎn)的度不超過(guò),故G的邊連通度λ(G)不超過(guò)。定理9.10

設(shè)G為n個(gè)頂點(diǎn)、m條邊的簡(jiǎn)單連通圖，那么

λ(G)≤9.2.3連通度9.2路徑、回路及連通圖例9.14

（1）零圖的鄰接矩陣為零矩陣。（2）一圖的每個(gè)頂點(diǎn)以且僅以環(huán)為關(guān)聯(lián)的邊,那么該圖的鄰接矩陣為幺矩陣。

（3）無(wú)向圖的鄰接矩陣是對(duì)稱矩陣。

（4）

定義9.18

設(shè)G=<V,E>為一無(wú)重邊的有向圖。其中V={v1,v2,…,vn}，那么nn矩陣A=[aij]，稱為圖G的鄰接矩陣，記為A[G]:9.3.1鄰接矩陣9.3圖的矩陣表示>,<0>,<1=EvvEvvajijiij當(dāng)當(dāng)

v1v2

v4

v3鄰接矩陣9.3.1鄰接矩陣設(shè)A為圖G的鄰接矩陣，A=[aij]，Aι為A的轉(zhuǎn)置矩陣，

?為通常的矩陣乘運(yùn)算符。我們知道，若A?B=C，A=[aij]，B=[bij]，C=[cij]，那么

用Al表示l個(gè)矩陣A的乘積。9.3圖的矩陣表示,v3到v1長(zhǎng)度為3的擬路徑:（v3,v1

,v1

,v1），（v3,v4,v1

,v1）（v3,v2,v4,v1），（v3,v2,v3,v1）事實(shí)(1)

令A(yù)l=[]，那么的意義是：G中從頂點(diǎn)vi到vj的長(zhǎng)度為l的擬路徑恰為條。9.3.1鄰接矩陣9.3圖的矩陣表示

v1v2

v4

v3驗(yàn)證：9.3.1鄰接矩陣對(duì)l歸納證明事實(shí)(1)

l=1時(shí)，Al

=A=[]=[]，命題顯然真。設(shè)Al

=[]中對(duì)任意i,j均表示vi到vj的長(zhǎng)度為l的擬路徑條數(shù)?？紤]Al+1=[]。由矩陣乘積定義知9.3圖的矩陣表示其中表示從vi到vk有條長(zhǎng)度為l的擬路徑。而表示從vi經(jīng)由vk到vj的長(zhǎng)度為l+1的擬路徑數(shù)目，因而和式(9-5)表明是從vi到vj的長(zhǎng)度為l+1的擬路徑的總條數(shù)。歸納完成，(1)得證。(9-5)9.3.1鄰接矩陣9.3圖的矩陣表示事實(shí)(2)

令A(yù)?Aι=[bij]，那么的意義是：有個(gè)頂點(diǎn)v，使得vi到v，

vj到v都有邊（兩邊交于v）。因而表示頂點(diǎn)vi的出度。驗(yàn)證:

v1v2

v4

v3b31=2，正有兩個(gè)頂點(diǎn)v1，v2，使得v3與v1到它們都有邊；b33=3，頂點(diǎn)v3的出度恰為3。9.3.1鄰接矩陣9.3圖的矩陣表示證明事實(shí)(2)根據(jù)矩陣乘積的定義:等價(jià)于有bij個(gè)k的值使aikajk=1,

有bij個(gè)k的值使aik=1且ajk=1,有bij個(gè)頂點(diǎn)vk使vi到vk有邊且vj到vk也有邊。這正是事實(shí)(2)所表明的。9.3.1鄰接矩陣9.3圖的矩陣表示事實(shí)(3)

令A(yù)ι

?A=[bij]，那么bij的意義是：有個(gè)頂點(diǎn)v，使得v到vi,v到vj都有邊；因而表示頂點(diǎn)vi的入度。驗(yàn)證:

v1v2

v4

v3b31＝0，確無(wú)到v3，v1均有邊的頂點(diǎn)；b44=2，v4的入度正是2。矩陣運(yùn)算：設(shè)n個(gè)頂點(diǎn)的圖G的鄰接矩陣為A，若A=[aij]，C=[cij]，

A∨C=[dij]dij=aij∨cij

A·C=[eij]9.3.2路徑矩陣與可達(dá)性矩陣9.3圖的矩陣表示A(m)表示A·A·…·A(m個(gè)A的·乘積)矩陣B＝A∨A(2)∨…∨A(n)

bij=1當(dāng)且僅當(dāng)圖G中有vi到vj的路徑。定義9.19

設(shè)A是圖G的鄰接矩陣，那幺矩陣

B＝A∨A(2)∨…∨A(n)稱為圖G的路徑矩陣，矩陣P＝I∨B，其中I為nn么矩陣，稱為圖G的可達(dá)性矩陣。9.3.2路徑矩陣與可達(dá)性矩陣?yán)?.15

計(jì)算下圖的路徑矩陣B與可達(dá)性矩陣P。9.3圖的矩陣表示

v1v2

v3v5

v4B=A∨A(2)∨A(3)∨A(4)∨A(5)

P=I∨B定義9.20

連通無(wú)回路的無(wú)向圖稱為樹(shù)。樹(shù)中的懸掛點(diǎn)又稱為樹(shù)葉，其它結(jié)點(diǎn)稱為分支點(diǎn)。單一孤立結(jié)點(diǎn)稱為空樹(shù)。諸連通分支均為樹(shù)的圖稱為森林，樹(shù)也是森林。例9.16

9.4.1樹(shù)的基本概念9.4樹(shù)樹(shù)樹(shù)森林定理9.11

設(shè)圖T為一樹(shù)，其頂點(diǎn)數(shù)、邊數(shù)分別是n,m,那么

n–m=1或m=n–1證對(duì)T的頂點(diǎn)數(shù)n歸納。

n=1時(shí)m=0，故n–m=1成立?，F(xiàn)設(shè)n=k時(shí)命題真。令T有k+1個(gè)頂點(diǎn)。在T中刪一懸掛點(diǎn)，產(chǎn)生圖T1(k,m–1)，它必定是樹(shù)，且其頂點(diǎn)數(shù)為k=n–1。根據(jù)歸納假設(shè)，

k–(m–1)=n–1–(m–1)=1成立，即n–m=1真。歸納完成，定理得證。9.4.1樹(shù)的基本概念9.4樹(shù)定理9.12

任何不少于兩個(gè)頂點(diǎn)的樹(shù)都至少有兩片葉。證設(shè)T為任一樹(shù)，其頂點(diǎn)數(shù)、邊數(shù)分別為n,m。又設(shè)T中至多只有一個(gè)頂點(diǎn)是葉，那么

2m=(vi)≥2(n–1)+1=2n–1

m≥n

–>n–1這與定理9.11矛盾。因此T至少有兩片葉。9.4.1樹(shù)的基本概念9.4樹(shù)9.4.1樹(shù)的基本概念9.4樹(shù)定理9.13：“(n，m)圖T為樹(shù)”與下列5命題中的每一命題等價(jià)：(1)

T無(wú)回路且m=n–1。(2)

T連通且m=n–1。(3)

T無(wú)回路，但任意添加邊時(shí)，T中產(chǎn)生唯一的一條回路。(4)

T連通，但刪去任一邊時(shí)便不再連通(T的每一邊均為割邊)。(5)

任意兩個(gè)不同頂點(diǎn)之間有且僅有一條通路。證：記“T為樹(shù)”即“T連通無(wú)回路”為命題(0)。證明過(guò)程：(0)(1)(2)(3)(4)(5)(0)9.4.1樹(shù)的基本概念9.4樹(shù)(0)(1)

這由定理9.14立得。(1)(2)

設(shè)T無(wú)回路，m=n–1，欲證T連通。反設(shè)T有k個(gè)連通分支（k≥2），T1，T2,…

，Tk，它們的頂點(diǎn)數(shù)分別是n1,n2,…,nk，邊數(shù)分別是m1,m2,…,mk，顯然mi=ni–1(i=1,2,…,k)于是

矛盾。因此T連通。9.4.1樹(shù)的基本概念9.4樹(shù)(2)(3)

設(shè)T連通且m=n–1。

先證T無(wú)回路，為此對(duì)n歸納:

n=1時(shí)顯然T無(wú)回路，因這時(shí)m=n–1=0。設(shè)頂點(diǎn)數(shù)為n–1的滿足題設(shè)的圖無(wú)回路，考慮頂點(diǎn)數(shù)為n的圖T。去掉T的一懸掛點(diǎn)構(gòu)成T

。顯然T

仍連通，且m=m–1=n–2=n–1因此由歸納假設(shè)T

無(wú)回路。在T

上加回所刪去的懸掛點(diǎn)得T，故T亦無(wú)回路。

再證添加任一邊產(chǎn)生唯一回路，設(shè)在T的頂點(diǎn)vi

、vj

間添加邊e。由于T連通，故原本有vi到vj的通路，此通路連同邊e構(gòu)成T∪{e}的一條回路。若此回路不唯一，那么去掉邊e后T仍有回路，與以上證明沖突。得證。9.4.1樹(shù)的基本概念9.4樹(shù)(3)(4)

留給讀者自行證明。(4)(5)

留給讀者自行證明。(5)(0)

設(shè)T的任何兩個(gè)頂點(diǎn)之間有且僅有一條通路，那么T顯然連通。T也是無(wú)回路的，否則T中有回路上頂點(diǎn)vi

，vj

，使vi到vj有兩條通路，與題設(shè)矛盾。定義9.21

如果T為G的生成子圖且T為樹(shù)，那么，稱T為無(wú)向圖G的生成樹(shù)。定理9.14

任一連通圖G都至少有一棵生成樹(shù)。證若G無(wú)回路，則G本身為一樹(shù)。若G有回路。則刪去回路上任一邊e，G–e仍連通。對(duì)G–e重復(fù)上述討論，直到得到G的無(wú)回路的連通子圖——生成樹(shù)。例9.179.4.2生成樹(shù)9.4樹(shù)e2e1e4e3e7e5e10e11e9e12e6e8e5e2e1e4e11e12e8e7e5e10e11e9e12e6定理9.15

設(shè)G為連通無(wú)向圖，那么G的任一回路與任一生成樹(shù)T的關(guān)于G的補(bǔ)G–T

，至少有一條公共邊。證設(shè)C為G的一回路，它和G的生成樹(shù)T關(guān)于G的補(bǔ)G–T

無(wú)公共邊，那么C是T的子圖，從而樹(shù)T中有回路，矛盾。定理9.16

設(shè)G為連通無(wú)向圖，那么G的任一割集與任一生成樹(shù)至少有一條公共邊。證設(shè)S為G的割集，但它和G的生成樹(shù)T無(wú)公共邊。那么，刪去G中所有S的邊后所得的圖仍以T為子圖，從而仍連通，這與S為割集矛盾。9.4.2生成樹(shù)9.4樹(shù)定義9.22

設(shè)T為圖G的生成樹(shù)，稱T中的邊為樹(shù)枝，稱G–T中的邊為

弦。對(duì)每一樹(shù)枝t，T–t分為兩個(gè)連通分支T1，T2，那么t及兩端點(diǎn)分別在T1，T2中的弦組成G的一個(gè)割集，它被稱為枝t-割集；而每一條弦e與T中的通路構(gòu)成一回路，它被稱為弦e-回路。

(n,m)圖G的任一生成樹(shù)T恒有n–1條邊，m–n+1條弦；從而有n–1個(gè)枝t-割集，m–n+1個(gè)弦e-回路(t指任一樹(shù)枝，e指任一弦)，分別稱為枝割集系和弦回路系。9.4.2生成樹(shù)9.4樹(shù)9.4.2生成樹(shù)9.4樹(shù)e2e1e4e3e7e5e10e11e9e12e6e8e7e5e10e11e9e12e6

例9.18

(1)共8–1=7枝。(2)e1,e2,e3,e4,e8為弦，共12–8+1=5條。生成樹(shù)：(3)枝e5-割集{e5,e1,e4,e8}

枝e6-割集{e6,e2,e4,e8}

枝e7-割集{e7,e3,e4,e8}

枝e9-割集{e9,e1,e4}

枝e10-割集{e10,e1,e2}

枝e11-割集{e11,e2,e3}

枝e12-割集{e12,e3,e4}(4)弦e1-回路是（e1,e9,e5,e10）弦e2-回路是（e2,e10,e6,e11）弦e3-回路是（e3,e11,e7,e12）弦e4-回路是（e4,e9,e5,e6,e7,e12）弦e8-回路是（e8,e5,e6,e7）定理9.17

在連通無(wú)向圖G中，任一回路與任一割集均有偶數(shù)條公共邊。證設(shè)C為G的任一回路，S為G的任一割集，從G中刪除S的所有邊后得到兩個(gè)互不連通的子圖G1，G2(如圖)。若回路C上的所有頂點(diǎn)都在G1(或G2)中，則C和S無(wú)公共邊，得證。若回路C的一部分頂點(diǎn)在G1中，另一部分在G2中，那么C必定經(jīng)過(guò)S中偶數(shù)條邊(因C為回路)，故C與S有偶數(shù)條公共邊。9.4.2生成樹(shù)9.4樹(shù)

定理9.18

設(shè)G為一連通無(wú)向圖，T是G的生成樹(shù)，

S={e1,e2,e3,…,ek}為枝e1-割集，那么e1必在弦ei-回路中(i=2，3,…，k)，不在其它弦e-回路中。（e1與弦ei-回路恰有兩條公共邊e1和ei，而e1與其它弦e-回路無(wú)公共邊。）證設(shè)C為任一弦ei-回路（i=2，3,…，k），例如C為弦e2-回路，則

e2在S與C中。又據(jù)定理9.17，C與S有偶數(shù)條公共邊。由于S中只有e1為樹(shù)枝，其余各邊均為弦；而C中只有e2為弦，其它各邊均為樹(shù)枝，所以只能還有e1在S與C中。即S與C恰有兩條公共邊e1

和e2，因此e1在弦e2-回路中。由于證明過(guò)程對(duì)一切ei（i=2，3,…，k）均成立，因此定理的前半部分得證。9.4.2生成樹(shù)9.4樹(shù)

定理9.18

設(shè)G為一連通無(wú)向圖，T是G的生成樹(shù)，

S={e1,e2,e3,…,ek}為枝e1-割集，那么e1必在弦ei-回路中(i=2，3,…，k)，不在其它弦e-回路中。（e1與弦ei-回路恰有兩條公共邊e1和ei，而e1與其它弦e-回路無(wú)公共邊。）證定理后半部分：設(shè)C為弦e-回路，而e≠e2,e3,…,ek。而C中只有e為弦，S中e2,e3,…,ek為弦，故eS。由于S中只有e1為樹(shù)枝，其余各邊均為弦；而C中只有e為弦，其它各