離散數(shù)學(xué)及其應(yīng)用-第2版 課件匯 第7-12章 高級(jí)計(jì)數(shù)技術(shù)-格和布爾代數(shù)

第7章

高級(jí)計(jì)數(shù)技術(shù)第7章高級(jí)計(jì)數(shù)技術(shù)7.1遞推方程7.2生成函數(shù)7.1遞推方程定義7.1.1設(shè)序列

簡(jiǎn)記為

。序列

的遞推方程是一個(gè)把

an用序列中在an

前面的一項(xiàng)或多項(xiàng)

ai(i<n)來(lái)表示的等式稱(chēng)作關(guān)于序列{an}的遞推方程。例題例7.2.113世紀(jì)意大利數(shù)學(xué)家斐波那契（Fibonacci）提出了一個(gè)有趣的兔子繁殖問(wèn)題：在一個(gè)島上放了一對(duì)剛出生的兔子，其中一只公兔，一只母兔。經(jīng)過(guò)兩個(gè)月長(zhǎng)成，長(zhǎng)成后即可生育，假定每對(duì)兔子每個(gè)月都可以生出一對(duì)小兔，且新生的小兔也是一只公兔和一只母兔。如果兔子不會(huì)死去，也不會(huì)被運(yùn)走，問(wèn)12個(gè)月時(shí)島上有多少對(duì)兔子?例題（續(xù)）解用

表示第

個(gè)月初的兔子對(duì)數(shù)，n是正整數(shù)。那么

f1=1（最初的兔子對(duì)數(shù)，第1個(gè)月的兔子對(duì)數(shù)）

f2=1（第2個(gè)月的兔子對(duì)數(shù)）f3=1+1=2（最初的一對(duì)加上它們的后代）

f4=2+1=3（第3個(gè)月的2對(duì)加上最初的一對(duì)的后代）f5=3+2=5（第4個(gè)月的3對(duì)加上第3個(gè)月2對(duì)的后代）

f6=5+3=8（第5個(gè)月的5對(duì)加上第4個(gè)月3對(duì)的后代）

f12=89+55=144（第11個(gè)月的89對(duì)加上第10個(gè)月55對(duì)的后代）12個(gè)月時(shí)島上共有兔子144對(duì)。一般的，斐波那契數(shù)列滿(mǎn)足下列遞推方程數(shù)列

稱(chēng)作斐波那契數(shù)列，其中的每一個(gè)數(shù)也稱(chēng)作斐波那契數(shù)。例題在股票投資中，復(fù)合利息的作用是強(qiáng)大的?！肮缮瘛蔽謧悺ぐ头铺?Warren

Buffett)據(jù)說(shuō)就是以年平均30%的復(fù)利戰(zhàn)勝市場(chǎng)，從而成為舉世矚目的價(jià)值投資大師。假設(shè)他的初始投資為10000美元，年投資收益的復(fù)利是30%，那么在30年后賬上的總資產(chǎn)有多少錢(qián)？解

令Pn表示n年后的總資產(chǎn)錢(qián)數(shù)。因?yàn)閚年后賬上的資產(chǎn)總額等于n-1年賬上的資產(chǎn)加上第n年的投資收益，容易知道序列{Pn}滿(mǎn)足遞推關(guān)系例題（續(xù)）初始條件是P0=10000，我們可以知道代入初始條件，得將n=30代入，

26199956.44美元。常系數(shù)線(xiàn)性齊次遞推方程的求解定義7.2.1設(shè)遞推方程滿(mǎn)足其中

為常數(shù),,這個(gè)方程稱(chēng)為k階常系數(shù)線(xiàn)性遞推方程。

為k個(gè)初值。當(dāng)

時(shí)，即稱(chēng)這個(gè)遞推方程為齊次方程。

常系數(shù)線(xiàn)性齊次遞推方程的求解定義7.2.2給定常系數(shù)線(xiàn)性齊次遞推方程如下：（7.2）,求解該方程的基本方法是找到形如G(n)=rn的解，其中r是常數(shù)，即

等式兩邊同時(shí)除以rn-k，得

因此我們將形如方程

稱(chēng)為該遞推方程的特征方程，特征方程的根r稱(chēng)為遞推方程的特征根。定理定理7.2.1設(shè)g1(n)和g2(n)是遞推方程(7.2)的兩個(gè)解，c1,c2為任意常數(shù)，則c1g1(n)+c2

g2(n)也是這個(gè)遞推方程的解。證明

將

g1(n)和g2(n)代入到方程(7.2)得，因此c1g1(n)+c2

g2(n)也是這個(gè)遞推方程的解。

推論

若

是遞推方程(7.2)的特征根，則

也是該遞推方程的解，其中

是任意常數(shù)。以上推論說(shuō)明

是遞推方程的解。那么，除了這種形式的解以外，是否存在其他形式的解?為了解決這個(gè)問(wèn)題，先定義通解。定義7.2.3能夠表示遞推方程（7.2）的每個(gè)解

的表達(dá)式稱(chēng)為該遞推方程的通解。定理定理7.2.2設(shè)

是遞推方程(7.2)不等的特征根，則

為該遞推方程的通解，其中

是任意常數(shù)。證明

此定理是推廣了定理7.2.1，證明類(lèi)似。例題例7.2.1求下面遞推方程的解：其中

，

。解遞推方程的特征方程是

，它的根是2和-1。因此，遞推方程的通解為c1,c2是常數(shù)。將初值

代入得解得,從而得到遞推方程的解為，

定理定理7.2.3設(shè)

是遞推方程（7.2）的不相等的特征根，且

ri的重?cái)?shù)為ei，其中

那么該遞推方程的通解是其中

為常數(shù)。

例題例7.2.4求解以下遞推方程解

特征方程

為即

特征根是2，其重?cái)?shù)是3，根據(jù)定理7.2.3

通解為代入初始條件，則有以下方程組解得

原方程的解為例題（續(xù)）解得

原方程的解為常系數(shù)線(xiàn)性非齊次遞推方程的求解常系數(shù)線(xiàn)性非齊次遞推方程的標(biāo)準(zhǔn)形是

（7.3）其中

f(n)是只依賴(lài)于n的函數(shù)。將

稱(chēng)作相伴的線(xiàn)性齊次遞推方程。定理7.2.4設(shè)

是對(duì)應(yīng)的相伴的線(xiàn)性齊次遞推方程的通解，

是方程（7.3）的一個(gè)特解，則是遞推方程（7.3）的通解。例題例7.2.5找出下述遞推方程的通解：解

該方程對(duì)應(yīng)相伴的線(xiàn)性齊次遞推方程是

它的通解是c3n，其中c是常數(shù)。設(shè)特解

，其中c1,c2

是常數(shù)。代入遞推方程得例題（續(xù)）整理得從而得線(xiàn)性方程組解得

因此

是一個(gè)特解，根據(jù)定理7.2.4，原方程的通解為初始條件

帶入通解得,因此得原方程的通解為7.2生成函數(shù)生成函數(shù)是研究組合計(jì)數(shù)中的一個(gè)重要工具，其基本思想是把要計(jì)數(shù)或研究的離散數(shù)列同多項(xiàng)式或冪級(jí)數(shù)的系數(shù)一一對(duì)應(yīng)起來(lái)，從而可以用數(shù)學(xué)分析的方法去研究這一數(shù)列，給出數(shù)列的一個(gè)顯示解或漸近解。牛頓二項(xiàng)式系數(shù)與牛頓二項(xiàng)式定理定義7.3.1設(shè)r為實(shí)數(shù)，n為整數(shù)，引入形式符號(hào)稱(chēng)為牛頓二項(xiàng)式系數(shù)．定理定理7.3.1牛頓二項(xiàng)式定理．

設(shè)r為實(shí)數(shù)，則對(duì)一切實(shí)數(shù)

，有其中

生成函數(shù)的定義及其性質(zhì)定義7.3.2設(shè)序列

，構(gòu)造形式冪級(jí)數(shù)

稱(chēng)f(x)為序列

的生成函數(shù)。

定義7.3.2給出的生成函數(shù)有時(shí)叫做

的普通生成函數(shù)，以和這個(gè)序列的其他類(lèi)型的生成函數(shù)相區(qū)別，序列

叫做f(x)的生成序列。例題例7.3.1設(shè)m是正整數(shù)，令ak=C(m,k)k=0,1,…m，

。那么序列{ak}的生成函數(shù)是什么？解這個(gè)序列的生成函數(shù)是由二項(xiàng)式定理可得

生成函數(shù)的性質(zhì)設(shè)

是已知序列，它們的生成函數(shù)分別為若

為常數(shù)，則

若

，則

若

，則

若

生成函數(shù)的性質(zhì)(續(xù)）(5)若

，則

(6)若

，則(7)若

，且

收斂，則

(8)若

為常數(shù)，則

(9)若

，則

，其中

為A(x)的導(dǎo)數(shù)。(10)若

，則

例題生成函數(shù)與序列是一一對(duì)應(yīng)的。例7.3.2求序列{an}的生成函數(shù)

解

例題已知{an}的生成函數(shù)為

，求an.

解

因此我們可以得到

生成函數(shù)的應(yīng)用例7.3.4求解遞推方程

且初始條件

解

設(shè)序列

的生成函數(shù)為首先注意到例題（續(xù)）因?yàn)閚>=1時(shí)有

且

所以有即得所以

指數(shù)型生成函數(shù)定義7.3.3

設(shè){an}為序列，構(gòu)造形式冪級(jí)數(shù)稱(chēng)

為{an}的指數(shù)型生成函數(shù)。例題設(shè){an}是序列，求下列數(shù)列的指數(shù)生成函數(shù)

。（1）

，m為正整數(shù)；（2）an=1；（3）an=bn

；解（1）

（2）

（3）定理定理7.3.2

設(shè)

為多重集，則S的r-排列數(shù)由指數(shù)生成函數(shù)的展開(kāi)式中

的系數(shù)給出。例題例7.3.10由1，2，3，4組成的5位數(shù)中，要求1出現(xiàn)不超過(guò)2次，但不能不出現(xiàn)，2出現(xiàn)不超過(guò)1次，3出現(xiàn)至多2次，4出現(xiàn)偶數(shù)次，求這樣的5位數(shù)個(gè)數(shù)。解展開(kāi)后

的

的系數(shù)為185，所以這樣的5位數(shù)有185個(gè)。例題例7.3.11用3個(gè)1,2個(gè)2,5個(gè)3這十個(gè)數(shù)字能構(gòu)成多少個(gè)偶的4位數(shù)？

解問(wèn)題是求多重集

的4-排列數(shù)，且要求排列的末尾為2。因?yàn)楦鶕?jù)已知條件，只能有2為末尾才為偶數(shù)，所以可把問(wèn)題轉(zhuǎn)換為求多重集

的3-排列數(shù)。其指數(shù)生成函數(shù)為展開(kāi)后的

的系數(shù)為20，所以能組成20個(gè)四位數(shù)的偶數(shù)。第8章

圖論圖論研究圖的點(diǎn)和線(xiàn)的關(guān)系及特點(diǎn)，是研究離散結(jié)構(gòu)及其特性的重要數(shù)學(xué)分支?，F(xiàn)實(shí)世界中，許多事務(wù)都可以抽象成點(diǎn)及它們之間的聯(lián)系，都可以用圖來(lái)描述。如哥尼斯堡七橋問(wèn)題、Internet網(wǎng)、社會(huì)關(guān)系網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)、電路網(wǎng)絡(luò)等。第8章圖8.1圖的基本概念8.2通路與回路、連通的概念8.3圖的表示8.4獨(dú)立集、覆蓋和支配集39ABCD圖論起源公元十八世紀(jì)有這樣一個(gè)問(wèn)題：在東普魯士有個(gè)哥尼斯堡城（

konigsberg，現(xiàn)名為加里寧格勒；現(xiàn)屬于俄羅斯聯(lián)邦）。哥尼斯堡城位于pregel河畔，河中有兩個(gè)島，城市中的各個(gè)部分由七座橋相連。

最早引入圖論處理的問(wèn)題就是哥尼斯堡七橋問(wèn)題。

1736年，瑞士數(shù)學(xué)家L.Eluer（歐拉）在他發(fā)表的“哥尼斯堡七座橋”的著名文章中闡述了解決這個(gè)問(wèn)題的觀(guān)點(diǎn)，從而被譽(yù)為圖論之父。

當(dāng)時(shí)，城中的居民熱衷于這樣一個(gè)問(wèn)題，從四塊陸地的任一塊出發(fā)，怎樣才能做到經(jīng)過(guò)每座橋一次且僅一次，然后回到出發(fā)點(diǎn)。問(wèn)題看來(lái)并不復(fù)雜，但當(dāng)?shù)氐木用窈陀稳俗隽瞬簧俚膰L試，卻都沒(méi)有取得成功。

Euler將四塊陸地表示成四個(gè)結(jié)點(diǎn)，凡陸地間有橋相連的，便在兩點(diǎn)間連一條邊。ABCDDCAB

此時(shí)，哥尼斯堡七橋問(wèn)題歸結(jié)為：從A,B,C,D任一點(diǎn)出發(fā)，通過(guò)每條邊一次且僅一次而返回出發(fā)點(diǎn)的回通路是否存在？

歐拉斷言這樣的回通路是不存在的。

理由是：從圖中的任一點(diǎn)出發(fā)，為了要回到原來(lái)的出發(fā)點(diǎn)，要求與每個(gè)點(diǎn)相關(guān)聯(lián)的邊數(shù)均為偶數(shù)。這樣才能保證從一條邊進(jìn)入某點(diǎn)后，再?gòu)牧硪粭l邊出去，從一個(gè)點(diǎn)的不同的兩條邊一進(jìn)一出才能回到出發(fā)點(diǎn)。而圖中的A,B,C,D全是與奇數(shù)條邊相連，由此可知所要求的回通路是不可能存在的。8.1圖的基本概念8.1.1無(wú)向圖和有向圖8.1.2度的概念8.1.3握手定理8.1.4圖的分類(lèi)8.1.5子圖與補(bǔ)圖8.1.6

圖的同構(gòu)44無(wú)向圖和有向圖定義一個(gè)無(wú)向圖可以表示為G=（V，E），其中V是非空有限結(jié)點(diǎn)集，稱(chēng)V中的元素為結(jié)點(diǎn)或頂點(diǎn)；E是邊集，其中的元素是由V中的元素組成的無(wú)序?qū)?，稱(chēng)E中的元素為邊。若（v，w）是無(wú)序?qū)?，則（v，w）=（w，v）。例如,G=<V,E>如圖所示,其中V={v1,v2,…,v5}E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}45e1e2e3e4e5e6e7v5v1v2v3v4有向圖定義

一個(gè)有向圖可以表示為D=（V，E），其中V是非空有限結(jié)點(diǎn)集，稱(chēng)V中的元素為結(jié)點(diǎn)或頂點(diǎn)；E是有向邊集，E中的元素是由V中的元素組成的有序?qū)?，稱(chēng)E中的元素為有向邊。有向圖D=（V，E）。結(jié)點(diǎn)集V={v1，v2，v3，v4}，有向邊集E={<v1，v1>，<v1，v2>，<v1，v2>，<v1，v3>，<v2，v3>，<v3，v4>，<v4，v3>}。在有向圖中，<b，a>

<a，b>46圖的術(shù)語(yǔ)定義

在無(wú)向圖中，如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的邊多于一條，則稱(chēng)這些邊為平行邊。如果有邊關(guān)聯(lián)于一對(duì)結(jié)點(diǎn)，則稱(chēng)這對(duì)結(jié)點(diǎn)是鄰接的。一條邊的兩個(gè)端點(diǎn)如果關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)，則稱(chēng)為環(huán)，和任何邊都不關(guān)聯(lián)的點(diǎn)稱(chēng)為孤立點(diǎn)。邊e2和e3是平行邊，邊e1關(guān)聯(lián)結(jié)點(diǎn)v1和v3，則稱(chēng)v1和v3是鄰接的，邊e5=（v3，v3）是環(huán)，v4是孤立點(diǎn)。圖的術(shù)語(yǔ)在有向圖中，如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的方向相同的有向邊多于一條，則稱(chēng)這些有向邊為多重有向邊或平行邊。如關(guān)聯(lián)于結(jié)點(diǎn)v1和v2的兩條有向邊是平行邊，而關(guān)聯(lián)于結(jié)點(diǎn)v3和v4的兩條有向邊方向相反，不是平行邊。（v1，v1）稱(chēng)為環(huán)。對(duì)于有向邊（v2，v3），稱(chēng)v2為起點(diǎn)，v3為終點(diǎn)，v2和v3是鄰接的。圖的術(shù)語(yǔ)n階圖:n個(gè)頂點(diǎn)的圖零圖:E=

的圖平凡圖:1階零圖在圖的定義中規(guī)定結(jié)點(diǎn)集合V為非空集，但在運(yùn)算中可能產(chǎn)生結(jié)點(diǎn)集為空集的運(yùn)算結(jié)果，因此規(guī)定結(jié)點(diǎn)集為空集的圖為空?qǐng)D，記為

度的概念

定義

設(shè)G=<V,E>為無(wú)向圖,v

V,v所關(guān)聯(lián)的邊數(shù)稱(chēng)為v的度數(shù)，簡(jiǎn)稱(chēng)度，記作d(v)。懸掛頂點(diǎn):度數(shù)為1的頂點(diǎn)懸掛邊:與懸掛頂點(diǎn)關(guān)聯(lián)的邊G的最大度(G)=max{d(v)|v

V}G的最小度(G)=min{d(v)|v

V}例如d(v5)=3,d(v2)=4,d(v1)=4,

(G)=4,

(G)=1,v4是懸掛頂點(diǎn),e7是懸掛邊,e1是環(huán)50e1e2e3e4e5e6e7v5v1v2v3v4頂點(diǎn)的度數(shù)(續(xù))定義

設(shè)D=<V,E>為有向圖,v

V,以v為起點(diǎn)所關(guān)聯(lián)的邊數(shù)稱(chēng)為v的出度，記作d+(v)；以v為終點(diǎn)所關(guān)聯(lián)的邊數(shù)稱(chēng)為v的入度，記作d

(v)。v的總度數(shù)(度)d(v)是v的出度和入度之和：

d(v)=d+(v)+d-(v)

+(D),

+(D),

(D),

(D),

(D),

(D)懸掛頂點(diǎn),懸掛邊例如d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,

+=4,

+=0,

=3,

=1,

=5,

=351e1e2e3e4e5e6e7dabc握手定理定理

設(shè)圖G=(V,E)為無(wú)向圖或有向圖，G有n個(gè)結(jié)點(diǎn)v1,v2,…,vn，e條邊(無(wú)向或有向),則圖G中所有結(jié)點(diǎn)的度數(shù)之和為邊數(shù)的兩倍，即證圖中每條邊(包括環(huán))均有兩個(gè)端點(diǎn),所以在計(jì)算各頂點(diǎn)度數(shù)之和時(shí),每條邊均提供2度,m條邊共提供2m度.推論任何圖(無(wú)向圖和有向圖)中，度數(shù)為奇數(shù)的結(jié)點(diǎn)的個(gè)數(shù)為偶數(shù)。52定理7.1.2定理

在有向圖中，所有結(jié)點(diǎn)的入度之和與所有結(jié)點(diǎn)的出度之和相等，都等于圖中的有向邊數(shù)。證在有向圖中，每條有向邊均有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)。于是在計(jì)算圖中各結(jié)點(diǎn)的出度之和與各結(jié)點(diǎn)的入度之和時(shí)，每條有向邊各提供一個(gè)出度和一個(gè)入度。當(dāng)然e條有向邊共提供e個(gè)出度和e個(gè)入度。因此所有結(jié)點(diǎn)的入度之和與所有結(jié)點(diǎn)的出度之和相等，都等于圖中的有向邊數(shù)e。圖的度數(shù)列設(shè)V={v1,v2,…,vn}為圖G的結(jié)點(diǎn)集，稱(chēng)(d(v1),d(v2),…,d(vn))為G的度數(shù)序列。一個(gè)由非負(fù)整數(shù)構(gòu)成的序列d=（d1,d2,…,dn）,如d恰好是一個(gè)圖的所有結(jié)點(diǎn)度數(shù)序列，稱(chēng)這個(gè)整數(shù)序列是可圖化的，根據(jù)握手定理，此序列的各個(gè)數(shù)之和必為偶數(shù)。圖的度數(shù)列設(shè)無(wú)向圖G的頂點(diǎn)集V={v1，v2，……，vn}G的度數(shù)列:d(v1),d(v2),…,d(vn)如右圖度數(shù)列:4,4,2,1,3設(shè)有向圖D的頂點(diǎn)集V={v1，v2，……，vn}D的度數(shù)列d(v1),d(v2),…,d(vn)D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d

(v1),d

(v2),…,d

(vn)如右圖度數(shù)列:5,3,3,3出度列:4,0,2,1入度列:1,3,1,255e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc例題例

自然數(shù)序列(3，3，2，2，1)，(4，2，2，1，1)能作為圖的結(jié)點(diǎn)的度數(shù)序列嗎？為什么？

解

在(3，3，2，2，1)中各個(gè)數(shù)之和為奇數(shù)，由握手定理可知，(3，3，2，2，1)不能作為圖的結(jié)點(diǎn)的度數(shù)序列。(4，2，2，1，1)能作為圖的結(jié)點(diǎn)的度數(shù)序列，下圖中的兩個(gè)圖都是以（4,2,2,1,1）為結(jié)點(diǎn)度數(shù)序列。實(shí)例57例2已知圖G有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)的度數(shù)均小于等于2,問(wèn)G至少有多少個(gè)頂點(diǎn)?解設(shè)G有n個(gè)頂點(diǎn).由握手定理,43+2(n-4)210解得n8例3已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和1,2,1,2,1,求它的入度列解2,1,1,1,2實(shí)例例4證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的多面體.58證用反證法.假設(shè)存在這樣的多面體,作無(wú)向圖G=<V,E>,其中V={v|v為多面體的面},

E={(u,v)|u,v

V

u與v有公共的棱u

v}.根據(jù)假設(shè),|V|為奇數(shù)且v

V,d(v)為奇數(shù).這與握手定理的推論矛盾.

圖的分類(lèi)定義

設(shè)圖G=（V，E）為無(wú)向圖或有向圖，如果G中不含平行邊，也不含環(huán)，則稱(chēng)為簡(jiǎn)單圖。定義

設(shè)圖G=（V，E）為無(wú)向圖或有向圖，如果G中含有平行邊，則稱(chēng)為多重圖。簡(jiǎn)單圖多重圖多重圖簡(jiǎn)單圖圖的應(yīng)用1、航班路線(xiàn)圖有向多重圖2、微博關(guān)注圖有向簡(jiǎn)單圖3、合作關(guān)系圖無(wú)向簡(jiǎn)單圖或多重圖完全圖(1)定義

設(shè)G=（V，E）是n階無(wú)向簡(jiǎn)單圖，若G中任何結(jié)點(diǎn)都與其余的n-1個(gè)結(jié)點(diǎn)相鄰，則稱(chēng)G為n階無(wú)向完全圖，記作Kn。

完全圖頂點(diǎn)數(shù)n,邊數(shù)m=n(n-1)/2,(G)=(G)=n-1K3K5完全圖(2)設(shè)G=（V，E）為n階有向簡(jiǎn)單圖，若對(duì)于V中任意的兩個(gè)結(jié)點(diǎn)u和v，既有有向邊(u，v)，又有有向邊(v，u)，則稱(chēng)G是n階有向完全圖。

頂點(diǎn)數(shù)n,邊數(shù)m=n(n-1),

+(D)=

+(D)=

-(D)=

-(D)=n-1,

(D)=

(D)=2(n-1)無(wú)特別說(shuō)明時(shí)，完全圖均指無(wú)向完全圖。定理

例題例5判斷下列各非負(fù)整數(shù)列是否是簡(jiǎn)單圖的結(jié)點(diǎn)度數(shù)序列？（1）（5,5,4,4,2,1）（2）（5,4,3,2,2）（3）（3,3,2,2,1,1）（4）（4，4，3，2，1）（5）

解

（1）根據(jù)握手定理的推論可知，不是圖的結(jié)點(diǎn)度數(shù)序列，因?yàn)橛?個(gè)奇數(shù)。

（2）中有5個(gè)數(shù)，最大數(shù)是5，根據(jù)定理7.1.3，它不是簡(jiǎn)單圖的結(jié)點(diǎn)序列。

（3）是簡(jiǎn)單圖的結(jié)點(diǎn)序列。下圖的兩個(gè)無(wú)向簡(jiǎn)單圖都是（3,3,2,2,1,1）為結(jié)點(diǎn)度數(shù)序列。

例題（續(xù)）（4）不是簡(jiǎn)單圖的度數(shù)序列。根據(jù)定理8.1.4，把序列(4,4,3,2,1)的最大元素4刪去，剩下4個(gè)元素都減1，得到序列（3，2，1，0），此序列不可簡(jiǎn)單圖化，因此以(4,4,3,2,1)為結(jié)點(diǎn)度數(shù)序列的圖不是簡(jiǎn)單圖的度數(shù)序列。（5）中的最大值d1>=n,根據(jù)定理8.1.3，不是簡(jiǎn)單圖的結(jié)點(diǎn)序列。正則圖定義

設(shè)G為n階無(wú)向簡(jiǎn)單圖，若

v

V（G），均有d(v)=k,則稱(chēng)G為k-正則圖。

K52正則圖4正則圖

3正則圖彼得松圖正則圖根據(jù)握手定理，n階k-正則圖的邊數(shù)

。當(dāng)k為奇數(shù)時(shí)，n為偶數(shù)。當(dāng)k=0時(shí)，0-正則圖就是n階零圖。n階無(wú)向完全圖是(n-1)-正則圖。環(huán)圖和輪圖定義

如果圖G=（V，E）的結(jié)點(diǎn)集V={v1，v2，

vn}（n

3），邊集E={（v1，v2），（v2，v3），

（vn-1，vn），（vn，v1）}，則稱(chēng)G為環(huán)圖，記為Cn。下圖是C3,C4,C5,C6。定義

當(dāng)給環(huán)圖Cn-1（n

4）添加一個(gè)結(jié)點(diǎn)，并把這個(gè)結(jié)點(diǎn)和Cn-1里的每個(gè)結(jié)點(diǎn)逐個(gè)連接后得到的圖成為輪圖，記作Wn。下圖是輪圖W4，W5，W6，W7。方體圖定義

如果圖G=（V，E）有2n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)表示一個(gè)長(zhǎng)度為n的位串，任何兩個(gè)相鄰的結(jié)點(diǎn)表示的位串只有一位不同，則稱(chēng)G稱(chēng)為n方體圖，記作Qn。690110110001010101100000111011001Q1Q2Q3方體圖對(duì)任意n

N

，Qn

是將兩個(gè)Qn-1

圖的對(duì)應(yīng)結(jié)點(diǎn)連接起來(lái)的簡(jiǎn)單圖.Q0

有1個(gè)結(jié)點(diǎn).Q0Q1Q2Q3Q4結(jié)點(diǎn)數(shù):2n.邊數(shù)：n2n-1二分圖定義

如果圖G=（V，E）的結(jié)點(diǎn)集V能劃分為兩個(gè)子集：V1和V2，使每條邊有一個(gè)端點(diǎn)在V1中,另一個(gè)端點(diǎn)在V2中，則稱(chēng)該圖為二分圖（或二部圖）。定義

二分圖G=（V，E）的結(jié)點(diǎn)集V能劃分為兩個(gè)子集：V1和V2，若V1中的每個(gè)結(jié)點(diǎn)和V2中的每個(gè)結(jié)點(diǎn)均有邊相連，則稱(chēng)G為完全二分圖。若|V1|=m，|V2|=n,則可記為Km,n。下圖所示的是K2,3和K3,3。

帶權(quán)圖定義7.1.17每個(gè)結(jié)點(diǎn)或每條邊都帶有數(shù)值的圖稱(chēng)為帶權(quán)圖。

邊帶權(quán)圖結(jié)點(diǎn)帶權(quán)圖可以用有序三元組或有序四元組表示帶權(quán)圖。如G=(V,E,f)，G=(V,E,g)或G=(V,E,f,g)，其中V是結(jié)點(diǎn)集，E是邊集，f是結(jié)點(diǎn)所帶的權(quán)的集合，g是邊所帶的權(quán)的集合。346218.1.5子圖與補(bǔ)圖定義

設(shè)圖G=（V，E）設(shè)e

E，從G圖中刪去邊e得到的圖表示為G-e,稱(chēng)為刪除邊運(yùn)算；設(shè)E1

E，從G圖中刪去E1的所有邊得到的圖表示為G-E1,稱(chēng)為刪除邊集運(yùn)算。設(shè)v

V，從G圖中刪去結(jié)點(diǎn)v及v關(guān)聯(lián)的所有邊得到的圖表示為G?v,稱(chēng)為刪除結(jié)點(diǎn)運(yùn)算；設(shè)V1

V，從G圖中刪去V1中所有結(jié)點(diǎn)及它們關(guān)聯(lián)的所有邊得到的圖表示為G?V1,稱(chēng)為刪除結(jié)點(diǎn)集運(yùn)算。設(shè)e=(u,v)

E，從G圖中刪去邊e,將e的兩個(gè)端點(diǎn)u、v用一個(gè)新的結(jié)點(diǎn)w代替，將u,v關(guān)聯(lián)的所有邊都關(guān)聯(lián)結(jié)點(diǎn)w，稱(chēng)為邊e的收縮，記為G\e。設(shè)u,v

V，在u,v之間加一條邊（u,v），稱(chēng)為加新邊，表示為G

(u,v)(或G+(u,v))。例題在下圖中，(1)為圖G，(2)為G-e1,(3)為G-{e1,e4}，(4)為G-v3,(5)為G-{v1,v3},(6)為G\e1。子圖定義

設(shè)G=（V，E）和G1=(V1，E1)是兩個(gè)圖。若V1

V，且E1

E，則稱(chēng)G1是G的子圖，G是G1的母圖，記作G1

G。若G1

G且G1

G(即V1

V,或E1

E)，則稱(chēng)G1是G的真子圖。若G1

G且V1=V，則稱(chēng)G1是G的生成子圖。對(duì)圖G=（V，E），設(shè)V1

V且V1

，以V1為結(jié)點(diǎn)集，以?xún)啥它c(diǎn)均在V1中的全體邊為邊集的G的子圖，稱(chēng)G1為G的由結(jié)點(diǎn)集V1導(dǎo)出的子圖，記為G（V1）。對(duì)圖G=（V，E），設(shè)E1

E且E1

，以E1為邊集，以E1中邊關(guān)聯(lián)的結(jié)點(diǎn)的全體為結(jié)點(diǎn)集的G的子圖，稱(chēng)G1為G的由邊集E1導(dǎo)出的子圖，記為G（E1）。例題(1),(2),(3)是(1)的子圖,(2),(3)是真子圖,(1)是母圖.(1),(3)是(1)的生成子圖.(2)是{d,e,f}的導(dǎo)出子圖,也是{e5,e6,e7}導(dǎo)出子圖.(3)是{e1,

e3,

e5,e7}的導(dǎo)出子圖76aabbccdddeeefffe1e1e2e3e3e4e5e5e5e6e6e7e7e7(1)(2)(3)若V1

V，且E1

E，則稱(chēng)G1是G的子圖，G是G1的母圖，記作G1

G。若G1

G且G1

G(即V1

V,或E1

E)，則稱(chēng)G1是G的真子圖。若G1

G且V1=V，則稱(chēng)G1是G的生成子圖。對(duì)圖G=（V，E），設(shè)V1

V且V1

，以V1為結(jié)點(diǎn)集，以?xún)啥它c(diǎn)均在V1中的全體邊為邊集的G的子圖，稱(chēng)G1為G的由結(jié)點(diǎn)集V1導(dǎo)出的子圖，記為G（V1）。對(duì)圖G=（V，E），設(shè)E1

E且E1

，以E1為邊集，以E1中邊關(guān)聯(lián)的結(jié)點(diǎn)的全體為結(jié)點(diǎn)集的G的子圖，稱(chēng)G1為G的由邊集E1導(dǎo)出的子圖，記為G（E1）。補(bǔ)圖定義

設(shè)G=(V，E)是n階無(wú)向簡(jiǎn)單圖或有向簡(jiǎn)單圖。以V為結(jié)點(diǎn)，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱(chēng)為G相對(duì)于完全圖的補(bǔ)圖，簡(jiǎn)稱(chēng)G的補(bǔ)圖，記作~G。

補(bǔ)圖定義

設(shè)G=(V，E)是n階無(wú)向簡(jiǎn)單圖或有向簡(jiǎn)單圖。以V為結(jié)點(diǎn)，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱(chēng)為G相對(duì)于完全圖的補(bǔ)圖，簡(jiǎn)稱(chēng)G的補(bǔ)圖，記作~G。

補(bǔ)圖定義

設(shè)G=(V，E)是n階無(wú)向簡(jiǎn)單圖或有向簡(jiǎn)單圖。以V為結(jié)點(diǎn)，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱(chēng)為G相對(duì)于完全圖的補(bǔ)圖，簡(jiǎn)稱(chēng)G的補(bǔ)圖，記作~G。

G1~G1

G2~G2例題證明：在任意6個(gè)人的集會(huì)上，總會(huì)有3個(gè)人以前互相認(rèn)識(shí)或有3個(gè)人以前互相不認(rèn)識(shí)（假設(shè)認(rèn)識(shí)是相互的）。即證明6個(gè)結(jié)點(diǎn)的無(wú)向圖G或其補(bǔ)圖~G中至少有一個(gè)完全子圖K3。證明：考慮完全圖K6,結(jié)點(diǎn)v1與其余5個(gè)結(jié)點(diǎn)各有一條邊相連，這5條邊一定有3條邊在G或~G中。假設(shè)有3條邊在G圖中，這3條邊為（v1,v2）、（v1,v3）、（v1,v4）。對(duì)于結(jié)點(diǎn)v2、v3、v4，若在G中v2、v3、v4間無(wú)邊連接，則v2、v3、v4相互不認(rèn)識(shí)，如果至少存在一條邊，如v2、v3間存在一條邊，則在v1、v2、v3三個(gè)結(jié)點(diǎn)都有邊連接，構(gòu)成一個(gè)K3子圖，即有三個(gè)人相互認(rèn)識(shí)。因此，總會(huì)有三個(gè)人相互認(rèn)識(shí)或不認(rèn)識(shí)。8.1.6圖的同構(gòu)定義

設(shè)兩個(gè)圖G=（V，E）和G'=（V'，E'），如果從V到V'存在雙射函數(shù)f，使得對(duì)于任意的u，v

V，(u，v)

E,當(dāng)且僅當(dāng)(f(u)，f(v))

E'；如果在u，v間存在平行邊，則關(guān)聯(lián)于結(jié)點(diǎn)u，v的平行邊數(shù)與關(guān)聯(lián)于結(jié)點(diǎn)f(u)，f(v)的平行邊數(shù)相同，則稱(chēng)G與G'是同構(gòu)的，記作G

G'。a

v1，b

v5，c

v3，d

v2，e

v4判斷兩個(gè)圖同構(gòu)的必要條件1)必須具有相同的頂點(diǎn)數(shù)；2)必須具有相同的邊數(shù)；3)度數(shù)相同的結(jié)點(diǎn)數(shù)相等。（對(duì)應(yīng)頂點(diǎn)的度數(shù)相同.）4)相同長(zhǎng)度的回路數(shù)相同。

判斷兩個(gè)圖同構(gòu)的必要條件不同構(gòu)的圖例題例6畫(huà)出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖解總度數(shù)為6,分配給4個(gè)頂點(diǎn),最大度為3,且奇度頂點(diǎn)數(shù)為偶數(shù),有下述3個(gè)度數(shù)列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.841,1,1,31,1,2,20,2,2,2例題例7畫(huà)出3個(gè)以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的無(wú)向簡(jiǎn)單圖85自互補(bǔ)圖定義

如果一個(gè)圖同構(gòu)于它的補(bǔ)圖,則稱(chēng)此圖為自互補(bǔ)圖。例8

試證明：一個(gè)圖為自互補(bǔ)圖，其對(duì)應(yīng)的完全圖的邊數(shù)必為偶數(shù)。證明

設(shè)G為自互補(bǔ)圖，G有e條邊，并設(shè)G對(duì)應(yīng)的完全圖的邊數(shù)為m，則G的補(bǔ)圖的邊數(shù)為m?e。對(duì)于自互補(bǔ)圖G，有G

~G，所以e=m?e，m=2e

是偶數(shù)。

8.2通路與回路、連通的概念8.2.1通路與回路8.2.2連通的概念87定義7.2.1給定圖G=（V，E）中，以v0為起點(diǎn)，vn為終點(diǎn)的由結(jié)點(diǎn)和邊交替出現(xiàn)的序列v0e1v1e2v2…vn-1envn稱(chēng)為從結(jié)點(diǎn)v0到vn的長(zhǎng)度為n的通路。G是無(wú)向圖時(shí)，其中的邊ei的端點(diǎn)是vi-1和vi（i=1，2，

n）；G是有向圖時(shí)，其中的有向邊ei的起點(diǎn)是vi-1，終點(diǎn)是vi（i=1，2，

n）。

887.2.1通路與回路通路與回路若一條通路的起點(diǎn)和終點(diǎn)是同一點(diǎn)，稱(chēng)它是一條回路。若通路中的所有邊互不相同，則稱(chēng)它為簡(jiǎn)單通路或跡。若回路中的所有邊互不相同，則稱(chēng)它為簡(jiǎn)單回路或閉跡。若通路中的所有結(jié)點(diǎn)互不相同，所有邊互不相同，則稱(chēng)它為基本通路或初級(jí)通路、路徑。若回路中的所有結(jié)點(diǎn)互不相同，所有邊互不相同，則稱(chēng)它為基本回路或初級(jí)回路、圈。一條通路或回路包含的邊的數(shù)目稱(chēng)為通路或回路的長(zhǎng)度。如果一條回路的長(zhǎng)度為奇(偶)數(shù)，則稱(chēng)為奇(偶)回路。例題v1e1v2e9v6e9v2e8v6e7v5是從結(jié)點(diǎn)v1到v5的長(zhǎng)度為5的通路，v2e4v4e5v5e6

v2e1v1e10v6是簡(jiǎn)單通路，v2e4v4e5v5e6

v2e1v1e10v6e9v2是簡(jiǎn)單回路，v3e3v4e5v5e6v2e1v1e10v6是基本通路，v2e1v1e10v6e7v5e6

v2

是基本回路或圈。例題v1e2v2e5v4e4v3是從結(jié)點(diǎn)v1到v3的長(zhǎng)度為3的通路，v1e2v2e5v4e6v2是簡(jiǎn)單通路，v1e2v2e5v4e4v3

是基本通路。在有向圖中要注意邊的方向，通路上一條邊的終點(diǎn)是這條通路下一條邊的起點(diǎn)說(shuō)明(1)表示方法①按定義用頂點(diǎn)和邊的交替序列,

=v0e1v1e2…elvl②用邊序列,

=e1e2…el③簡(jiǎn)單圖中,用頂點(diǎn)序列,

=v0v1…vl(2)在無(wú)向圖中,長(zhǎng)度為1的圈由環(huán)構(gòu)成.長(zhǎng)度為2的圈由兩條平行邊構(gòu)成.在無(wú)向簡(jiǎn)單圖中,所有圈的長(zhǎng)度

3.在有向圖中,長(zhǎng)度為1的圈由環(huán)構(gòu)成.在有向簡(jiǎn)單圖中,所有圈的長(zhǎng)度

2.92說(shuō)明(續(xù))(3)初級(jí)通路(回路)是簡(jiǎn)單通路(回路),但反之不真93初級(jí)通路非初級(jí)的簡(jiǎn)單通路初級(jí)回路非初級(jí)的簡(jiǎn)單回路定理定理

在n階圖G中，若從結(jié)點(diǎn)u到v（u

v）存在通路，則從u到v存在長(zhǎng)度小于或等于n-1的通路。證明

設(shè)ue1v1e2v2…ekv為G中從u到v的長(zhǎng)度為k的通路，通路上有k+1個(gè)結(jié)點(diǎn)。若通路長(zhǎng)度k

n-1，則定理成立。若k>n-1，該通路上的結(jié)點(diǎn)數(shù)大于G的結(jié)點(diǎn)數(shù)n，根據(jù)鴿巢原理，必有一個(gè)結(jié)點(diǎn)在通路上出現(xiàn)兩次，即存在t，s，0

t

s

k，使得vs=vt，因此通路上存在回路。刪去回路，至少要?jiǎng)h去一條邊，得通路ue1v1e2v2…vtes+1…ekv仍是從u到v的通路，長(zhǎng)度至少減小1。重復(fù)上述過(guò)程，經(jīng)過(guò)有限步后，一定得到從u到v的長(zhǎng)度小于或等于n?1的通路。推論推論

在n階圖G中，若從結(jié)點(diǎn)u到v（u

v）存在通路，則從u到v存在長(zhǎng)度小于或等于n?1的基本通路。證明：若通路中沒(méi)有相同的頂點(diǎn)(即基本通路),長(zhǎng)度必

n

1.若有相同的頂點(diǎn),刪去這兩個(gè)頂點(diǎn)之間的這一段,仍是u到v的通路.重復(fù)進(jìn)行,直到?jīng)]有相同的頂點(diǎn)為止.定理定理

在n階圖G中，若從結(jié)點(diǎn)u到自身存在回路，則回路的長(zhǎng)度小于或等于n。推論

在n階圖G中，若從結(jié)點(diǎn)u到自身存在回路，則一定存在從結(jié)點(diǎn)u到自身的長(zhǎng)度小于或等于n的基本回路。短程線(xiàn)與距離設(shè)u,v為圖G中任意兩個(gè)結(jié)點(diǎn)，u與v之間的短程線(xiàn):u與v之間長(zhǎng)度最短的通路(設(shè)u與v連通)u與v之間的距離d(u,v):u與v之間短程線(xiàn)的長(zhǎng)度若u與v不連通,規(guī)定d(u,v)=∞.性質(zhì)：(1)

d(u,v)

0,且d(u,v)=0

u=v(2)d(u,v)=d(v,u)(3)d(u,v)+d(v,w)

d(u,w)

97例如a與e之間的短程線(xiàn):ace,afe.d(a,e)=2,d(a,h)=

abcdefghi通路的應(yīng)用六度分割理論電影演員合作圖中的貝肯數(shù)（bacon

number）論文合作關(guān)系圖中的埃德斯數(shù)(Erd?s

number)8.2.2連通的概念定義

若無(wú)向圖G中任意兩結(jié)點(diǎn)間都有一條通路(長(zhǎng)度

1)，則稱(chēng)G是連通圖；否則，稱(chēng)G是非連通圖。連通關(guān)系R={<u,v>|u,v

V且u與v連通}.R是等價(jià)關(guān)系連通分支:V關(guān)于R的等價(jià)類(lèi)的導(dǎo)出子圖設(shè)V/R={V1,V2,…,Vk},G的連通分支為G[V1],G[V2],…,G[Vk]連通分支數(shù)W(G)=kG是連通圖

W(G)=1

定理定理

設(shè)簡(jiǎn)單圖G=（V，E）有n個(gè)結(jié)點(diǎn)，e條邊，w個(gè)連通分支，則n-w

e。證明(用歸納法來(lái)證明)（1）當(dāng)e=0時(shí)，也就是對(duì)于n個(gè)結(jié)點(diǎn)的零圖，w=n，則n-w

e成立。（2）假定邊數(shù)為e-1的簡(jiǎn)單圖結(jié)論成立。對(duì)于邊數(shù)為e的簡(jiǎn)單圖G，從G中刪去一條邊，得到邊數(shù)為e-1的簡(jiǎn)單圖G'。分兩種情況分析：(a)刪去一條邊的圖G'的連通分支數(shù)沒(méi)有增加，即G'有n個(gè)結(jié)點(diǎn)，w個(gè)分支，e-1條邊，由歸納假設(shè)有n-w

e-1，所以n-w

e成立。(b)刪去一條邊的圖G'的連通分支數(shù)增加，即G'有n個(gè)結(jié)點(diǎn)，w+1個(gè)分支，e-1條邊，由歸納假設(shè)有n-(w+1)

e-1,所以n-w

e成立。點(diǎn)割集和邊割集定義

設(shè)無(wú)向圖G=(V,E),V

V,若W(G

V

)>W(G)且

V

V,W(G

V

)=W(G),則稱(chēng)V

為G的點(diǎn)割集.若{v}為點(diǎn)割集,則稱(chēng)v為割點(diǎn).設(shè)E

E,若W(G

E

)>W(G)且

E

E,W(G

E

)=W(G),則稱(chēng)E

為G的邊割集.若{e}為邊割集,則稱(chēng)e為割邊或橋.abcdefge1e2e3e4e5e6e7e8e9e,f點(diǎn)割集:{e},{f},割點(diǎn):{c,d}

橋:e8,e9邊割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}說(shuō)明102Kn無(wú)點(diǎn)割集n階零圖既無(wú)點(diǎn)割集，也無(wú)邊割集.若G連通，E

為邊割集，則W(G

E

)=2若G連通，V

為點(diǎn)割集，則W(G

V

)

2例題例

試證明2n個(gè)城市，如果每個(gè)城市至少可以和另外n個(gè)城市可以相互直航，那么這2n個(gè)城市中任何兩個(gè)之間可互相通航(有些可能要通過(guò)另外的城市中轉(zhuǎn))（即證明:2n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度數(shù)

n的簡(jiǎn)單圖是連通的。）證明

設(shè)有2n個(gè)結(jié)點(diǎn)的圖G不連通，則G中至少包含兩個(gè)連通分支,而且必有一個(gè)分支的結(jié)點(diǎn)數(shù)

n，即使這個(gè)分支是完全圖，其每個(gè)結(jié)點(diǎn)的度數(shù)d(v)

n-1，和d(v)

n矛盾。所以圖G只有一個(gè)連通分支，G是連通的。有向圖的連通性及其分類(lèi)定義

設(shè)G=（V，E）是一個(gè)有向圖，對(duì)G中任意兩個(gè)結(jié)點(diǎn)u和v，若從u到v存在通路，則稱(chēng)由u到v是可達(dá)的，否則稱(chēng)由u到v是不可達(dá)的。若從u到v存在通路，且從v到u存在通路，則稱(chēng)u和v是相互可達(dá)的。規(guī)定一個(gè)結(jié)點(diǎn)到自己總是可達(dá)的。有向圖的結(jié)點(diǎn)之間的可達(dá)關(guān)系具有自反性和傳遞性，不具有對(duì)稱(chēng)性。104有向連通圖定義

設(shè)G=（V，E）是有向圖。如果圖G的任意兩個(gè)結(jié)點(diǎn)間至少?gòu)囊粋€(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱(chēng)G是單向連通的。如果圖G的任意兩個(gè)結(jié)點(diǎn)間是互相可達(dá)的，則稱(chēng)G是強(qiáng)連通的。如果圖G在略去有向邊的方向后得到的無(wú)向圖是連通的，則稱(chēng)G是弱連通的。具有三種連通性中的任何一種的有向圖都稱(chēng)為有向連通圖。實(shí)例106

強(qiáng)連通單連通弱連通頂點(diǎn)集上的互相可達(dá)關(guān)系對(duì)于u，v

V，u與v有關(guān)系，當(dāng)且僅當(dāng)從u可達(dá)v，并且從v可達(dá)u。頂點(diǎn)集上的互相可達(dá)關(guān)系是等價(jià)關(guān)系。利用互相可達(dá)關(guān)系可將頂點(diǎn)集V劃分為V1，V2，…,Vw,每個(gè)Vi的任兩個(gè)頂點(diǎn)都是互相可達(dá)的.所以每個(gè)Vi導(dǎo)出的子圖Gi是強(qiáng)連通的,稱(chēng)為G的一個(gè)強(qiáng)分圖.頂點(diǎn)集上的互相可達(dá)關(guān)系有向圖的強(qiáng)連通分支.GG(V1)G(V2)G(V3)V1={v1,v7}V2={v2,v3,v5,v6}V3={v4}注意:有向圖中不一定每條邊都一定屬于一個(gè)強(qiáng)連通分支.而無(wú)向圖中每條邊必屬于一個(gè)連通分支.有向圖中每個(gè)頂點(diǎn)必屬于一個(gè)強(qiáng)連通分支.定理7.2.4：有向圖G是強(qiáng)連通的當(dāng)且僅當(dāng)G中存在經(jīng)過(guò)每個(gè)結(jié)點(diǎn)的回路。有向圖的應(yīng)用資源分配圖是有向圖：G=（V，E）,其中V是頂點(diǎn)的集合，E是邊的集合。頂點(diǎn)集合分為兩部分：（1）P={P1,P2,…Pn},它由進(jìn)程集合的所有活動(dòng)進(jìn)程組成。（2）

R={r1,r2,…rm},它由進(jìn)程集合所涉及的全部資源類(lèi)型組成。邊集合分為以下兩種：（1）申請(qǐng)邊(Pi，rj),表示進(jìn)程Pi申請(qǐng)一個(gè)單位的rj資源，但當(dāng)前Pi在等待該資源。（2）賦給邊(rj，Pi),表示有一個(gè)單位的rj資源已分配給進(jìn)程Pi。資源分配圖（1）G1(2)G2圖G1中有一個(gè)回路，所以是死鎖狀態(tài)。圖G2也有一個(gè)回路：P1r1P3r2P1，然而沒(méi)有出現(xiàn)死鎖。因?yàn)檫M(jìn)程P2和P4能釋放占有的資源r1和r2,然后就可以將r1和r2分給P1和P3,這樣環(huán)路就打開(kāi)了。資源分配圖中存在回路是死鎖存在的必要條件，但不是充分條件。P1P3．．r2r1r1P1P2P3P4．．．．r28.3圖的表示8.3.1鄰接表8.3.2鄰接矩陣8.3.3可達(dá)矩陣8.3.4關(guān)聯(lián)矩陣111定義

列出圖的每一個(gè)結(jié)點(diǎn)和它的所有鄰接結(jié)點(diǎn)的表稱(chēng)為鄰接表。例1

用鄰接表表示無(wú)向簡(jiǎn)單圖。例2

用鄰接表表示有向簡(jiǎn)單圖。1128.3.1鄰接表無(wú)向簡(jiǎn)單圖的鄰接表結(jié)點(diǎn)鄰接結(jié)點(diǎn)ab,cba,c,dca,b,d,edb,cec有向圖的鄰接表起點(diǎn)終點(diǎn)abbc,dca,b,d,edeb,c8.3.2鄰接矩陣定義

設(shè)圖G=（V，E）是有向圖，V={v1，v2，

，vn}，G的鄰接矩陣為，其中例題114A=1100001010001020v1v2v3v4有向圖中的通路數(shù)與回路數(shù)定理

設(shè)A是有向圖G=（V，E）的鄰接矩陣，V={v1，v2，

，vn}，

，則

表示G中從vi到vj的長(zhǎng)度為k的所有有向路的數(shù)目，其中

是從vi到自身的長(zhǎng)度為k的所有回路的數(shù)目。證明

用歸納法證明，對(duì)k作歸納。當(dāng)k=1時(shí)，由鄰接矩陣的定義知結(jié)論成立。設(shè)k=m時(shí)，結(jié)論成立。當(dāng)k=m+1時(shí)，有

，從而

。顯然

等于從vi出發(fā)經(jīng)vp到vj的長(zhǎng)度為m+1的有向路的數(shù)目。由于p的任意性

等于G中從vi到vj的長(zhǎng)度為m+1的所有有向路的數(shù)目。115有向圖中的通路數(shù)與回路數(shù)(續(xù))推論設(shè)矩陣

則Bl中的元素表示圖G中從結(jié)點(diǎn)vi到vj的長(zhǎng)度小于等于l的所有通路的總數(shù)。其中bii(l)是從vi到自身的長(zhǎng)度小于等于l的所有回路的總數(shù)目。116實(shí)例(續(xù))

117A=1100001010001020A2=1110100011003100A3=2110110011003310A4=3210110021104310v1到v2長(zhǎng)為3的通路有1條v1到v3長(zhǎng)為3的通路有1條v1到自身長(zhǎng)為4的回路有3條D中長(zhǎng)為3的通路共有15條,其中回路3條v1v2v3v4無(wú)向圖的鄰接矩陣定義

設(shè)圖G=（V，E）是無(wú)向圖，V={v1，v2，

，vn}，G的鄰接矩陣為，其中例3

寫(xiě)出如下圖所示的無(wú)向圖G的鄰接矩陣。解

鄰接矩陣為例題例4

畫(huà)出給定的鄰接矩陣所表示的圖。（1）（2）

（a）（b）abcabc(c)v1v2v4v3解

（1）鄰接矩陣（1）所表示的圖可以是無(wú)向圖（a）或有向圖（b）。

（2）鄰接矩陣（2）所表示的圖見(jiàn)圖（c)。例題例5判定下面的鄰接矩陣A所表示的圖G是否強(qiáng)連通圖？解因?yàn)锽3中存在為0的元素，所以圖G不是強(qiáng)連通圖。v1v2v3例題例6

判斷下面的兩個(gè)圖是否同構(gòu)？解兩個(gè)圖的鄰接矩陣為：

將矩陣A2的第2行元素和第3行元素交換，得到矩陣

，然后將矩陣

的第2列元素和第3列元素交換，得到矩陣

。

矩陣

和矩陣

相同，所以?xún)蓚€(gè)圖同構(gòu)。8.3.3可達(dá)矩陣定義

設(shè)圖G=（V，E）是有向圖，V={v1，v2，

，vn}，A是G的鄰接矩陣，

G的可達(dá)矩陣為

，

i，j=1,2，…，n,其中例題

寫(xiě)出右圖的可達(dá)矩陣。解

所以可達(dá)矩陣為由可達(dá)矩陣求強(qiáng)連通分支對(duì)可達(dá)矩陣P求轉(zhuǎn)置PT，PT中的(i,j)的元素為

，定義一個(gè)矩陣P∧PT，使得它的(i,j)的元素為

，于是矩陣P∧PT的第i行的“1”對(duì)應(yīng)的結(jié)點(diǎn)組成一個(gè)含有結(jié)點(diǎn)vi的強(qiáng)連通分支。矩陣P∧PT的第2行的兩個(gè)“1”表明結(jié)點(diǎn)v2和v3是一個(gè)強(qiáng)連通分支。125則稱(chēng)(mij)n

m為G的關(guān)聯(lián)矩陣,記為M(G).定義

設(shè)圖G=(V,E)是無(wú)環(huán)的有向圖,V={v1,v2,…,vn},E={e1,e2,…,em}.令8.3.4關(guān)聯(lián)矩陣?yán)}126ej與ek是平行邊

第j列與第k列相同孤立點(diǎn)對(duì)應(yīng)的行全為0(2)第i行1的個(gè)數(shù)等于d+(v),第i行-1的個(gè)數(shù)等于d-(v)性質(zhì):(1)每列恰好有一個(gè)1和一個(gè)-1定義

設(shè)圖G=(V,E)是無(wú)向圖，V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij為vi與ej的關(guān)聯(lián)次數(shù),稱(chēng)(mij)n

m為G的關(guān)聯(lián)矩陣,記為M(G).mij的可能取值為:0,1,2127例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2110000101110000110000000011008.3.4關(guān)聯(lián)矩陣同一個(gè)圖當(dāng)結(jié)點(diǎn)或邊的邊序不同時(shí),其對(duì)應(yīng)的A(G)有行序、列序的差別。性質(zhì)128(6)ej是環(huán)

第j列的一個(gè)元素為2,其余為0(5)vi是孤立點(diǎn)

第i行全為0例題

畫(huà)出下面的關(guān)聯(lián)矩陣M(G)表示的圖G。解

關(guān)聯(lián)矩陣M(G)表示的圖G如下圖。例題判斷下面兩個(gè)關(guān)聯(lián)矩陣表示的圖是否同構(gòu)？答案：是e1e2e3v1v2v3e1e2e3v3v1v2例題三枚錢(qián)幣處于反、正、反面，每次只許翻動(dòng)一枚錢(qián)幣，問(wèn)連續(xù)翻動(dòng)三次后，能否出現(xiàn)全正面或全反面。例題（續(xù)）解

引入一個(gè)三元組(q0,q1,q2)來(lái)描述錢(qián)幣的狀態(tài)，錢(qián)幣正面為0，反面為1，全部可能的狀態(tài)為：Q0=(0,0,0)；Q1=(0,0,1)；Q2=(0,1,0)；Q3=(0,1,1)；Q4=(1,0,0)；Q5=(1,0,1)；Q6=(1,1,0)；Q7=(1,1,1)。三枚錢(qián)幣的初始狀態(tài)是Q5，目標(biāo)狀態(tài)是Q0和Q7。是否可以翻動(dòng)3次后從Q5到Q0或Q7的問(wèn)題轉(zhuǎn)化為在下圖中是否存在從結(jié)點(diǎn)Q5到Q0或Q7的長(zhǎng)度為3的通路。例題（續(xù)）用鄰接矩陣表示圖

：例題（續(xù)）求A的3次冪從矩陣A3可知a61=0,a68=7,即Q5到Q0沒(méi)有長(zhǎng)度為3的通路，Q5到Q7有7條長(zhǎng)度為3的通路。所以，連續(xù)翻動(dòng)錢(qián)幣三次，不能出現(xiàn)全正面，可以出現(xiàn)全反面，有7種翻動(dòng)方法可以出現(xiàn)全反面。a:把錢(qián)幣q0翻轉(zhuǎn)一次

b:把錢(qián)幣q1翻轉(zhuǎn)一次

c:把錢(qián)幣q2翻轉(zhuǎn)一次aabababaabbbbcccbcccb

圖的運(yùn)算定義7.4.1設(shè)G1=（V1，E1）和G2=(V2，E2)是兩個(gè)簡(jiǎn)單圖，G1和G2的并圖是以E1

E2為邊集的圖，以E1

E2中的邊關(guān)聯(lián)的結(jié)點(diǎn)的集合為結(jié)點(diǎn)集的圖，可表示成G1

G2。G1和G2的交圖是以E1

E2為邊集，以E1

E2中的邊關(guān)聯(lián)的結(jié)點(diǎn)的集合為結(jié)點(diǎn)集的圖，可表示成G1

G2。G1和G2的差圖是以E1

E2為邊集，以E1

E2中的邊關(guān)聯(lián)的結(jié)點(diǎn)的集合為結(jié)點(diǎn)集的圖，可表示成G1

G2。G1和G2的環(huán)和圖是以E1

E2為邊集，以E1

E2中的邊關(guān)聯(lián)的結(jié)點(diǎn)的集合為結(jié)點(diǎn)集的圖，可表示成G1

G2。

兩個(gè)圖的環(huán)和可以用并、交、差給出：G1

G2=(G1

G2)

(G1

G2)。定義

設(shè)G1=（V1，E1）和G2=(V2，E2)是兩個(gè)圖，若V1

V2=

，則稱(chēng)G1和G2是不交的；若E1

E2=

，則稱(chēng)G1和G2是邊不交的，或邊不重的。

當(dāng)G1和G2是邊不交時(shí)，G1

G2=

，G1

G2=

G1，G2

G1=

G2，G1

G2=(G1

G2)。8.4獨(dú)立集、覆蓋和支配集獨(dú)立集定義：設(shè)G=（V，E）是無(wú)向圖簡(jiǎn)單圖，V的一個(gè)子集U中，任兩個(gè)結(jié)點(diǎn)不相鄰，則稱(chēng)U為G的一個(gè)點(diǎn)獨(dú)立集，簡(jiǎn)稱(chēng)獨(dú)立集。若圖G的一個(gè)獨(dú)立集，再加入任何結(jié)點(diǎn)都不是獨(dú)立集，則稱(chēng)為極大獨(dú)立集；結(jié)點(diǎn)數(shù)最多的獨(dú)立集稱(chēng)為最大獨(dú)立集；最大獨(dú)立集的結(jié)點(diǎn)數(shù)稱(chēng)為圖G的獨(dú)立數(shù)，記為α(G)。例題{a,e}和{b,d,f}是獨(dú)立集，也是極大獨(dú)立集，{b,d,f}是最大獨(dú)立集。可以看出，獨(dú)立集是導(dǎo)出子圖是零圖（沒(méi)有邊）的結(jié)點(diǎn)集?？占侨我鈭D的獨(dú)立集。覆蓋和覆蓋集定義

設(shè)G=（V，E）是無(wú)孤立點(diǎn)的無(wú)向圖簡(jiǎn)單圖，V的一個(gè)子集S，圖中每一條邊至少有一個(gè)結(jié)點(diǎn)在S中，稱(chēng)S為G的一個(gè)點(diǎn)覆蓋。若G的一個(gè)點(diǎn)覆蓋中去掉任一個(gè)結(jié)點(diǎn)后不再是點(diǎn)覆蓋，則稱(chēng)此點(diǎn)覆蓋為G的一個(gè)極小點(diǎn)覆蓋。結(jié)點(diǎn)數(shù)最少的點(diǎn)覆蓋，稱(chēng)為G的最小點(diǎn)覆蓋。最小點(diǎn)覆蓋S的元素個(gè)數(shù)稱(chēng)作圖G的點(diǎn)覆蓋數(shù)，記作

(G)。例題{b,c,d,f,g}和{a,c,e,g}是極小點(diǎn)覆蓋，{a,c,e,g}是最小點(diǎn)覆蓋在任一簡(jiǎn)單圖G=（V，E）中，V是點(diǎn)覆蓋。定理定理：

設(shè)圖G=（V，E）是無(wú)孤立點(diǎn)的無(wú)向簡(jiǎn)單圖，S是G的點(diǎn)覆蓋，當(dāng)且僅當(dāng)U=V-S是G的點(diǎn)獨(dú)立集。證明：

當(dāng)S是G的點(diǎn)覆蓋，假設(shè)U中有兩個(gè)結(jié)點(diǎn)u,v相鄰,則有邊(u,v)不被S所覆蓋，和S是點(diǎn)覆蓋矛盾，所以U中任兩個(gè)結(jié)點(diǎn)u,v不相鄰，U為點(diǎn)獨(dú)立集。當(dāng)U為點(diǎn)獨(dú)立集，假設(shè)圖G中存在邊e不關(guān)聯(lián)S中的結(jié)點(diǎn),則邊e的兩端點(diǎn)都在U中，即U中有兩個(gè)相鄰結(jié)點(diǎn)，和U為點(diǎn)獨(dú)立集矛盾，所以圖G中任一邊e關(guān)聯(lián)S中的結(jié)點(diǎn)，S是G的點(diǎn)覆蓋。例題{b,c,d,f,g}是點(diǎn)覆蓋，{a,e}是點(diǎn)獨(dú)立集。推論1推論1：設(shè)圖G=（V，E）中無(wú)孤立點(diǎn)的無(wú)向簡(jiǎn)單圖，S是G的極小點(diǎn)覆蓋，當(dāng)且僅當(dāng)U=V-S是G的極大點(diǎn)獨(dú)立集。證明：如果S是G的極小點(diǎn)覆蓋，但U=V–S不是G的極大點(diǎn)獨(dú)立集，則存在另一個(gè)點(diǎn)獨(dú)立集U，UU，由定理7.4.1知V–U是點(diǎn)覆蓋，而且S=V–UV–U，與S的極小性矛盾。類(lèi)似地可以證明，如果U=V-S是G的極大點(diǎn)獨(dú)立集，S是G的極小點(diǎn)覆蓋。推論2設(shè)圖G=（V，E）中無(wú)孤立點(diǎn)的簡(jiǎn)單圖，S是G的最小點(diǎn)覆蓋，當(dāng)且僅當(dāng)U=V-S是G的最大點(diǎn)獨(dú)立集，因而有

(G)+

(G)=|V|。證明：如果S是G的最小點(diǎn)覆蓋，而U=V–S不是G的最大點(diǎn)獨(dú)立集，則存在另一個(gè)最大點(diǎn)獨(dú)立集U

，U

U

，由定理8.4.1知V–U

是點(diǎn)覆蓋，而且|V–U

|=|V|–|U

|<