離散數(shù)學(xué)及其應(yīng)用-第2版 課件 第8章圖論

第8章

圖論圖論研究圖的點(diǎ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ú)立集、覆蓋和支配集3ABCD圖論起源公元十八世紀(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)題的觀點(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圖的分類8.1.5子圖與補(bǔ)圖8.1.6

圖的同構(gòu)8無(wú)向圖和有向圖定義一個(gè)無(wú)向圖可以表示為G=（V，E），其中V是非空有限結(jié)點(diǎn)集，稱V中的元素為結(jié)點(diǎn)或頂點(diǎn)；E是邊集，其中的元素是由V中的元素組成的無(wú)序?qū)ΓQE中的元素為邊。若（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)}9e1e2e3e4e5e6e7v5v1v2v3v4有向圖定義

一個(gè)有向圖可以表示為D=（V，E），其中V是非空有限結(jié)點(diǎn)集，稱V中的元素為結(jié)點(diǎn)或頂點(diǎn)；E是有向邊集，E中的元素是由V中的元素組成的有序?qū)?，稱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>10圖的術(shù)語(yǔ)定義

在無(wú)向圖中，如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的邊多于一條，則稱這些邊為平行邊。如果有邊關(guān)聯(lián)于一對(duì)結(jié)點(diǎn)，則稱這對(duì)結(jié)點(diǎn)是鄰接的。一條邊的兩個(gè)端點(diǎn)如果關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)，則稱為環(huán)，和任何邊都不關(guān)聯(lián)的點(diǎn)稱為孤立點(diǎn)。邊e2和e3是平行邊，邊e1關(guān)聯(lián)結(jié)點(diǎn)v1和v3，則稱v1和v3是鄰接的，邊e5=（v3，v3）是環(huán)，v4是孤立點(diǎn)。圖的術(shù)語(yǔ)在有向圖中，如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的方向相同的有向邊多于一條，則稱這些有向邊為多重有向邊或平行邊。如關(guān)聯(lián)于結(jié)點(diǎn)v1和v2的兩條有向邊是平行邊，而關(guān)聯(lián)于結(jié)點(diǎn)v3和v4的兩條有向邊方向相反，不是平行邊。（v1，v1）稱為環(huán)。對(duì)于有向邊（v2，v3），稱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ù)稱為v的度數(shù)，簡(jiǎn)稱度，記作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)14e1e2e3e4e5e6e7v5v1v2v3v4頂點(diǎn)的度數(shù)(續(xù))定義

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

V,以v為起點(diǎn)所關(guān)聯(lián)的邊數(shù)稱為v的出度，記作d+(v)；以v為終點(diǎn)所關(guān)聯(lián)的邊數(shù)稱為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,

=315e1e2e3e4e5e6e7dabc握手定理定理

設(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ù)。16定理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)集，稱(d(v1),d(v2),…,d(vn))為G的度數(shù)序列。一個(gè)由非負(fù)整數(shù)構(gòu)成的序列d=（d1,d2,…,dn）,如d恰好是一個(gè)圖的所有結(jié)點(diǎn)度數(shù)序列，稱這個(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,219e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc例題例

自然數(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í)例21例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ù)條棱的多面體.22證用反證法.假設(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ù).這與握手定理的推論矛盾.

圖的分類定義

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

設(shè)圖G=（V，E）為無(wú)向圖或有向圖，如果G中含有平行邊，則稱為多重圖。簡(jiǎn)單圖多重圖多重圖簡(jiǎn)單圖圖的應(yīng)用1、航班路線圖有向多重圖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)相鄰，則稱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)，則稱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,則稱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）}，則稱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。33定義

如果圖G=（V，E）有2n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)表示一個(gè)長(zhǎng)度為n的位串，任何兩個(gè)相鄰的結(jié)點(diǎn)表示的位串只有一位不同，則稱G稱為n方體圖，記作Qn。方體圖0110110001010101100000111011001Q1Q2Q3方體圖對(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中，則稱該圖為二分圖（或二部圖）。定義

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

帶權(quán)圖定義7.1.17每個(gè)結(jié)點(diǎn)或每條邊都帶有數(shù)值的圖稱為帶權(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,稱為刪除邊運(yùn)算；設(shè)E1

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

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

V，從G圖中刪去V1中所有結(jié)點(diǎn)及它們關(guān)聯(lián)的所有邊得到的圖表示為G?V1,稱為刪除結(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，稱為邊e的收縮，記為G\e。設(shè)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。子圖定義

設(shè)G=（V，E）和G1=(V1，E1)是兩個(gè)圖。若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的生成子圖。對(duì)圖G=（V，E），設(shè)V1

V且V1

，以V1為結(jié)點(diǎn)集，以兩端點(diǎn)均在V1中的全體邊為邊集的G的子圖，稱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的子圖，稱G1為G的由邊集E1導(dǎo)出的子圖，記為G（E1）。40例題(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)出子圖aabbccdddeeefffe1e1e2e3e3e4e5e5e5e6e6e7e7e7(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的生成子圖。對(duì)圖G=（V，E），設(shè)V1

V且V1

，以V1為結(jié)點(diǎn)集，以兩端點(diǎn)均在V1中的全體邊為邊集的G的子圖，稱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的子圖，稱G1為G的由邊集E1導(dǎo)出的子圖，記為G（E1）。補(bǔ)圖定義

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

補(bǔ)圖定義

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

補(bǔ)圖定義

設(shè)G=(V，E)是n階無(wú)向簡(jiǎn)單圖或有向簡(jiǎn)單圖。以V為結(jié)點(diǎn)，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱為G相對(duì)于完全圖的補(bǔ)圖，簡(jiǎn)稱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ù)相同，則稱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.481,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)單圖49自互補(bǔ)圖定義

如果一個(gè)圖同構(gòu)于它的補(bǔ)圖,則稱此圖為自互補(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連通的概念5152定義7.2.1給定圖G=（V，E）中，以v0為起點(diǎn)，vn為終點(diǎn)的由結(jié)點(diǎn)和邊交替出現(xiàn)的序列v0e1v1e2v2…vn-1envn稱為從結(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）。

7.2.1通路與回路通路與回路若一條通路的起點(diǎn)和終點(diǎn)是同一點(diǎn)，稱它是一條回路。若通路中的所有邊互不相同，則稱它為簡(jiǎn)單通路或跡。若回路中的所有邊互不相同，則稱它為簡(jiǎn)單回路或閉跡。若通路中的所有結(jié)點(diǎn)互不相同，所有邊互不相同，則稱它為基本通路或初級(jí)通路、路徑。若回路中的所有結(jié)點(diǎn)互不相同，所有邊互不相同，則稱它為基本回路或初級(jí)回路、圈。一條通路或回路包含的邊的數(shù)目稱為通路或回路的長(zhǎng)度。如果一條回路的長(zhǎng)度為奇(偶)數(shù)，則稱為奇(偶)回路。例題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)56說(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.57說(shuō)明(續(xù))(3)初級(jí)通路(回路)是簡(jiǎn)單通路(回路),但反之不真初級(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的基本回路。61短程線與距離設(shè)u,v為圖G中任意兩個(gè)結(jié)點(diǎn)，u與v之間的短程線:u與v之間長(zhǎng)度最短的通路(設(shè)u與v連通)u與v之間的距離d(u,v):u與v之間短程線的長(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)

例如a與e之間的短程線: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)，則稱G是連通圖；否則，稱G是非連通圖。連通關(guān)系R={<u,v>|u,v

V且u與v連通}.R是等價(jià)關(guān)系連通分支:V關(guān)于R的等價(jià)類的導(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),則稱V

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

E,若W(G

E

)>W(G)且

E

E,W(G

E

)=W(G),則稱E

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

橋:e8,e9邊割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}66說(shuō)明Kn無(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是連通的。有向圖的連通性及其分類定義

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

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

強(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)連通的,稱為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)程集合所涉及的全部資源類型組成。邊集合分為以下兩種：（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．．．．r2758.3圖的表示8.3.1鄰接表8.3.2鄰接矩陣8.3.3可達(dá)矩陣8.3.4關(guān)聯(lián)矩陣76定義

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

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

用鄰接表表示有向簡(jiǎn)單圖。8.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的鄰接矩陣為，其中78例題A=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ù)目。79有向圖中的通路數(shù)與回路數(shù)(續(xù))推論設(shè)矩陣

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

81A=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

寫出如下圖所示的無(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列元素交換，得到矩陣

。

矩陣

和矩陣

相同，所以兩個(gè)圖同構(gòu)。8.3.3可達(dá)矩陣定義

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

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

G的可達(dá)矩陣為

，

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

寫出右圖的可達(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)連通分支。89則稱(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)矩陣90例題ej與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è)-191定義

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

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

m為G的關(guān)聯(lián)矩陣,記為M(G).mij的可能取值為:0,1,2例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2110000101110000110000000011008.3.4關(guān)聯(lián)矩陣同一個(gè)圖當(dāng)結(jié)點(diǎn)或邊的邊序不同時(shí),其對(duì)應(yīng)的A(G)有行序、列序的差別。92性質(zhì)(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例題三枚錢幣處于反、正、反面，每次只許翻動(dòng)一枚錢幣，問(wèn)連續(xù)翻動(dòng)三次后，能否出現(xiàn)全正面或全反面。例題（續(xù)）解

引入一個(gè)三元組(q0,q1,q2)來(lái)描述錢幣的狀態(tài)，錢幣正面為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)。三枚錢幣的初始狀態(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)錢幣三次，不能出現(xiàn)全正面，可以出現(xiàn)全反面，有7種翻動(dòng)方法可以出現(xiàn)全反面。a:把錢幣q0翻轉(zhuǎn)一次

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

c:把錢幣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=

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

E2=

，則稱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)不相鄰，則稱U為G的一個(gè)點(diǎn)獨(dú)立集，簡(jiǎn)稱獨(dú)立集。若圖G的一個(gè)獨(dú)立集，再加入任何結(jié)點(diǎn)都不是獨(dú)立集，則稱為極大獨(dú)立集；結(jié)點(diǎn)數(shù)最多的獨(dú)立集稱為最大獨(dú)立集；最大獨(dú)立集的結(jié)點(diǎn)數(shù)稱為圖G的獨(dú)立數(shù)，記為α(G)。例題{a,e}和{b,d,f}是