第7章

高級計數技術第7章高級計數技術7.1遞推方程7.2生成函數7.1遞推方程定義7.1.1設序列

簡記為

。序列

的遞推方程是一個把

an用序列中在an

前面的一項或多項

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

表示第

個月初的兔子對數，n是正整數。那么

f1=1（最初的兔子對數，第1個月的兔子對數）

f2=1（第2個月的兔子對數）f3=1+1=2（最初的一對加上它們的后代）

f4=2+1=3（第3個月的2對加上最初的一對的后代）f5=3+2=5（第4個月的3對加上第3個月2對的后代）

f6=5+3=8（第5個月的5對加上第4個月3對的后代）

f12=89+55=144（第11個月的89對加上第10個月55對的后代）12個月時島上共有兔子144對。一般的，斐波那契數列滿足下列遞推方程數列

稱作斐波那契數列，其中的每一個數也稱作斐波那契數。例題在股票投資中，復合利息的作用是強大的。“股神”沃倫·巴菲特(Warren

Buffett)據說就是以年平均30%的復利戰勝市場，從而成為舉世矚目的價值投資大師。假設他的初始投資為10000美元，年投資收益的復利是30%，那么在30年后賬上的總資產有多少錢？解

令Pn表示n年后的總資產錢數。因為n年后賬上的資產總額等于n-1年賬上的資產加上第n年的投資收益，容易知道序列{Pn}滿足遞推關系例題（續）初始條件是P0=10000，我們可以知道代入初始條件，得將n=30代入，

26199956.44美元。常系數線性齊次遞推方程的求解定義7.2.1設遞推方程滿足其中

為常數,,這個方程稱為k階常系數線性遞推方程。

為k個初值。當

時，即稱這個遞推方程為齊次方程。

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

等式兩邊同時除以rn-k，得

因此我們將形如方程

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

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

將

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

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

推論

若

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

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

是任意常數。以上推論說明

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

的表達式稱為該遞推方程的通解。定理定理7.2.2設

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

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

是任意常數。證明

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

，

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

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

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

定理定理7.2.3設

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

ri的重數為ei，其中

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

為常數。

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

特征方程

為即

特征根是2，其重數是3，根據定理7.2.3

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

原方程的解為例題（續）解得

原方程的解為常系數線性非齊次遞推方程的求解常系數線性非齊次遞推方程的標準形是

（7.3）其中

f(n)是只依賴于n的函數。將

稱作相伴的線性齊次遞推方程。定理7.2.4設

是對應的相伴的線性齊次遞推方程的通解，

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

該方程對應相伴的線性齊次遞推方程是

它的通解是c3n，其中c是常數。設特解

，其中c1,c2

是常數。代入遞推方程得例題（續）整理得從而得線性方程組解得

因此

是一個特解，根據定理7.2.4，原方程的通解為初始條件

帶入通解得,因此得原方程的通解為7.2生成函數生成函數是研究組合計數中的一個重要工具，其基本思想是把要計數或研究的離散數列同多項式或冪級數的系數一一對應起來，從而可以用數學分析的方法去研究這一數列，給出數列的一個顯示解或漸近解。牛頓二項式系數與牛頓二項式定理定義7.3.1設r為實數，n為整數，引入形式符號稱為牛頓二項式系數．定理定理7.3.1牛頓二項式定理．

設r為實數，則對一切實數

，有其中

生成函數的定義及其性質定義7.3.2設序列

，構造形式冪級數

稱f(x)為序列

的生成函數。

定義7.3.2給出的生成函數有時叫做

的普通生成函數，以和這個序列的其他類型的生成函數相區別，序列

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

。那么序列{ak}的生成函數是什么？解這個序列的生成函數是由二項式定理可得

生成函數的性質設

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

為常數，則

若

，則

若

，則

若

生成函數的性質(續）(5)若

，則

(6)若

，則(7)若

，且

收斂，則

(8)若

為常數，則

(9)若

，則

，其中

為A(x)的導數。(10)若

，則

例題生成函數與序列是一一對應的。例7.3.2求序列{an}的生成函數

解

例題已知{an}的生成函數為

，求an.

解

因此我們可以得到

生成函數的應用例7.3.4求解遞推方程

且初始條件

解

設序列

的生成函數為首先注意到例題（續）因為n>=1時有

且

所以有即得所以

指數型生成函數定義7.3.3

設{an}為序列，構造形式冪級數稱

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

。（1）

，m為正整數；（2）an=1；（3）an=bn

；解（1）

（2）

（3）定理定理7.3.2

設

為多重集，則S的r-排列數由指數生成函數的展開式中

的系數給出。例題例7.3.10由1，2，3，4組成的5位數中，要求1出現不超過2次，但不能不出現，2出現不超過1次，3出現至多2次，4出現偶數次，求這樣的5位數個數。解展開后

的

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

解問題是求多重集

的4-排列數，且要求排列的末尾為2。因為根據已知條件，只能有2為末尾才為偶數，所以可把問題轉換為求多重集

的3-排列數。其指數生成函數為展開后的

的系數為20，所以能組成20個四位數的偶數。第8章

圖論圖論研究圖的點和線的關系及特點，是研究離散結構及其特性的重要數學分支。現實世界中，許多事務都可以抽象成點及它們之間的聯系，都可以用圖來描述。如哥尼斯堡七橋問題、Internet網、社會關系網絡、交通運輸網、電路網絡等。第8章圖8.1圖的基本概念8.2通路與回路、連通的概念8.3圖的表示8.4獨立集、覆蓋和支配集39ABCD圖論起源公元十八世紀有這樣一個問題：在東普魯士有個哥尼斯堡城（

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

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

1736年，瑞士數學家L.Eluer（歐拉）在他發表的“哥尼斯堡七座橋”的著名文章中闡述了解決這個問題的觀點，從而被譽為圖論之父。

當時，城中的居民熱衷于這樣一個問題，從四塊陸地的任一塊出發，怎樣才能做到經過每座橋一次且僅一次，然后回到出發點。問題看來并不復雜，但當地的居民和游人做了不少的嘗試，卻都沒有取得成功。

Euler將四塊陸地表示成四個結點，凡陸地間有橋相連的，便在兩點間連一條邊。ABCDDCAB

此時，哥尼斯堡七橋問題歸結為：從A,B,C,D任一點出發，通過每條邊一次且僅一次而返回出發點的回通路是否存在？

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

理由是：從圖中的任一點出發，為了要回到原來的出發點，要求與每個點相關聯的邊數均為偶數。這樣才能保證從一條邊進入某點后，再從另一條邊出去，從一個點的不同的兩條邊一進一出才能回到出發點。而圖中的A,B,C,D全是與奇數條邊相連，由此可知所要求的回通路是不可能存在的。8.1圖的基本概念8.1.1無向圖和有向圖8.1.2度的概念8.1.3握手定理8.1.4圖的分類8.1.5子圖與補圖8.1.6

圖的同構44無向圖和有向圖定義一個無向圖可以表示為G=（V，E），其中V是非空有限結點集，稱V中的元素為結點或頂點；E是邊集，其中的元素是由V中的元素組成的無序對，稱E中的元素為邊。若（v，w）是無序對，則（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有向圖定義

一個有向圖可以表示為D=（V，E），其中V是非空有限結點集，稱V中的元素為結點或頂點；E是有向邊集，E中的元素是由V中的元素組成的有序對，稱E中的元素為有向邊。有向圖D=（V，E）。結點集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圖的術語定義

在無向圖中，如果關聯一對結點的邊多于一條，則稱這些邊為平行邊。如果有邊關聯于一對結點，則稱這對結點是鄰接的。一條邊的兩個端點如果關聯于同一個結點，則稱為環，和任何邊都不關聯的點稱為孤立點。邊e2和e3是平行邊，邊e1關聯結點v1和v3，則稱v1和v3是鄰接的，邊e5=（v3，v3）是環，v4是孤立點。圖的術語在有向圖中，如果關聯一對結點的方向相同的有向邊多于一條，則稱這些有向邊為多重有向邊或平行邊。如關聯于結點v1和v2的兩條有向邊是平行邊，而關聯于結點v3和v4的兩條有向邊方向相反，不是平行邊。（v1，v1）稱為環。對于有向邊（v2，v3），稱v2為起點，v3為終點，v2和v3是鄰接的。圖的術語n階圖:n個頂點的圖零圖:E=

的圖平凡圖:1階零圖在圖的定義中規定結點集合V為非空集，但在運算中可能產生結點集為空集的運算結果，因此規定結點集為空集的圖為空圖，記為

度的概念

定義

設G=<V,E>為無向圖,v

V,v所關聯的邊數稱為v的度數，簡稱度，記作d(v)。懸掛頂點:度數為1的頂點懸掛邊:與懸掛頂點關聯的邊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是懸掛頂點,e7是懸掛邊,e1是環50e1e2e3e4e5e6e7v5v1v2v3v4頂點的度數(續)定義

設D=<V,E>為有向圖,v

V,以v為起點所關聯的邊數稱為v的出度，記作d+(v)；以v為終點所關聯的邊數稱為v的入度，記作d

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

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

+(D),

+(D),

(D),

(D),

(D),

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

+=4,

+=0,

=3,

=1,

=5,

=351e1e2e3e4e5e6e7dabc握手定理定理

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

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

(v1),d

(v2),…,d

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

自然數序列(3，3，2，2，1)，(4，2，2，1，1)能作為圖的結點的度數序列嗎？為什么？

解

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

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

V

u與v有公共的棱u

v}.根據假設,|V|為奇數且v

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

圖的分類定義

設圖G=（V，E）為無向圖或有向圖，如果G中不含平行邊，也不含環，則稱為簡單圖。定義

設圖G=（V，E）為無向圖或有向圖，如果G中含有平行邊，則稱為多重圖。簡單圖多重圖多重圖簡單圖圖的應用1、航班路線圖有向多重圖2、微博關注圖有向簡單圖3、合作關系圖無向簡單圖或多重圖完全圖(1)定義

設G=（V，E）是n階無向簡單圖，若G中任何結點都與其余的n-1個結點相鄰，則稱G為n階無向完全圖，記作Kn。

完全圖頂點數n,邊數m=n(n-1)/2,(G)=(G)=n-1K3K5完全圖(2)設G=（V，E）為n階有向簡單圖，若對于V中任意的兩個結點u和v，既有有向邊(u，v)，又有有向邊(v，u)，則稱G是n階有向完全圖。

頂點數n,邊數m=n(n-1),

+(D)=

+(D)=

-(D)=

-(D)=n-1,

(D)=

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

例題例5判斷下列各非負整數列是否是簡單圖的結點度數序列？（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）根據握手定理的推論可知，不是圖的結點度數序列，因為有3個奇數。

（2）中有5個數，最大數是5，根據定理7.1.3，它不是簡單圖的結點序列。

（3）是簡單圖的結點序列。下圖的兩個無向簡單圖都是（3,3,2,2,1,1）為結點度數序列。

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

設G為n階無向簡單圖，若

v

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

K52正則圖4正則圖

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

。當k為奇數時，n為偶數。當k=0時，0-正則圖就是n階零圖。n階無向完全圖是(n-1)-正則圖。環圖和輪圖定義

如果圖G=（V，E）的結點集V={v1，v2，

vn}（n

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

（vn-1，vn），（vn，v1）}，則稱G為環圖，記為Cn。下圖是C3,C4,C5,C6。定義

當給環圖Cn-1（n

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

如果圖G=（V，E）有2n個結點，每個結點表示一個長度為n的位串，任何兩個相鄰的結點表示的位串只有一位不同，則稱G稱為n方體圖，記作Qn。690110110001010101100000111011001Q1Q2Q3方體圖對任意n

N

，Qn

是將兩個Qn-1

圖的對應結點連接起來的簡單圖.Q0

有1個結點.Q0Q1Q2Q3Q4結點數:2n.邊數：n2n-1二分圖定義

如果圖G=（V，E）的結點集V能劃分為兩個子集：V1和V2，使每條邊有一個端點在V1中,另一個端點在V2中，則稱該圖為二分圖（或二部圖）。定義

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

帶權圖定義7.1.17每個結點或每條邊都帶有數值的圖稱為帶權圖。

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

設圖G=（V，E）設e

E，從G圖中刪去邊e得到的圖表示為G-e,稱為刪除邊運算；設E1

E，從G圖中刪去E1的所有邊得到的圖表示為G-E1,稱為刪除邊集運算。設v

V，從G圖中刪去結點v及v關聯的所有邊得到的圖表示為G?v,稱為刪除結點運算；設V1

V，從G圖中刪去V1中所有結點及它們關聯的所有邊得到的圖表示為G?V1,稱為刪除結點集運算。設e=(u,v)

E，從G圖中刪去邊e,將e的兩個端點u、v用一個新的結點w代替，將u,v關聯的所有邊都關聯結點w，稱為邊e的收縮，記為G\e。設u,v

V，在u,v之間加一條邊（u,v），稱為加新邊，表示為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。子圖定義

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

V，且E1

E，則稱G1是G的子圖，G是G1的母圖，記作G1

G。若G1

G且G1

G(即V1

V,或E1

E)，則稱G1是G的真子圖。若G1

G且V1=V，則稱G1是G的生成子圖。對圖G=（V，E），設V1

V且V1

，以V1為結點集，以兩端點均在V1中的全體邊為邊集的G的子圖，稱G1為G的由結點集V1導出的子圖，記為G（V1）。對圖G=（V，E），設E1

E且E1

，以E1為邊集，以E1中邊關聯的結點的全體為結點集的G的子圖，稱G1為G的由邊集E1導出的子圖，記為G（E1）。例題(1),(2),(3)是(1)的子圖,(2),(3)是真子圖,(1)是母圖.(1),(3)是(1)的生成子圖.(2)是{d,e,f}的導出子圖,也是{e5,e6,e7}導出子圖.(3)是{e1,

e3,

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

V，且E1

E，則稱G1是G的子圖，G是G1的母圖，記作G1

G。若G1

G且G1

G(即V1

V,或E1

E)，則稱G1是G的真子圖。若G1

G且V1=V，則稱G1是G的生成子圖。對圖G=（V，E），設V1

V且V1

，以V1為結點集，以兩端點均在V1中的全體邊為邊集的G的子圖，稱G1為G的由結點集V1導出的子圖，記為G（V1）。對圖G=（V，E），設E1

E且E1

，以E1為邊集，以E1中邊關聯的結點的全體為結點集的G的子圖，稱G1為G的由邊集E1導出的子圖，記為G（E1）。補圖定義

設G=(V，E)是n階無向簡單圖或有向簡單圖。以V為結點，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱為G相對于完全圖的補圖，簡稱G的補圖，記作~G。

補圖定義

設G=(V，E)是n階無向簡單圖或有向簡單圖。以V為結點，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱為G相對于完全圖的補圖，簡稱G的補圖，記作~G。

補圖定義

設G=(V，E)是n階無向簡單圖或有向簡單圖。以V為結點，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱為G相對于完全圖的補圖，簡稱G的補圖，記作~G。

G1~G1

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

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

V，(u，v)

E,當且僅當(f(u)，f(v))

E'；如果在u，v間存在平行邊，則關聯于結點u，v的平行邊數與關聯于結點f(u)，f(v)的平行邊數相同，則稱G與G'是同構的，記作G

G'。a

v1，b

v5，c

v3，d

v2，e

v4判斷兩個圖同構的必要條件1)必須具有相同的頂點數；2)必須具有相同的邊數；3)度數相同的結點數相等。（對應頂點的度數相同.）4)相同長度的回路數相同。

判斷兩個圖同構的必要條件不同構的圖例題例6畫出4階3條邊的所有非同構的無向簡單圖解總度數為6,分配給4個頂點,最大度為3,且奇度頂點數為偶數,有下述3個度數列:(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畫出3個以1,1,1,2,2,3為度數列的非同構的無向簡單圖85自互補圖定義

如果一個圖同構于它的補圖,則稱此圖為自互補圖。例8

試證明：一個圖為自互補圖，其對應的完全圖的邊數必為偶數。證明

設G為自互補圖，G有e條邊，并設G對應的完全圖的邊數為m，則G的補圖的邊數為m?e。對于自互補圖G，有G

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

是偶數。

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

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

n）。

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

v2e1v1e10v6是簡單通路，v2e4v4e5v5e6

v2e1v1e10v6e9v2是簡單回路，v3e3v4e5v5e6v2e1v1e10v6是基本通路，v2e1v1e10v6e7v5e6

v2

是基本回路或圈。例題v1e2v2e5v4e4v3是從結點v1到v3的長度為3的通路，v1e2v2e5v4e6v2是簡單通路，v1e2v2e5v4e4v3

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

=v0e1v1e2…elvl②用邊序列,

=e1e2…el③簡單圖中,用頂點序列,

=v0v1…vl(2)在無向圖中,長度為1的圈由環構成.長度為2的圈由兩條平行邊構成.在無向簡單圖中,所有圈的長度

3.在有向圖中,長度為1的圈由環構成.在有向簡單圖中,所有圈的長度

2.92說明(續)(3)初級通路(回路)是簡單通路(回路),但反之不真93初級通路非初級的簡單通路初級回路非初級的簡單回路定理定理

在n階圖G中，若從結點u到v（u

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

設ue1v1e2v2…ekv為G中從u到v的長度為k的通路，通路上有k+1個結點。若通路長度k

n-1，則定理成立。若k>n-1，該通路上的結點數大于G的結點數n，根據鴿巢原理，必有一個結點在通路上出現兩次，即存在t，s，0

t

s

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

在n階圖G中，若從結點u到v（u

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

n

1.若有相同的頂點,刪去這兩個頂點之間的這一段,仍是u到v的通路.重復進行,直到沒有相同的頂點為止.定理定理

在n階圖G中，若從結點u到自身存在回路，則回路的長度小于或等于n。推論

在n階圖G中，若從結點u到自身存在回路，則一定存在從結點u到自身的長度小于或等于n的基本回路。短程線與距離設u,v為圖G中任意兩個結點，u與v之間的短程線:u與v之間長度最短的通路(設u與v連通)u與v之間的距離d(u,v):u與v之間短程線的長度若u與v不連通,規定d(u,v)=∞.性質：(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之間的短程線:ace,afe.d(a,e)=2,d(a,h)=

abcdefghi通路的應用六度分割理論電影演員合作圖中的貝肯數（bacon

number）論文合作關系圖中的埃德斯數(Erd?s

number)8.2.2連通的概念定義

若無向圖G中任意兩結點間都有一條通路(長度

1)，則稱G是連通圖；否則，稱G是非連通圖。連通關系R={<u,v>|u,v

V且u與v連通}.R是等價關系連通分支:V關于R的等價類的導出子圖設V/R={V1,V2,…,Vk},G的連通分支為G[V1],G[V2],…,G[Vk]連通分支數W(G)=kG是連通圖

W(G)=1

定理定理

設簡單圖G=（V，E）有n個結點，e條邊，w個連通分支，則n-w

e。證明(用歸納法來證明)（1）當e=0時，也就是對于n個結點的零圖，w=n，則n-w

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

e-1，所以n-w

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

e-1,所以n-w

e成立。點割集和邊割集定義

設無向圖G=(V,E),V

V,若W(G

V

)>W(G)且

V

V,W(G

V

)=W(G),則稱V

為G的點割集.若{v}為點割集,則稱v為割點.設E

E,若W(G

E

)>W(G)且

E

E,W(G

E

)=W(G),則稱E

為G的邊割集.若{e}為邊割集,則稱e為割邊或橋.abcdefge1e2e3e4e5e6e7e8e9e,f點割集:{e},{f},割點:{c,d}

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

為邊割集，則W(G

E

)=2若G連通，V

為點割集，則W(G

V

)

2例題例

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

n的簡單圖是連通的。）證明

設有2n個結點的圖G不連通，則G中至少包含兩個連通分支,而且必有一個分支的結點數

n，即使這個分支是完全圖，其每個結點的度數d(v)

n-1，和d(v)

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

設G=（V，E）是一個有向圖，對G中任意兩個結點u和v，若從u到v存在通路，則稱由u到v是可達的，否則稱由u到v是不可達的。若從u到v存在通路，且從v到u存在通路，則稱u和v是相互可達的。規定一個結點到自己總是可達的。有向圖的結點之間的可達關系具有自反性和傳遞性，不具有對稱性。104有向連通圖定義

設G=（V，E）是有向圖。如果圖G的任意兩個結點間至少從一個結點到另一個結點是可達的，則稱G是單向連通的。如果圖G的任意兩個結點間是互相可達的，則稱G是強連通的。如果圖G在略去有向邊的方向后得到的無向圖是連通的，則稱G是弱連通的。具有三種連通性中的任何一種的有向圖都稱為有向連通圖。實例106

強連通單連通弱連通頂點集上的互相可達關系對于u，v

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

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

列出圖的每一個結點和它的所有鄰接結點的表稱為鄰接表。例1

用鄰接表表示無向簡單圖。例2

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

設圖G=（V，E）是有向圖，V={v1，v2，

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

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

，vn}，

，則

表示G中從vi到vj的長度為k的所有有向路的數目，其中

是從vi到自身的長度為k的所有回路的數目。證明

用歸納法證明，對k作歸納。當k=1時，由鄰接矩陣的定義知結論成立。設k=m時，結論成立。當k=m+1時，有

，從而

。顯然

等于從vi出發經vp到vj的長度為m+1的有向路的數目。由于p的任意性

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

則Bl中的元素表示圖G中從結點vi到vj的長度小于等于l的所有通路的總數。其中bii(l)是從vi到自身的長度小于等于l的所有回路的總數目。116實例(續)

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

設圖G=（V，E）是無向圖，V={v1，v2，

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

寫出如下圖所示的無向圖G的鄰接矩陣。解

鄰接矩陣為例題例4

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

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

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

（2）鄰接矩陣（2）所表示的圖見圖（c)。例題例5判定下面的鄰接矩陣A所表示的圖G是否強連通圖？解因為B3中存在為0的元素，所以圖G不是強連通圖。v1v2v3例題例6

判斷下面的兩個圖是否同構？解兩個圖的鄰接矩陣為：

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

，然后將矩陣

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

。

矩陣

和矩陣

相同，所以兩個圖同構。8.3.3可達矩陣定義

設圖G=（V，E）是有向圖，V={v1，v2，

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

G的可達矩陣為

，

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

寫出右圖的可達矩陣。解

所以可達矩陣為由可達矩陣求強連通分支對可達矩陣P求轉置PT，PT中的(i,j)的元素為

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

，于是矩陣P∧PT的第i行的“1”對應的結點組成一個含有結點vi的強連通分支。矩陣P∧PT的第2行的兩個“1”表明結點v2和v3是一個強連通分支。125則稱(mij)n

m為G的關聯矩陣,記為M(G).定義

設圖G=(V,E)是無環的有向圖,V={v1,v2,…,vn},E={e1,e2,…,em}.令8.3.4關聯矩陣例題126ej與ek是平行邊

第j列與第k列相同孤立點對應的行全為0(2)第i行1的個數等于d+(v),第i行-1的個數等于d-(v)性質:(1)每列恰好有一個1和一個-1定義

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

令mij為vi與ej的關聯次數,稱(mij)n

m為G的關聯矩陣,記為M(G).mij的可能取值為:0,1,2127例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2110000101110000110000000011008.3.4關聯矩陣同一個圖當結點或邊的邊序不同時,其對應的A(G)有行序、列序的差別。性質128(6)ej是環

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

第i行全為0例題

畫出下面的關聯矩陣M(G)表示的圖G。解

關聯矩陣M(G)表示的圖G如下圖。例題判斷下面兩個關聯矩陣表示的圖是否同構？答案：是e1e2e3v1v2v3e1e2e3v3v1v2例題三枚錢幣處于反、正、反面，每次只許翻動一枚錢幣，問連續翻動三次后，能否出現全正面或全反面。例題（續）解

引入一個三元組(q0,q1,q2)來描述錢幣的狀態，錢幣正面為0，反面為1，全部可能的狀態為：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)。三枚錢幣的初始狀態是Q5，目標狀態是Q0和Q7。是否可以翻動3次后從Q5到Q0或Q7的問題轉化為在下圖中是否存在從結點Q5到Q0或Q7的長度為3的通路。例題（續）用鄰接矩陣表示圖

：例題（續）求A的3次冪從矩陣A3可知a61=0,a68=7,即Q5到Q0沒有長度為3的通路，Q5到Q7有7條長度為3的通路。所以，連續翻動錢幣三次，不能出現全正面，可以出現全反面，有7種翻動方法可以出現全反面。a:把錢幣q0翻轉一次

b:把錢幣q1翻轉一次

c:把錢幣q2翻轉一次aabababaabbbbcccbcccb

圖的運算定義7.4.1設G1=（V1，E1）和G2=(V2，E2)是兩個簡單圖，G1和G2的并圖是以E1

E2為邊集的圖，以E1

E2中的邊關聯的結點的集合為結點集的圖，可表示成G1

G2。G1和G2的交圖是以E1

E2為邊集，以E1

E2中的邊關聯的結點的集合為結點集的圖，可表示成G1

G2。G1和G2的差圖是以E1

E2為邊集，以E1

E2中的邊關聯的結點的集合為結點集的圖，可表示成G1

G2。G1和G2的環和圖是以E1

E2為邊集，以E1

E2中的邊關聯的結點的集合為結點集的圖，可表示成G1

G2。

兩個圖的環和可以用并、交、差給出：G1

G2=(G1

G2)

(G1

G2)。定義

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

V2=

，則稱G1和G2是不交的；若E1

E2=

，則稱G1和G2是邊不交的，或邊不重的。

當G1和G2是邊不交時，G1

G2=

，G1

G2=

G1，G2

G1=

G2，G1

G2=(G1

G2)。8.4獨立集、覆蓋和支配集獨立集定義：設G=（V，E）是無向圖簡單圖，V的一個子集U中，任兩個結點不相鄰，則稱U為G的一個點獨立集，簡稱獨立集。若圖G的一個獨立集，再加入任何結點都不是獨立集，則稱為極大獨立集；結點數最多的獨立集稱為最大獨立集；最大獨立集的結點數稱為圖G的獨立數，記為α(G)。例題{a,e}和{b,d,f}是獨立集，也是極大獨立集，{b,d,f}是最大獨立集。可以看出，獨立集是導出子圖是零圖（沒有邊）的結點集。空集是任意圖的獨立集。覆蓋和覆蓋集定義

設G=（V，E）是無孤立點的無向圖簡單圖，V的一個子集S，圖中每一條邊至少有一個結點在S中，稱S為G的一個點覆蓋。若G的一個點覆蓋中去掉任一個結點后不再是點覆蓋，則稱此點覆蓋為G的一個極小點覆蓋。結點數最少的點覆蓋，稱為G的最小點覆蓋。最小點覆蓋S的元素個數稱作圖G的點覆蓋數，記作

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

設圖G=（V，E）是無孤立點的無向簡單圖，S是G的點覆蓋，當且僅當U=V-S是G的點獨立集。證明：

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

(G)+

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

，U

U

，由定理8.4.1知V–U

是點覆蓋，而且|V–U

|=|V|–|U

|<