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

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

B={(x,y)|x

A

y

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

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

V(G)(G為無向圖)

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

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

v

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

(2)設(shè)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)奇度頂點(diǎn)與偶度頂點(diǎn)

(6)懸掛頂點(diǎn)與懸掛邊14d(v1)＝3，d+(v1)＝1，d-(v1)＝2；實(shí)例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是懸掛頂點(diǎn)，<v1，v4>為懸掛邊。例215定理14.1設(shè)G=<V,E>為任意無向圖，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,那么16握手定理的推論推論任何圖(無向或有向)中，奇度頂點(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ù).17例3

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

d是可圖化的當(dāng)且僅當(dāng)非負(fù)整數(shù)序列之和能被2整除。定理14.4設(shè)G為任意的n階無向簡(jiǎn)單圖，那么Δ(G)≦n-1.20例4(1)(3,3,2,3)，(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？(2)(3,3,3,1)可圖化嗎？可簡(jiǎn)圖化嗎？(3)(4,4,3,3,2,2)可圖化嗎？可簡(jiǎn)圖化嗎？實(shí)例解(1)由可圖化定理，它們都不能成為圖的度數(shù)序列。(2)可圖化，但不可簡(jiǎn)單圖化。(3)可簡(jiǎn)單圖化。21圖的同構(gòu)定義14.5設(shè)G1=<V1,E1>,G2=<V2,E2>為兩個(gè)無向圖(兩個(gè)有向圖)，假設(shè)存在雙射函數(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.22G1≌G2；G3≌G4(G3和G4稱為自補(bǔ)圖)；G5≌G6

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

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

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

1)階競(jìng)賽圖——基圖為Kn的有向簡(jiǎn)單圖.邊數(shù)為

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

有向完全圖

競(jìng)賽圖

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

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

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

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

環(huán)〔長(zhǎng)為1的圈〕的長(zhǎng)度為1，兩條平行邊構(gòu)成的圈長(zhǎng)度為2，無向簡(jiǎn)單圖中，圈長(zhǎng)3，有向簡(jiǎn)單圖中圈的長(zhǎng)度2.35通路與回路的長(zhǎng)度定理14.5在n階圖G中，假設(shè)從頂點(diǎn)vi到vj〔vivj〕存在通路，那么從vi到vj存在長(zhǎng)度小于或等于n1的通路.推論在n階圖G中，假設(shè)從頂點(diǎn)vi到vj〔vivj〕存在通路，那么從vi到vj存在長(zhǎng)度小于或等于n1的初級(jí)通路〔路徑〕.定理14.6在一個(gè)n階圖G中，假設(shè)存在vi到自身的回路，那么一定存在vi到自身長(zhǎng)度小于或等于n的回路.推論在一個(gè)n階圖G中，假設(shè)存在vi到自身的簡(jiǎn)單回路，那么一定存在長(zhǎng)度小于或等于n的初級(jí)回路.3614.3

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

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

D=<V,E>為有向圖

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

D單向連通——

vi,vj

V，vi

vj

或vj

vi

D強(qiáng)連通——

vi,vj

V，vi

vj易知，強(qiáng)連通

單向連通

弱連通判別法定理14.8

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

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

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

(1)

(2)

(4)

(3)46擴(kuò)大路徑法的應(yīng)用例4設(shè)G為n〔n3〕階無向簡(jiǎn)單圖，2，證明G中存在長(zhǎng)度+1的圈.〔作業(yè)〕證設(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的圈.

小結(jié)48二部圖定義14.22設(shè)G=<V,E>為一個(gè)無向圖，假設(shè)能將V分成V1和V2(V1V2=V，V1V2=)，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，那么稱G為二部圖(或稱二分圖、偶圖等)，稱V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為<V1,V2,E>.又假設(shè)G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，那么稱G為完全二部圖，記為Kr,s，其中r=|V1|，s=|V2|.約定：n階零圖為二部圖.49二部圖的判別法定理14.10無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇圈判斷以下圖哪些是二部圖，哪些是完全二部圖？5014.4圖的矩陣表示無向圖的關(guān)聯(lián)矩陣〔對(duì)圖無限制〕定義14.23無向圖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ì)：51有向圖的關(guān)聯(lián)矩陣〔無環(huán)有向圖〕

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

(4)平行邊對(duì)應(yīng)的列相同性質(zhì)：有向圖的關(guān)聯(lián)矩陣52有向圖的鄰接矩陣〔無限制〕定義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ì)：

53推論設(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ù).

54例5有向圖D如下圖，求A,A2,A3,A4，并答復(fù)諸問題：(1)D中長(zhǎng)度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？實(shí)例55(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í)例求解56定義14.26

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

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