離散數(shù)學第14章

1第五局部圖論圖論是數(shù)學的一個分支,以圖為研究對象。圖是由假設干給定的點和連接兩點的線構(gòu)成，其中，點代表事物，連接兩點的線表示兩個事物之間具有的特定關系。圖論起源于18世紀，追朔到1736年瑞士數(shù)學家L.Euler發(fā)表了圖論的首篇論文——《哥尼斯堡七橋問題無解》，提出和解決著名Konigsberg七橋問題。1936年，匈牙利數(shù)學家寇尼格〔Konig〕出版了圖論的第一部專著《有限圖與無限圖理論》，這是圖論開展史上的重要的里程碑，它標志著圖論將進入突飛猛進開展的新階段。圖論在許多領域，如計算機科學、物理學、化學、運籌學、信息論、控制論、網(wǎng)絡通訊、社會科學以及經(jīng)濟管理、軍事、國防、工農(nóng)業(yè)生產(chǎn)等方面都得到廣泛的應用。2經(jīng)典的圖論問題——七橋問題瑞士數(shù)學家歐拉〔Euler〕3經(jīng)典的圖論問題——四色問題4圖論結(jié)構(gòu)本局部主要內(nèi)容圖的根本概念歐拉圖、哈密頓圖樹平面圖5第十四章圖的根本概念主要內(nèi)容圖的概念通路與回路圖的連通性圖的矩陣表示圖的運算預備知識多重集合——元素可以重復出現(xiàn)的集合無序集——A

B={(x,y)|x

A

y

B}6引例四個班進行第一輪的足球循環(huán)賽，為了表示四個班之間比賽勝負情況，作出如右圖所示的競賽圖。該圖中的4個小圓圈分別表示這四個班，稱之為頂點。如果兩個班進行了一場比賽，那么在兩個頂點間用一條帶箭頭的線連接起來，稱之為邊。這樣，利用圖形使得各班之間的比賽及勝負情況一目了然。714.1圖定義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>為一無向圖8有向圖定義14.2有向圖D=<V,E>,(1)V為頂點集，元素稱為頂點(2)E為VV的有窮多重子集，其元素稱為有向邊，簡稱邊圖2表示的是一個有向圖，試寫出它的V和E

注意：圖的數(shù)學定義與圖形表示，在同構(gòu)〔待敘〕的意義下是一一對應的9相關概念1.圖①可用G泛指圖〔無向的或有向的〕②V(G),E(G),V(D),E(D)③n階圖2.有限圖即(n,m)圖3.n階零圖與平凡圖4.空圖——5.用ek表示無向邊或有向邊6.頂點與邊的關聯(lián)關系①關聯(lián)、關聯(lián)次數(shù)②環(huán)③孤立點7.頂點之間的相鄰與鄰接關系108.鄰域與關聯(lián)集①v

V(G)(G為無向圖)

v的關聯(lián)集②v

V(D)(D為有向圖)9.標定圖〔每個頂點、每條邊標注符號〕與非標定圖10.有向圖的基圖相關概念11多重圖與簡單圖定義14.3(1)無向圖中的平行邊及重數(shù)(2)有向圖中的平行邊及重數(shù)〔注意方向性〕(3)多重圖：含有平行邊的圖(4)簡單圖：既不含平行邊也無環(huán)的圖簡單圖是圖論中根底而又極其重要的概念12實例G1、G2是多重圖，G3是線圖，G4是簡單圖。例113頂點的度數(shù)定義14.4(1)設G=<V,E>為無向圖,

v

V,d(v)——v的度數(shù),簡稱度

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

v

V,

d+(v)——v的入度

d

(v)——v的出度

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

(3)

(G),

(G)(4)

+(D),

+(D),

(D),

(D),

(D),

(D)(5)奇度頂點與偶度頂點

(6)懸掛頂點與懸掛邊14d(v1)＝3，d+(v1)＝1，d-(v1)＝2；實例d(v2)＝3，d+(v2)＝1，d-(v2)＝2；d(v3)＝5，d+(v3)＝3，d-(v3)＝2；d(v4)＝1，d+(v4)＝1，d-(v4)＝0；d(v5)＝d+(v5)＝d-(v5)＝0；其中，v4是懸掛頂點，<v1，v4>為懸掛邊。例215定理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,那么16握手定理的推論推論任何圖(無向或有向)中，奇度頂點的個數(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ù).17例3

無向圖G有16條邊，3個4度頂點，4個3度頂點，其余頂點度數(shù)均小于3，問G至少有多少頂點？解此題的關鍵是應用握手定理.設除3度與4度頂點外，還有x個頂點v1,v2,…,vx，那么d(vi)2，i=1,2,…,x，于是得不等式323*4+4*3+2x得x4,階數(shù)n4+4+3=11.握手定理的應用18圖的度數(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)上圖的度數(shù)列為〔3,3,5,1,0〕19可圖化與可簡單圖化對于給定的一個非負整數(shù)序列d=(d1,d2,…dn),假設存在以V=(v1,v2,…vn)為頂點集的n階無向圖G,使得d(vi)=di，那么稱d是可圖化的，假設所得的圖是簡單圖，那么稱d是可簡單化的。定理14.3

d是可圖化的當且僅當非負整數(shù)序列之和能被2整除。定理14.4設G為任意的n階無向簡單圖，那么Δ(G)≦n-1.20例4(1)(3,3,2,3)，(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？(2)(3,3,3,1)可圖化嗎？可簡圖化嗎？(3)(4,4,3,3,2,2)可圖化嗎？可簡圖化嗎？實例解(1)由可圖化定理，它們都不能成為圖的度數(shù)序列。(2)可圖化，但不可簡單圖化。(3)可簡單圖化。21圖的同構(gòu)定義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是同構(gòu)的，記作G1G2.22G1≌G2；G3≌G4(G3和G4稱為自補圖)；G5≌G6

，G5稱為彼得森圖；G7與G8不同構(gòu)。圖同構(gòu)的實例例523練習圖(5)與(6)的度數(shù)列相同，它們同構(gòu)嗎？為什么？(1)(2)(3)(4)圖(1)與(2)的度數(shù)列不同，它們不同構(gòu)，(3)與(4)也不同構(gòu).

(5)(6)

24圖同構(gòu)的必要條件圖之間的同構(gòu)關系具有自反性、對稱性和傳遞性.圖同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件：①邊數(shù)相同，頂點數(shù)相同;②度數(shù)列相同;③對應頂點的關聯(lián)集及鄰域的元素個數(shù)相同。假設破壞必要條件，那么兩圖必不同構(gòu)圖同構(gòu)的目的同構(gòu)是在數(shù)學對象之間定義的一類映射,它能揭示出在這些對象的屬性或者操作之間存在的關系。假設兩個數(shù)學結(jié)構(gòu)之間存在同構(gòu)映射，那么這兩個結(jié)構(gòu)叫做是同構(gòu)的。一般來說，如果忽略掉同構(gòu)的對象的屬性或操作的具體定義，單從結(jié)構(gòu)上講，同構(gòu)的對象是完全等價的。研究同構(gòu)的主要目的是為了把數(shù)學理論應用于不同的領域。如果兩個結(jié)構(gòu)是同構(gòu)的，那么其上的對象會有相似的屬性和操作，對某個結(jié)構(gòu)成立的命題在另一個結(jié)構(gòu)上也就成立。因此，如果在某個數(shù)學領域發(fā)現(xiàn)了一個對象結(jié)構(gòu)同構(gòu)于某個結(jié)構(gòu)，且對于該結(jié)構(gòu)已經(jīng)證明了很多定理，那么這些定理馬上就可以應用到該領域。如果某些數(shù)學方法可以用于該結(jié)構(gòu)，那么這些方法也可以用于新領域的結(jié)構(gòu)。這就使得理解和處理該對象結(jié)構(gòu)變得容易，并往往可以讓數(shù)學家對該領域有更深刻的理解。2526完全圖、競賽圖、k正那么圖定義14.6(1)n(n

1)階無向完全圖——每個頂點與其余頂點均相鄰的無向簡單圖，記作Kn.邊數(shù)為：(2)n(n

1)階有向完全圖——每對頂點之間均有兩條方向相反的有向邊的有向簡單圖.邊數(shù)為：(3)n(n

1)階競賽圖——基圖為Kn的有向簡單圖.邊數(shù)為

定義14.7k正那么圖——==k的無向簡單圖.邊數(shù)為：27實例K5

有向完全圖

競賽圖

(1)(2)(3)28子圖定義14.8G=<V,E>,G=<V,E>(1)假設V'V且E'E，那么稱G'是G的子圖，記為G'G。G為G的母圖(2)假設E'E且V=V，那么稱G為G的生成子圖(3)假設VV或EE，稱G為G的真子圖(4)V〔VV且V〕的導出子圖，記作G[V](5)E〔EE且E〕的導出子圖，記作G[E]29例6

畫出K4的所有非同構(gòu)的生成子圖實例30補圖定義14.9設G=<V,E>為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補圖，記作.假設G,那么稱G是自補圖.問1：相對于K4,求上面圖中所有圖的補圖，并指出哪些是自補圖.〔提示：互為自補圖的兩個圖的邊數(shù)有何關系？〕問2：〔n,m〕無向簡單圖G的補圖的邊數(shù)是多少？31

圖的操作定義14.10設圖G＝<V,E>為無向圖，設e∈E，用G-e表示從G中去掉邊e得到的圖，稱為刪除邊e。又設EE，用G-E表示從G中刪除E中所有邊得到的圖，稱為刪除E。設v∈V，用G-v表示從G中去掉結(jié)點v及v關聯(lián)的所有邊得到的圖，稱為刪除頂點v。又設VV，用G-V表示從G中刪除V中所有結(jié)點及關聯(lián)的所有邊得到的圖，稱為刪除V。設e＝(u,v)∈E，用G\e表示從G中刪除e，將e的兩個端點u,v用一個新的結(jié)點w代替，使w關聯(lián)除e外的u和v關聯(lián)的一切邊，稱為邊e的收縮。一個圖G可以收縮為圖H，是指H可以從G經(jīng)過假設干次邊的收縮而得到。設u,v∈V〔u,v可能相鄰，也可能不相鄰〕，用G∪(u,v)表示在u,v之間加一條邊(u,v)，稱為加新邊。

小結(jié)3314.2通路與回路定義14.11給定圖G=<V,E>〔無向或有向的〕，G中頂點與邊的交替序列=v0e1v1e2…elvl，vi1,vi是ei的端點.(1)通路與回路：為通路；假設v0=vl，為回路，l為回路長度.(2)簡單通路與回路：所有邊各異，為簡單通路，又假設v0=vl，為簡單回路(3)初級通路(路徑)與初級回路(圈)：中所有頂點各異，那么稱為初級通路(路徑)，又假設除v0=vl，所有的頂點各不相同且所有的邊各異，那么稱為初級回路(圈)(4)復雜通路與回路：有邊重復出現(xiàn)34幾點說明表示法①定義表示法②只用邊表示法③只用頂點表示法〔在簡單圖中〕

環(huán)〔長為1的圈〕的長度為1，兩條平行邊構(gòu)成的圈長度為2，無向簡單圖中，圈長3，有向簡單圖中圈的長度2.35通路與回路的長度定理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的初級回路.3614.3

圖的連通性無向圖的連通性(1)頂點之間的連通關系：G=<V,E>為無向圖①假設vi與vj之間有通路，那么vivj②R={<vi,vj>|vi,vjV且vivj}是V上的等價關系(2)G的連通性與連通分支①假設vi,vjV，vivj，那么稱G連通②V/R={V1,V2,…,Vk}，稱G[V1],G[V2],…,G[Vk]為連通分支，其個數(shù)p(G)=k(k1)③k=1，G連通37短程線與距離(3)短程線與距離①u與v之間的短程線：u

v，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)38無向圖的連通度1.刪除頂點及刪除邊Gv——從G中將v及關聯(lián)的邊去掉GV——從G中刪除V中所有的頂點Ge——將e從G中去掉GE——刪除E中所有邊2.點割集與邊割集定義14.15G=<V,E>,VVV為點割集——p(GV)>p(G)且有極小性v為割點——{v}為點割集定義14.16G=<V,E>,EEE是邊割集——p(GE)>p(G)且有極小性e是割邊〔橋〕——{e}為邊割集39點割集與割點例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)240點連通度與邊連通度定義14.17G為連通非完全圖點連通度—(G)=min{|V|V為點割集}規(guī)定(Kn)=n1假設G非連通，(G)=0假設(G)k，那么稱G為k-連通圖定義14.18設G為連通圖邊連通度——(G)=min{|E|E為邊割集}假設G非連通，那么(G)=0假設(G)r，那么稱G是r邊-連通圖圖中，==1，它是1-連通圖和1邊-連通圖41幾點說明(Kn)=(Kn)=n1G非連通，那么==0假設G中有割點，那么=1，假設有橋，那么=1。有橋一定有割點；反之不然,,之間的關系定理14.7(G)(G)(G)42有向圖的連通性定義14.19D=<V,E>為有向圖vivj〔vi可達vj〕——vi到vj有通路vivj〔vi與vj相互可達〕性質(zhì)具有自反性(vivi)和傳遞性具有自反性、對稱性、傳遞性vi到vj的短程線與距離類似于無向圖中，只需注意距離表示法的不同(無向圖中d(vi,vj)，有向圖中d<vi,vj>)及d<vi,vj>無對稱性43有向圖的連通性及分類定義14.22

D=<V,E>為有向圖

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

D單向連通——

vi,vj

V，vi

vj

或vj

vi

D強連通——

vi,vj

V，vi

vj易知，強連通

單向連通

弱連通判別法定理14.8

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

D單向連通當且僅當D中存在經(jīng)過每個頂點至少一次的通路44擴大路徑法設G=<V,E>為n階無向圖，E。設l為G中一條路徑，假設此路徑的始點或終點與路徑外的某個頂點相鄰，就將該頂點參加到路徑中來，繼續(xù)這一過程，直到最后得到的路徑的兩個端點不與路徑外的其他頂點相鄰為止。設最后得到的路徑為l+k〔長度為l的路徑擴大成了長度為l+k的路徑〕，稱l+k為“極大路徑〞，稱使用此種方法證明問題為“擴大路徑法〞。有向圖中類似討論，只需注意，在每步擴大中保證有向邊方向的一致性.45實例由某條路徑擴大出的極大路徑不惟一，極大路徑不一定是圖中最長的路徑。上圖中，(1)中實線邊所示的長為2的初始路徑

，(2),(3),(4)中實線邊所示的都是它擴展成的極大路徑.還能找到另外的極大路徑嗎？

(1)

(2)

(4)

(3)46擴大路徑法的應用例4設G為n〔n3〕階無向簡單圖，2，證明G中存在長度+1的圈.〔作業(yè)〕證設=v0v1…vl是由初始路徑0用擴大路徑法得到的極大路徑，那么l〔為什么？〕.因為v0不與外頂點相鄰，又d(v0)，因而在上除v1外，至少還存在1個頂點與v0相鄰.設vx是離v0最遠的頂點，于是v0v1…vxv0為G中長度+1的圈.

小結(jié)48二部圖定義14.22設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階零圖為二部圖.49二部圖的判別法定理14.10無向圖G=<V,E>是二部圖當且僅當G中無奇圈判斷以下圖哪些是二部圖，哪些是完全二部圖？5014.4圖的矩陣表示無向圖的關聯(lián)矩陣〔對圖無限制〕定義14.23無向圖G=<V,E>，|V|=n，|E|=m，令mij為vi與ej的關聯(lián)次數(shù)，稱(mij)nm為G的關聯(lián)矩陣，記為M(G).性質(zhì)：51有向圖的關聯(lián)矩陣〔無環(huán)有向圖〕

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

(4)平行邊對應的列相同性質(zhì)：有向圖的關聯(lián)矩陣52有向圖的鄰接矩陣〔無限制〕定義14.26

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

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

53推論設Bl=A+A2+…+Al〔l1〕，那么Bl中元素為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ù)為D中長度小于或等于l的通路數(shù).鄰接矩陣的應用為D中長度為l的回路總數(shù).

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

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

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

有向圖的可達矩陣〔無限制〕稱(pij)nn為D的可達矩陣，記作P(D)，簡記為P.由于viV，vivi，所以P(D)主對角線上的元素全為1.由定義不難看出,D強連通當且僅當P(D)為全1矩陣.以下圖所示有向圖D的可達矩陣為57本章小結(jié)“圖〞是一個具有二元關系的代數(shù)結(jié)構(gòu)，圖形和矩陣只是它的兩種表示形式。圖的圖形表示可以把圖的結(jié)構(gòu)特征直觀地表現(xiàn)出來，有利于分析和發(fā)現(xiàn)圖的結(jié)構(gòu)性質(zhì)；圖的矩陣表示有利于借助代數(shù)方法研究它，也方便借助計算機實現(xiàn)相關的算法。主要內(nèi)容無向圖、有向圖、關聯(lián)與相鄰、簡單圖、完全圖、正那么圖、子圖、補圖；握手定理與推論；圖的同構(gòu)通路與回路及其分類無向圖的連通性與連通度有向圖的連通性及其分類圖的矩陣表示58根本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應用它們深刻理解圖同構(gòu)、簡單圖、完全圖、正那么圖、子圖、補圖、二部圖的概念以及它們的性質(zhì)及相互之間的關系記住通路與回路的定義、分類及表示法深刻理解與無向圖連通性、連通度有關的諸多概念會判別有向圖連通性的類型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達矩陣59作業(yè)14習題十四：10,21,41,45圖的根底知識的應用一問題：舞會上有6個人，是否總能找到3個相互認識的人或三個相互不認識的人？解題思路：首先，建立相應的圖模型含有6個頂點的無向簡單圖G然后，轉(zhuǎn)換為圖的問題描述G或其補圖G‘是否包含一個三角形子圖？解決：圖的根底知識的應用二問題：某地區(qū)有100個小鎮(zhèn)，每個小鎮(zhèn)開出一輛直達巴士，至少到達50個小鎮(zhèn)。能否乘坐巴士從一個小鎮(zhèn)到其他任何小鎮(zhèn)，可以在一個鎮(zhèn)中乘坐一輛巴士，到另一個小鎮(zhèn)換乘另一輛巴士？解題思路：建立圖模型：包含100個頂點的簡單圖，圖中每個頂點至少有50個鄰接點轉(zhuǎn)換為圖的問題描述：該圖是否為連通圖？解決：圖的根底知識的應用三問題：某校5位老師講授5門課程的情況如右表。如果一位老師只能帶一門課，能否給每位老師分配到他們能講授的課？解題思路：圖模型：二部圖轉(zhuǎn)換為圖的問題描述：找到一個二部圖的匹配解決：教師課程T1C1，C3T2C3，C4T3C1，C3T4C2，C3，C4，C5T5C4，C5631．9階無向圖G中，每個頂點的度數(shù)不是5就是6.證明G中至少有5個6度頂點或至少有6個5度頂點.練習1證關鍵是利用握手