離散數(shù)學第14章-圖論課件

第四部分

圖論本部分主要內容圖的基本概念歐拉圖、哈密頓圖樹主要內容圖通路與回路圖的連通性圖的矩陣表示圖的運算第十四章

圖的基本概念一、無向圖與有向圖的定義定義14.1

無向圖G=<V,E>,其中(1)V

為頂點集，元素稱為頂點(2)E為VV的多重集，其元素稱為無向邊，簡稱邊實例

設V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}則G=<V,E>為一無向圖第一節(jié)圖定義14.2

有向圖D=<V,E>,只需注意E是VV的多重子集，圖2表示的是一個有向圖，試寫出它的V和E注意：圖的數(shù)學定義與圖形表示，在同構（待敘）的意義下是一一對應的相關概念1.圖①可用G泛指圖（無向的或有向的）②V(G),E(G),V(D),E(D)③n階圖n階零圖：一條邊也沒有的圖稱為零圖平凡圖：1階零圖4.空圖——：頂點集為空集的圖5.用ek表示無向邊或有向邊6.頂點與邊的關聯(lián)關系①關聯(lián)、關聯(lián)次數(shù)②環(huán)③孤立點頂點之間的相鄰與鄰接關系8.鄰域與關聯(lián)集①vV(G)(G為無向圖)

②vV(D)(D為有向圖)9.標定圖與非標定圖10.基圖：將有向圖的各條有向邊改成無向邊后所得到的無向圖稱為這個有向圖的基圖二多重圖與簡單圖定義14.3

(1)無向圖中的平行邊及重數(shù)：在無向圖中，如果關聯(lián)一對頂點的無向邊多于1條，則稱這些邊為平行邊。

(2)有向圖中的平行邊及重數(shù)（注意方向性）

(3)多重圖：含平行邊的圖

(4)簡單圖：不含平行邊也不含環(huán)的圖三、頂點的度數(shù)及握手定理定義14.4(1)設G=<V,E>為無向圖,vV,稱v

作為邊的端點的次數(shù)之和為v的度數(shù)，記作d(v)，簡稱度

(2)設D=<V,E>為有向圖,vV,

d+(v)——v的出度：以v為始點的次數(shù)之和

d(v)——v的入度：以v為終點的次數(shù)之和

d(v)——v的度或度數(shù)

(3)(G)：無向圖G的最大度

(G)：無向圖G的最小度

(4)+(D)：有向圖D的最大出度

+(D)：有向圖D的最小出度

(D)：有向圖D的最大入度

(D)：有向圖D的最小入度

(D)：有向圖D的最大度

(D)：有向圖D的最小度

(5)度數(shù)為1的頂點稱為懸掛頂點，與它關聯(lián)的邊稱為懸掛邊（6）奇頂點度：度為奇數(shù)的頂點

偶頂點度：度為偶數(shù)的頂點例：求頂點的度，以及圖的(G),(G)，+(D),+(D),(D),(D),(D),(D)2.圖論基本定理握手定理定理14.1

設G=<V,E>為任意無向圖，V={v1,v2,…,vn},|E|=m,則

證

G中每條邊(包括環(huán))均有兩個端點，所以在計算G中各頂點度數(shù)之和時，每條邊均提供2度，m條邊共提供2m度.

本定理的證明類似于定理14.1定理14.2

設D=<V,E>為任意有向圖，V={v1,v2,…,vn},|E|=m,則推論任何圖(無向或有向)中，奇度頂點的個數(shù)是偶數(shù).證設G=<V,E>為任意圖，令

V1={v|vVd(v)為奇數(shù)}

V2={v|vVd(v)為偶數(shù)}則V1V2=V,V1V2=，由握手定理可知由于2m,均為偶數(shù)，所以為偶數(shù)，但因為V1中頂點度數(shù)為奇數(shù)，所以|V1|必為偶數(shù).例1

無向圖G有16條邊，3個4度頂點，4個3度頂點，其余頂點度數(shù)均小于3，問G的階數(shù)n為幾？解本題的關鍵是應用握手定理.設除3度與4度頂點外，還有x個頂點v1,v2,…,vx，則

d(vi)2，i=1,2,…,x，于是得不等式

3224+2x得x4,階數(shù)n4+4+3=11.3.圖的度數(shù)列（1）V={v1,v2,…,vn}為無向圖G的頂點集，稱d(v1),d(v2),…,d(vn)為G的度數(shù)列

（2）V={v1,v2,…,vn}為有向圖D的頂點集，

D的度數(shù)列：d(v1),d(v2),…,d(vn)D的出度列：d+(v1),d+(v2),…,d+(vn)D的入度列：d(v1),d(v2),…,d(vn)（3）非負整數(shù)列d=(d1,d2,…,dn)在為偶數(shù)的情況下可圖形化易知：(2,4,6,8,10)，(1,3,3,3,4)是可圖化的，后者又是可簡單圖化的，而(2,2,3,4,5)，(3,3,3,4)都不是可簡單圖化的，特別是后者也不是可圖化的定理14.4

設G為任意的n階無向簡單圖，則

四、圖的同構定義14.5

設G1=<V1,E1>,G2=<V2,E2>為兩個無向圖(兩個有向圖)，若存在雙射函數(shù)f:V1V2,對于vi,vjV1,(vi,vj)E1當且僅當(f(vi),f(vj))E2

（<vi,vj>E1當且僅當<f(vi),f(vj)>E2)并且,(vi,vj)（<vi,vj>）與(f(vi),f(vj))（<f(vi),f(vj)>）的重數(shù)相同，則稱G1與G2是同構的，記作G1G2.圖之間的同構關系具有自反性、對稱性和傳遞性.能找到多條同構的必要條件，但它們全不是充分條件：①邊數(shù)相同，頂點數(shù)相同;②度數(shù)列相同;③對應頂點的關聯(lián)集及鄰域的元素個數(shù)相同，等等若破壞必要條件，則兩圖不同構判斷兩個圖同構是個難題圖中(1)與(2)的度數(shù)列相同，它們同構嗎？為什么？

(1)(2)(3)(4)圖中，(1)與(2)不同構（度數(shù)列不同），(3)與(4)也不同構.

(1)(2)

五、完全圖與競賽圖定義14.6(1)n(n1)階無向完全圖——每個頂點與其余頂點均相鄰的無向簡單圖，記作Kn.簡單性質：邊數(shù)(2)n(n1)階有向完全圖——每對頂點之間均有兩條方向相反的有向邊的有向簡單圖.簡單性質：(3)n(n1)階競賽圖——基圖為Kn的有向簡單圖.簡單性質：邊數(shù)(1)為K5(2)為3階有向完全圖(3)為4階競賽圖.六、正則圖定義14.7

n階k正則圖——==k

的無向簡單圖簡單性質：邊數(shù)（由握手定理得）Kn是n1正則圖七子圖定義14.8

G=<V,E>,G=<V,E>(1)GG——G為G的子圖，G為G的母圖(2)若GG且V=V，則稱G為G的生成子圖(3)若VV或EE，稱G為G的真子圖(4)V（VV且V）的導出子圖，記作G[V](5)E（EE且E）的導出子圖，記作G[E]例2

畫出K4的所有非同構的生成子圖例3

畫出4階3條邊的所有非同構的無向簡單圖解

（1）由握手定理，所畫的無向簡單圖各頂點度數(shù)之和為2x3=6,最大度小于或等于3.

問題演變?yōu)椋簩?分成4個非負整數(shù)，每個整數(shù)大于等于0且小于等于3；奇數(shù)的個數(shù)為偶數(shù)。排列組合：（1）3,1,1,1（2）2,2,1,1（3）2，2,2，0八、補圖定義14.9

設G=<V,E>為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補圖，記作.若G,則稱G是自補圖.相對于K4,求上面圖中所有圖的補圖，并指出哪些是自補圖.第二節(jié)通路與回路一、通路與回路的定義定義14.11

給定圖G=<V,E>（無向或有向的），G中頂點與邊的交替序列

=v0e1v1e2…elvl，vi1,vi是ei的端點.(1)通路與回路：為通路；若v0=vl，為回路，l為回路長度.(2)簡單通路與回路：所有邊各異，為簡單通路，又若v0=vl，為簡單回路(3)初級通路(路徑)與初級回路(圈)：中所有頂點各異，則稱為初級通路(路徑)，又若除v0=vl，所有的頂點各不相同且所有的邊各異，則稱為初級回路(圈)(4)復雜通路與回路：有邊重復出現(xiàn)幾點說明：表示法①定義表示法②只用邊表示法③只用頂點表示法（在簡單圖中）④混合表示法環(huán)（長為1的圈）的長度為1，兩條平行邊構成的圈長度為2，無向簡單圖中，圈長3，有向簡單圖中圈的長度2.

不同的圈（以長度3的為例）①定義意義下無向圖：圖中長度為l（l3）的圈，定義意義下為2l有向圖：圖中長度為l（l3）的圈，定義意義下為l個②同構意義下：長度相同的圈均為1個試討論l=3和l=4的情況二、通路與回路的長度定理14.5

在n階圖G中，若從頂點vi到vj（vivj）存在通路，則從vi到vj存在長度小于或等于n1的通路.推論在n階圖G中，若從頂點vi

到vj（vivj）存在通路，則從vi

到vj存在長度小于或等于n1的初級通路（路徑）.定理14.6

在一個n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長度小于或等于n的回路.推論在一個n階圖G中，若存在vi到自身的簡單回路，則一定存在長度小于或等于n的初級回路.1.無向圖的連通性(1)頂點之間的連通關系：G=<V,E>為無向圖①若vi與vj之間有通路，則vivj②是V上的等價關系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連通第三節(jié)圖的連通性(3)短程線與距離

①u與v之間的短程線：uv，u與v之間長度最短的通路②u與v之間的距離：d(u,v)——短程線的長度③d(u,v)的性質：

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

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

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

Ge——將e從G中去掉

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

G=<V,E>,VV

V為點割集——p(GV)>p(G)且有極小性

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

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

e是割邊（橋）——{e}為邊割集例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)23.點連通度與邊連通度定義14.18

G為連通非完全圖

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

規(guī)定(Kn)=n1

若G非連通，(G)=0

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

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

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

若(G)r，則稱G是r邊-連通圖圖中，==1，它是1-連通圖和1邊-連通圖幾點說明(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,,之間的關系.定理7.5

(G)(G)(G)請畫出一個<<的無向簡單圖二、有向圖的連通性1、有向圖節(jié)點間可達性定義14.20

D=<V,E>為有向圖

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

vivj（vi與vj相互可達）性質

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

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

D=<V,E>為有向圖

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

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

或vjvi

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

D強連通當且僅當D中存在經過每個頂點至少一次的回路定理14.9D單向連通當且僅當D中存在經過每個頂點至少一次的通路3.擴大路徑法無向圖中設G=<V,E>為n階無向圖，E.設l為G中一條路徑，若此路徑的始點或終點與通路外的頂點相鄰，就將它們擴到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個端點不與通路外的頂點相鄰為止.設最后得到的路徑為l+k（長度為l的路徑擴大成了長度為l+k的路徑），稱l+k為“極大路徑”，稱使用此種方法證明問題的方法為“擴大路徑法”.有向圖中類似討論，只需注意，在每步擴大中保證有向邊方向的一致性.由某條路徑擴大出的極大路徑不惟一，極大路徑不一定是圖中最長的路徑下圖中，(1)中實線邊所示的長為2的初始路徑，(2),(3),(4)中實線邊所示的都是它擴展成的極大路徑.還能找到另外的極大路徑嗎？例4

設G為n（n3）階無向簡單圖，

2，證明G中存在長度

+1的圈.證設

=v0v1…vl是由初始路徑0用擴大路徑法的得到的極大路徑，則

l（為什么？）.因為v0不與

外頂點相鄰，又d(v0)

，因而在上除v1外，至少還存在1個頂點與v0相鄰.設vx是離v0最遠的頂點，于是v0v1…vxv0為G中長度

+1的圈.4、二部圖定義14.23

設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階零圖為二部圖.定理14.10

無向圖G=<V,E>是二部圖當且僅當G中無奇圈由定理14.10可知圖9中各圖都是二部圖，哪些是完全二部圖？哪些圖是同構的？第四節(jié)圖的矩陣表示一、無向圖的關聯(lián)矩陣（對圖無限制）定義14.24

無向圖G=<V,E>，|V|=n，|E|=m，令mij為vi與ej的關聯(lián)次數(shù)，稱(mij)nm為G的關聯(lián)矩陣，記為M(G).性質二、有向圖的關聯(lián)矩陣（無環(huán)有向圖）

定義14.25

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

性質(4)平行邊對應的列相同三、有向圖的鄰接矩陣定義14.26

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

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

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

設A為有向圖D的鄰接矩陣，V={v1,v2,…,vn}為頂點集，則A的l次冪Al（l1）中元素為D中vi到vj長度為l的通路數(shù)，其中為vi到自身長度為l的回路數(shù)，而為D中長度為l的回路總數(shù).推論

設Bl=A+A2+…+Al（l1），則

Bl中元素為D中長度小于或等于l的回路數(shù)為D中長度小于或等于l的通路數(shù).例5

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

D中長度為2的通路為11條，其中有3條是回路.D中長度為3和4的通路分別為14和17條，回路分別為1與3條.(2)D中長度小于等于4的通路為50條，其中有8條是回路.四、有向圖的可達矩陣定義14.27

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

稱(pij)nn為D的可達矩陣，記作P(D)，簡記為P.由于viV，vivi，所以P(D)主對角線上的元素全為1.由定義不難看出,D強連通當且僅當P(D)為全1矩陣.下圖所示有向圖D的可達矩陣為第十四章

習題課基本要求深刻理解握手定理及推論的內容并能靈活地應用它們深刻理解圖同構、簡單圖、完全圖、正則圖、子圖、補圖、二部圖的概念以及它們的性質及相互之間的關系記住通路與回路的定義、分類及表示法深刻理解與無向圖連通性、連通度有關的諸多概念會判別有向圖連通性的類型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達矩陣1．9階無向圖G中，每個頂點的度數(shù)不是5就是6.證明G中至少有5個6度頂點或至少有6個5度頂點.證關鍵是利用握手定理的推論.方法一：窮舉法設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階圖矛盾.2．數(shù)組2,