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

第四部分

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

圖的基本概念一、無(wú)向圖與有向圖的定義定義14.1

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

為頂點(diǎn)集，元素稱為頂點(diǎn)(2)E為VV的多重集，其元素稱為無(wú)向邊，簡(jiǎn)稱邊實(shí)例

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

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

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

(1)無(wú)向圖中的平行邊及重?cái)?shù)：在無(wú)向圖中，如果關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊多于1條，則稱這些邊為平行邊。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證

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

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

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

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

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

無(wú)向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于3，問G的階數(shù)n為幾？解本題的關(guān)鍵是應(yīng)用握手定理.設(shè)除3度與4度頂點(diǎn)外，還有x個(gè)頂點(diǎn)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}為無(wú)向圖G的頂點(diǎn)集，稱d(v1),d(v2),…,d(vn)為G的度數(shù)列

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

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

設(shè)G為任意的n階無(wú)向簡(jiǎn)單圖，則

四、圖的同構(gòu)定義14.5

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

（<vi,vj>E1當(dāng)且僅當(dāng)<f(vi),f(vj)>E2)并且,(vi,vj)（<vi,vj>）與(f(vi),f(vj))（<f(vi),f(vj)>）的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記作G1G2.圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性.能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件：①邊數(shù)相同，頂點(diǎn)數(shù)相同;②度數(shù)列相同;③對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同，等等若破壞必要條件，則兩圖不同構(gòu)判斷兩個(gè)圖同構(gòu)是個(gè)難題圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什么？

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

(1)(2)

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

n階k正則圖——==k

的無(wú)向簡(jiǎn)單圖簡(jiǎn)單性質(zhì)：邊數(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）的導(dǎo)出子圖，記作G[V](5)E（EE且E）的導(dǎo)出子圖，記作G[E]例2

畫出K4的所有非同構(gòu)的生成子圖例3

畫出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖解

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

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

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

給定圖G=<V,E>（無(wú)向或有向的），G中頂點(diǎn)與邊的交替序列

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

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

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

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

到vj存在長(zhǎng)度小于或等于n1的初級(jí)通路（路徑）.定理14.6

在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長(zhǎng)度小于或等于n的回路.推論在一個(gè)n階圖G中，若存在vi到自身的簡(jiǎn)單回路，則一定存在長(zhǎng)度小于或等于n的初級(jí)回路.1.無(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，則稱G連通②V/R={V1,V2,…,Vk}，稱G[V1],G[V2],…,G[Vk]為連通分支，其個(gè)數(shù)p(G)=k(k1)；

k=1，G連通第三節(jié)圖的連通性(3)短程線與距離

①u與v之間的短程線：uv，u與v之間長(zhǎng)度最短的通路②u與v之間的距離：d(u,v)——短程線的長(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)2.無(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>,VV

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

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

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

e是割邊（橋）——{e}為邊割集例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)說明：Kn中無(wú)點(diǎn)割集，Nn中既無(wú)點(diǎn)割集，也無(wú)邊割集，其中Nn為n階零圖.若G連通，E為邊割集，則p(GE)=2，V為點(diǎn)割集，則p(GV)23.點(diǎn)連通度與邊連通度定義14.18

G為連通非完全圖

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

規(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邊-連通圖幾點(diǎn)說明(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)畫出一個(gè)<<的無(wú)向簡(jiǎn)單圖二、有向圖的連通性1、有向圖節(jié)點(diǎn)間可達(dá)性定義14.20

D=<V,E>為有向圖

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

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

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

具有自反性、對(duì)稱性、傳遞性vi到vj的短程線與距離類似于無(wú)向圖中，只需注意距離表示法的不同(無(wú)向圖中d(vi,vj)，有向圖中d<vi,vj>)及d<vi,vj>無(wú)對(duì)稱性2、有向圖的連通性及分類定義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)過每個(gè)頂點(diǎn)至少一次的回路定理14.9D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路3.擴(kuò)大路徑法無(wú)向圖中設(shè)G=<V,E>為n階無(wú)向圖，E.設(shè)l為G中一條路徑，若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它們擴(kuò)到通路中來(lái)，繼續(xù)這一過程，直到最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止.設(shè)最后得到的路徑為l+k（長(zhǎng)度為l的路徑擴(kuò)大成了長(zhǎng)度為l+k的路徑），稱l+k為“極大路徑”，稱使用此種方法證明問題的方法為“擴(kuò)大路徑法”.有向圖中類似討論，只需注意，在每步擴(kuò)大中保證有向邊方向的一致性.由某條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是圖中最長(zhǎng)的路徑下圖中，(1)中實(shí)線邊所示的長(zhǎng)為2的初始路徑，(2),(3),(4)中實(shí)線邊所示的都是它擴(kuò)展成的極大路徑.還能找到另外的極大路徑嗎？例4

設(shè)G為n（n3）階無(wú)向簡(jiǎn)單圖，

2，證明G中存在長(zhǎng)度

+1的圈.證設(shè)

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

l（為什么？）.因?yàn)関0不與

外頂點(diǎn)相鄰，又d(v0)

，因而在上除v1外，至少還存在1個(gè)頂點(diǎn)與v0相鄰.設(shè)vx是離v0最遠(yuǎn)的頂點(diǎn)，于是v0v1…vxv0為G中長(zhǎng)度

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

設(shè)G=<V,E>為一個(gè)無(wú)向圖，若能將V分成V1和V2(V1V2=V，V1V2=)，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱G為二部圖

(或稱二分圖、偶圖等)，稱V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G，記為<V1,V2,E>.

又若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，則稱G為完全二部圖，記為Kr,s，其中r=|V1|，s=|V2|.注意，n階零圖為二部圖.定理14.10

無(wú)向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無(wú)奇圈由定理14.10可知圖9中各圖都是二部圖，哪些是完全二部圖？哪些圖是同構(gòu)的？第四節(jié)圖的矩陣表示一、無(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ù)，稱(mij)nm為G的關(guān)聯(lián)矩陣，記為M(G).性質(zhì)二、有向圖的關(guān)聯(lián)矩陣（無(wú)環(huán)有向圖）

定義14.25

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

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

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

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

為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ù).推論

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

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

有向圖D如圖所示，求A,A2,A3,A4，并回答諸問題：(1)D中長(zhǎng)度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？(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條是回路.四、有向圖的可達(dá)矩陣定義14.27

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

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

習(xí)題課基本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系記住通路與回路的定義、分類及表示法深刻理解與無(wú)向圖連通性、連通度有關(guān)的諸多概念會(huì)判別有向圖連通性的類型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣1．9階無(wú)向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是5就是6.證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn).證關(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）它們都滿足要求.方法二：反證法否則，由握手定理推論可知，“G至多有4個(gè)5度頂點(diǎn)并且至多有4個(gè)6度頂點(diǎn)”，這與G是9階圖矛盾.2．?dāng)?shù)組2,