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

114.3

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

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

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

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

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

GV——從G中刪除V中所有的頂點

Ge——將e從G中去掉

GE——刪除E中所有邊2.點割集與邊割集點割集與割點定義14.16

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

v為割點——{v}為點割集定義14.17

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

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

G為連通非完全圖

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

規(guī)定(Kn)=n1

若G非連通，(G)=0

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

定義14.19

設(shè)G為連通圖

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

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

若(G)r，則稱G是r邊-連通圖圖中，==1，它是1-連通圖和1邊-連通圖6幾點說明(Kn)=(Kn)=n1G非連通，則==0若G中有割點，則=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)請畫出一個<<的無向簡單圖7有向圖的連通性定義14.20

D=<V,E>為有向圖

vivj（vi可達vj）——vi到vj有通路

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

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

具有自反性、對稱性、傳遞性vi到vj的短程線與距離類似于無向圖中，只需注意距離表示法的不同(無向圖中d(vi,vj)，有向圖中d<vi,vj>)及d<vi,vj>無對稱性8有向圖的連通性及分類定義14.22

D=<V,E>為有向圖

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

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

或vjvi

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

D強連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的回路定理14.9

D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的通路實例

強連通單連通弱連通10二部圖定義14.23

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

3K3,

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

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

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

定義14.25

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

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

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

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

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

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

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

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

19例5

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

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

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

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

V2為結(jié)點集E1∪

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

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

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

V2為結(jié)點集E1⊕

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

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

+.證明D中存在長度

+1的圈.設(shè)

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

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

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

，只需注意d+(vl)

+

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

max{+,}+1的圈.為D中長度

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