離散數(shù)學(xué)(第十四章)

114.3

圖的連通性無(wú)向圖的連通性(1)頂點(diǎn)之間的連通關(guān)系：G=<V,E>為無(wú)向圖①若vi與vj之間有通路，則vivj②是V上的等價(jià)關(guān)系R={<u,v>|u,v

V且uv}(2)G的連通性與連通分支①若u,vV，uv，則稱(chēng)G連通②V/R={V1,V2,…,Vk}，稱(chēng)G[V1],G[V2],…,G[Vk]為連通分支，其個(gè)數(shù)p(G)=k(k1)；

k=1，G連通2短程線(xiàn)與距離(3)短程線(xiàn)與距離①u(mài)與v之間的短程線(xiàn)：uv，u與v之間長(zhǎng)度最短的通路②u與v之間的距離：d(u,v)——短程線(xiàn)的長(zhǎng)度③d(u,v)的性質(zhì)：

d(u,v)0,u?v時(shí)d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)3無(wú)向圖的連通度1.刪除頂點(diǎn)及刪除邊

Gv——從G中將v及關(guān)聯(lián)的邊去掉

GV——從G中刪除V中所有的頂點(diǎn)

Ge——將e從G中去掉

GE——?jiǎng)h除E中所有邊2.點(diǎn)割集與邊割集點(diǎn)割集與割點(diǎn)定義14.16

G=<V,E>,VVV為點(diǎn)割集——p(GV)>p(G)且有極小性

v為割點(diǎn)——{v}為點(diǎn)割集定義14.17

G=<V,E>,EEE是邊割集——p(GE)>p(G)且有極小性

e是割邊（橋）——{e}為邊割集4點(diǎn)割集與割點(diǎn)例3{v1,v4}，{v6}是點(diǎn)割集，v6是割點(diǎn).{v2,v5}是點(diǎn)割集嗎？{e1,e2}，{e1,e3,e5,e6}，{e8}等是邊割集，e8是橋，{e7,e9,e5,e6}是邊割集嗎？幾點(diǎn)說(shuō)明：Kn中無(wú)點(diǎn)割集，Nn中既無(wú)點(diǎn)割集，也無(wú)邊割集，其中Nn為n階零圖.若G連通，E為邊割集，則p(GE)=2，V為點(diǎn)割集，則p(GV)25點(diǎn)連通度與邊連通度定義14.18

G為連通非完全圖

點(diǎn)連通度—(G)=min{|V|V為點(diǎn)割集}

規(guī)定(Kn)=n1

若G非連通，(G)=0

若(G)k，則稱(chēng)G為k-連通圖

定義14.19

設(shè)G為連通圖

邊連通度——(G)=min{|E|E為邊割集}

若G非連通，則(G)=0

若(G)r，則稱(chēng)G是r邊-連通圖圖中，==1，它是1-連通圖和1邊-連通圖6幾點(diǎn)說(shuō)明(Kn)=(Kn)=n1G非連通，則==0若G中有割點(diǎn)，則=1，若有橋，則=1若(G)=k,則G是1-連通圖，2-連通圖，…，k-連通圖，但不是(k+s)-連通圖，s1若(G)=r,則G是1-邊連通圖，2-邊連通圖，…，r-邊連通圖，但不是(r+s)-邊連通圖，s1,,之間的關(guān)系.定理7.5

(G)(G)(G)請(qǐng)畫(huà)出一個(gè)<<的無(wú)向簡(jiǎn)單圖7有向圖的連通性定義14.20

D=<V,E>為有向圖

vivj（vi可達(dá)vj）——vi到vj有通路

vivj（vi與vj相互可達(dá)）性質(zhì)

具有自反性(vivi)、傳遞性

具有自反性、對(duì)稱(chēng)性、傳遞性vi到vj的短程線(xiàn)與距離類(lèi)似于無(wú)向圖中，只需注意距離表示法的不同(無(wú)向圖中d(vi,vj)，有向圖中d<vi,vj>)及d<vi,vj>無(wú)對(duì)稱(chēng)性8有向圖的連通性及分類(lèi)定義14.22

D=<V,E>為有向圖

D弱連通(連通)——基圖為無(wú)向連通圖

D單向連通——vi,vjV，vivj

或vjvi

D強(qiáng)連通——vi,vjV，vivj易知，強(qiáng)連通單向連通弱連通判別法定理14.8

D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路定理14.9

D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通路實(shí)例

強(qiáng)連通單連通弱連通10二部圖定義14.23

設(shè)G=<V,E>為一個(gè)無(wú)向圖，若能將V分成V1和V2(V1V2=V，V1V2=)，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱(chēng)G為二部圖(或稱(chēng)二分圖、偶圖等)，稱(chēng)V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為<V1,V2,E>.又若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，則稱(chēng)G為完全二部圖，記為Kr,s，其中r=|V1|，s=|V2|.注意，n階零圖為二部圖.11K2,

3K3,

3一個(gè)無(wú)向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無(wú)奇數(shù)長(zhǎng)度的回路。二部圖判定定理若|V1|=n，|V2|=m，則記完全二部圖G為Kn,m圈的長(zhǎng)度都是偶數(shù)12例1：判斷下列圖是否為二部圖。v4v3v2v1v5v6v7v8同構(gòu)于v4v3v2v1v5v6同構(gòu)于v6v4v3v2v1v5v7v8v4v3v2v1v5v61314.4圖的矩陣表示無(wú)向圖的關(guān)聯(lián)矩陣（對(duì)圖無(wú)限制）定義14.24

無(wú)向圖G=<V,E>，|V|=n，|E|=m，令mij為vi與ej的關(guān)聯(lián)次數(shù)，稱(chēng)(mij)nm為G的關(guān)聯(lián)矩陣，記為M(G).mij

的可能取值為0,1,2.性質(zhì)無(wú)向圖的關(guān)聯(lián)矩陣?yán)鏴1e2e3e4e5e6v5v1v2v3v4M(G)=21100001011100001100000000110015有向圖的關(guān)聯(lián)矩陣（無(wú)環(huán)有向圖）

定義14.25

有向圖D=<V,E>，令則稱(chēng)(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).

(4)平行邊對(duì)應(yīng)的列相同性質(zhì)有向圖的關(guān)聯(lián)矩陣實(shí)例v1v2v3v4e2e1e3e4e5e6e7M(D)=-11000–110-11000000-1-1-11-1100110017有向圖的鄰接矩陣（無(wú)限制）定義14.26

設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi

鄰接到頂點(diǎn)vj邊的條數(shù)，稱(chēng)為D的鄰接矩陣，記作A(D)，或簡(jiǎn)記為A.性質(zhì)

18推論設(shè)Bl=A+A2+…+Al（l1），則

Bl中元素為D中長(zhǎng)度為l的通路總數(shù)，定理14.11

設(shè)A為有向圖D的鄰接矩陣，V={v1,v2,…,vn}為頂點(diǎn)集，則A的l次冪Al（l1）中元素為D中vi到vj長(zhǎng)度為

l的通路數(shù)，其中為vi到自身長(zhǎng)度為l的回路數(shù)，而為D中長(zhǎng)度小于或等于l的回路數(shù)為D中長(zhǎng)度小于或等于l的通路數(shù).鄰接矩陣的應(yīng)用為D中長(zhǎng)度為l的回路總數(shù).

19例5

有向圖D如圖所示，求A,A2,A3,A4，并回答諸問(wèn)題：(1)D中長(zhǎng)度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？實(shí)例20(1)D中長(zhǎng)度為1的通路為8條，其中有1條是回路.

D中長(zhǎng)度為2的通路為11條，其中有3條是回路.D中長(zhǎng)度為3和4的通路分別為14和17條，回路分別為1與3條.(2)D中長(zhǎng)度小于等于4的通路為50條，其中有8條是回路.實(shí)例求解21定義14.27

設(shè)D=<V,E>為有向圖.V={v1,v2,…,vn},令

有向圖的可達(dá)矩陣（無(wú)限制）稱(chēng)(pij)nn為D的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為P.由于viV，vivi，所以P(D)主對(duì)角線(xiàn)上的元素全為1.由定義不難看出,D強(qiáng)連通當(dāng)且僅當(dāng)P(D)為全1矩陣.下圖所示有向圖D的可達(dá)矩陣為2、邊不相交的G1=<V1,E1,1>G2=<V2,E2,2>同為無(wú)向圖或同為有向圖G1與G2是不相交的E1∩E2=φV1∩V2=φG1與G2是邊不相交E1∩E2=φ4、圖的交G1=<V1,E1,1>G2=<V2,E2,2>是可運(yùn)算的V1∩V2為結(jié)點(diǎn)集E1∩E2為邊集合G1和G2的交G1∩G25、圖的并G1=<V1,E1,1>G2=<V2,E2,2>是可運(yùn)算的V1∪

V2為結(jié)點(diǎn)集E1∪

E2為邊集合G1和G2的并G1∪

G26、圖的差G1=<V1,E1,1>G2=<V2,E2,2>是可運(yùn)算的G1與G2的差:在G1中去掉G2的邊所得到的圖G1-

G27、圖的環(huán)和G1=<V1,E1,1>G2=<V2,E2,2>是可運(yùn)算的V1∪

V2為結(jié)點(diǎn)集E1⊕

E2為邊集合G1和G2的環(huán)和G1⊕

G2圖運(yùn)算的舉例與如下圖所示，求：G1∩G2

G1∪G2G1-G2G2-G1，G1⊕G2

。G1∩G2V1∩V2E1∩E2={a,b,d}={e1,e2,e5}G1∪G2V1∪V2{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}={a,b,c,d,e}E1∪E2=G1-G2G2

–G1G1⊕G2E1⊕

E2=V1∪V2={a,b,c,d,e}{e3,e4,e6,e7,e8,e9,e10}33第十四章

習(xí)題課主要內(nèi)容無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)通路與回路及其分類(lèi)無(wú)向圖的連通性與連通度有向圖的連通性及其分類(lèi)圖的矩陣表示34基本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系記住通路與回路的定義、分類(lèi)及表示法深刻理解與無(wú)向圖連通性、連通度有關(guān)的諸多概念會(huì)判別有向圖連通性的類(lèi)型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣351．9階無(wú)向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是5就是6.證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn).練習(xí)1證關(guān)鍵是利用握手定理的推論.方法一：窮舉法設(shè)G中有x個(gè)5度頂點(diǎn)，則必有(9x)個(gè)6度頂點(diǎn)，由握手定理推論可知，(x,9x)只有5種可能：(0,9),(2,7),(4,5),(6,3),(8,1）它們都滿(mǎn)足要求.方法二：反證法否則，由握手定理推論可知，“G至多有4個(gè)5度頂點(diǎn)并且至多有4個(gè)6度頂點(diǎn)”，這與G是9階圖矛盾.362．?dāng)?shù)組2,2,2,2,3,3能簡(jiǎn)單圖化嗎？若能，畫(huà)出盡可能多的非同構(gòu)的圖來(lái).練習(xí)2只要能畫(huà)出6階無(wú)向簡(jiǎn)單圖，就說(shuō)明它可簡(jiǎn)單圖化.下圖的4個(gè)圖都以此數(shù)列為度數(shù)列，都是K6的子圖.37用擴(kuò)大路徑法證明.情況一：

+.證明D中存在長(zhǎng)度

+1的圈.設(shè)

=v0v1…vl為極大路徑，則l

(為什么?).由于d(v0)

，所以在上存在PLAY鄰接到v0，于是情況二：+

，只需注意d+(vl)

+

.3．設(shè)D=<V,E>為有向簡(jiǎn)單圖，已知(D)2，+(D)>0，(D)>0，證明D中存在長(zhǎng)度

max{+,}+1的圈.為D中長(zhǎng)度

+1的有向圈練習(xí)338(1)D中有幾種非同構(gòu)的圈？(2)D中有幾種非圈非同構(gòu)的簡(jiǎn)單回路？(3)D是哪類(lèi)