離散數(shù)學(xué)圖論

第八章圖論圖論(GraphTheory)圖論是個(gè)應(yīng)用十分廣泛而又極其有趣數(shù)學(xué)分支,物理、學(xué)、生物、經(jīng)濟(jì)、管理科學(xué)、信息論、計(jì)算機(jī)等各個(gè)領(lǐng)域都可以找到圖論的足跡.歷史上很多數(shù)學(xué)家對(duì)圖論的形成作出過貢獻(xiàn),特別要提到的歐拉(Euler)、基爾霍夫(Kirchhoff)與凱萊(Cayley).

歐拉在1736年發(fā)表了第一篇圖論的論文,解決了著名的七橋問題.拓?fù)鋵W(xué)中著名的歐拉公式,也是圖論中的重要公式.基爾霍夫?qū)﹄娐肪W(wǎng)絡(luò)的研究(基爾霍夫定律)以及凱萊在有機(jī)化學(xué)計(jì)算中應(yīng)用了樹和生成樹等概念.很多有趣的數(shù)學(xué)游戲也促進(jìn)了圖論的發(fā)展,如漢米爾頓周游世界游戲,四色定理等,都促進(jìn)了圖論的發(fā)展.8-1.圖的基本概念例1.多用戶操作系統(tǒng)中的進(jìn)程狀態(tài)變換圖:(進(jìn)程:一個(gè)業(yè)務(wù)可以分成若干個(gè)階段,每個(gè)階段看成一個(gè)進(jìn)程.一個(gè)進(jìn)程有三種狀態(tài).)就緒狀態(tài):進(jìn)程具備執(zhí)行條件,因CPU少,要排隊(duì)等待分配

CPU.就緒r執(zhí)行e等待w進(jìn)程調(diào)度請(qǐng)求I/OI/O完成r

weV={r,e,w}E={<r,e>,<e,w>,<w,r>}執(zhí)行狀態(tài):進(jìn)程已經(jīng)分配到CPU,它的程序正被執(zhí)行.等待狀態(tài):進(jìn)程等待某事件(如I/O完成),此時(shí)就是給它CPU

也不能執(zhí)行..例2.“七橋問題”十八世紀(jì),哥尼斯堡城內(nèi)有一條河----普雷格爾河,河中有兩個(gè)島嶼,河面架有七座橋,使得島嶼與兩岸之間互相貫通.

V={A,B,C,D}

E={e1,e2,e3,e4,e5e6,e7}

人們茶余飯后經(jīng)常到橋上散步,從而提出這樣問題:是否可以從某地出發(fā)，每座橋都走一次,再回到出發(fā)點(diǎn).很多人試圖找出這樣的路徑,都沒有找到.后來歐拉證明這樣的路徑根本不存在.此圖可以抽象為上邊右圖.ABCDABCDe1e5e7e6e3e4e2例3.在機(jī)械加工中,經(jīng)常需要在一塊金屬薄板上鉆若干孔(或者是機(jī)械手在印刷電路板上安裝電子元件)如圖所示:問如何確定鉆孔的次序,使之加工的時(shí)間最短.這個(gè)問題可以抽象為在一個(gè)圖上求從某一個(gè)結(jié)點(diǎn)出發(fā),經(jīng)過所有結(jié)點(diǎn)一次,使得此路徑最短.如何找到此路徑.類似的:旅行最優(yōu)問題,工程最優(yōu)問題,成本(費(fèi)用)最低.…...

5372一.

圖的概念

一個(gè)圖G=<V(G),E(G)>,其中

V(G):是G的結(jié)點(diǎn)的非空集合.(V(G)≠Φ),簡(jiǎn)記成V.E(G):

是G的邊的集合.有時(shí)簡(jiǎn)記成E.

結(jié)點(diǎn)(Vertices):用

表示,旁邊標(biāo)上該結(jié)點(diǎn)的名稱.邊(Edges):

有向邊:帶箭頭的弧線.從u到v的邊表示成<u,v>

無向邊:不帶箭頭的弧線.u和v間的邊表示成(u,v)r

weV(G1)={r,e,w}E(G1)={<r,e>,<e,w>,<w,r>}ABCDe1e5e7e6e3e4e2G1:G2:V(G2)={A,B,C,D}E(G2)={e1,e2,e3,e4,e5,e6,e7}在圖中,結(jié)點(diǎn)的相對(duì)位置不同,邊的曲直、長(zhǎng)短無關(guān)緊要.鄰接點(diǎn):與一邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn).u

va

b

鄰接邊:關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊.

環(huán):只關(guān)聯(lián)一個(gè)結(jié)點(diǎn)的邊.

平行邊:在兩個(gè)結(jié)點(diǎn)之間關(guān)聯(lián)的多條邊.二.有向圖與無向圖有向圖:只有有向邊的圖.無向圖:只有無向邊的圖.三.零圖與平凡圖

孤立結(jié)點(diǎn):不與任何邊關(guān)聯(lián)的結(jié)點(diǎn).

u

零圖:僅由一些孤立結(jié)點(diǎn)構(gòu)成的圖.a

即此圖的邊的集合E=Φ

b

c

平凡圖:僅由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的零圖.|V(G)|=1,|E(G)|=0e1ve2

G:

四.簡(jiǎn)單圖與多重圖

簡(jiǎn)單圖:不含有環(huán)和平行邊的圖.

多重圖:含有平行邊的圖.五.無向圖結(jié)點(diǎn)v的度:

1.定義:G是個(gè)無向圖,v∈V(G),結(jié)點(diǎn)v所關(guān)聯(lián)邊數(shù),稱之為結(jié)點(diǎn)v的度.記作deg(v).(或d(v)).deg(a)=3deg(b)=5deg(c)=4deg(d)=2

一個(gè)環(huán)給結(jié)點(diǎn)的度是2.

2.無向圖的結(jié)點(diǎn)度序列:令G=<V,E>是無向圖,V={v1,v2,v3,…,vn},則稱:(der(v1),der(v2),der(v3),…,der(vn))為圖G的結(jié)點(diǎn)度序列.例如上圖的結(jié)點(diǎn)度序列為:(3,5,4,2)

3.圖的最大度Δ(G)與最小度δ(G):G=<V,E>是無向圖,

Δ(G)=max{deg(v)|v∈G}δ(G)=min{deg(v)|v∈G}ABCDe1e5e7e6e3e4e2cbacabd上圖中Δ(G)=5δ(G)=24.定理8-1.1每個(gè)無向圖所有結(jié)點(diǎn)度總和等于邊數(shù)的2倍.即證明:因?yàn)閳D中每條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn),因此每條邊給予它所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)的度各是1,即一條邊對(duì)應(yīng)的度數(shù)是2,所以整個(gè)圖的度數(shù)總和為邊數(shù)的2倍.定理8-1.2(握手定理)每個(gè)無向圖中,奇數(shù)度的結(jié)點(diǎn)必為偶數(shù)個(gè).(一次集會(huì)中,與奇數(shù)個(gè)人握手的人,必是偶數(shù)個(gè).)證明:令G=<V,E>是無向圖,將V分成兩個(gè)子集V1和V2,其中V1---是度數(shù)是奇數(shù)的結(jié)點(diǎn)集合,

V2---是度數(shù)是偶數(shù)的結(jié)點(diǎn)集合而是偶數(shù).所以也是偶數(shù),于是奇數(shù)度的結(jié)點(diǎn)數(shù)是偶數(shù).∑deg(v)=2|E|v∈V∑deg(v)+∑deg(v)=2|E|v∈V1v∈V2∑deg(v)v∈V2∑deg(v)v∈V1六.k-正則圖:一個(gè)無向簡(jiǎn)單圖G中,如果Δ(G)=δ(G)=k則稱G為k-正則圖.課堂練習(xí):1.下面哪些數(shù)的序列,可能是一個(gè)圖的度數(shù)序列?如果可能,請(qǐng)?jiān)嚠嫵鏊膱D.哪些可能不是簡(jiǎn)單圖?

a)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4)2.已知無向簡(jiǎn)單圖G中,有10條邊,4個(gè)3度結(jié)點(diǎn),其余結(jié)點(diǎn)的度均小于或等于2,問G中至少有多少個(gè)結(jié)點(diǎn)?為什么?

1.

a)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4)解:a)不是,因?yàn)橛腥齻€(gè)數(shù)字是奇數(shù).

b)是.

c)不是簡(jiǎn)單圖,因?yàn)樗?個(gè)結(jié)點(diǎn),已經(jīng)有4個(gè)結(jié)點(diǎn)度分別為1,2,2,3,余下一個(gè)結(jié)點(diǎn)度為4,必然有環(huán).2.解:已知邊數(shù)|E|=10,∑deg(v)=2|E|=20

其中有4個(gè)3度結(jié)點(diǎn),余下結(jié)點(diǎn)度之和為:20-3×4=8因?yàn)镚是簡(jiǎn)單圖,其余每個(gè)結(jié)點(diǎn)度數(shù)≤2,所以至少還有4個(gè)結(jié)點(diǎn).所以G中至少有8個(gè)結(jié)點(diǎn).

七.有向圖結(jié)點(diǎn)的出度和入度:(indegreeoutdegree)G=<V,E>是有向圖,v∈Vv的出度:從結(jié)點(diǎn)v射出的邊數(shù).記作deg+(v)或dego(v)v的入度:射入結(jié)點(diǎn)v的邊數(shù).記作deg-(v)或degi(v)degi(a)=2degi(b)=2degi(c)=1degi(d)=1dego(a)=2dego(b)=3dego(c)=1dego(d)=0定理8-1.3

G=<V,E>是有向圖,則G的所有結(jié)點(diǎn)的出度之和等于入度之和.證明:因?yàn)閳D中每條邊對(duì)應(yīng)一個(gè)出度和一個(gè)入度.所以所有結(jié)點(diǎn)的出度之和與所有結(jié)點(diǎn)的入度之和都等于有向邊數(shù).必然有所有結(jié)點(diǎn)的出度之和等于入度之和.abcd八.完全圖1.無向完全圖定義:G是個(gè)簡(jiǎn)單圖,如果每對(duì)不同結(jié)點(diǎn)之間都有邊相連則稱G是個(gè)無向完全圖.如果G有n個(gè)結(jié)點(diǎn),則記作Kn.定理8-1.4無向完全圖Kn,有邊數(shù)證明:因?yàn)镵n中每個(gè)結(jié)點(diǎn)都與其余n-1個(gè)結(jié)點(diǎn)關(guān)聯(lián),即每個(gè)結(jié)點(diǎn)的度均為n-1,所以Kn的所有結(jié)點(diǎn)度數(shù)總和為n(n-1),設(shè)邊數(shù)為|E|,于是n(n-1)=2|E|所以|E|=

K2K3K4K52.有向圖的完全圖(注:這里的定義與教材不同)

1).有向簡(jiǎn)單完全圖:G是個(gè)有向簡(jiǎn)單圖,如果任何兩個(gè)不同結(jié)點(diǎn)之間都有相互可達(dá)的邊,則稱它是有向簡(jiǎn)單完全圖.例如:

定理8-1.5:有n個(gè)結(jié)點(diǎn)的有向簡(jiǎn)單完全圖有邊數(shù)為n(n-1).證明:顯然它的邊數(shù)是Kn邊數(shù)的2倍.所以是n(n-1).

2).有向完全圖(有向全圖)(它與完全關(guān)系圖一致)

G是個(gè)有向圖如果任何兩個(gè)結(jié)點(diǎn)之間都有相互可達(dá)的邊,則稱它是有向完全圖.其圖形如下:

所以有n個(gè)結(jié)點(diǎn)的有向完全圖,有邊數(shù)n2.九.子圖和生成子圖1.子圖:設(shè)G=<V,E>是圖,如果G’=<V’,E’>且V’V,V’≠Φ,E’E,則稱G’是G的子圖.可見G1,G2,G3都是K5的子圖.

bcdeabcabcdeG1G2G3K5abcde2.生成子圖設(shè)G=<V,E>是圖,G’=<V’,E’>,G’是G的子圖,如果V’=V,則稱G’是G的生成子圖.上例中,G1是K5的生成子圖.十.補(bǔ)圖由G的所有結(jié)點(diǎn)和為使G變成完全圖,所需要添加的那些邊組成的圖,稱之為G相對(duì)完全圖的補(bǔ)圖,簡(jiǎn)稱G的補(bǔ)圖,記作.G

K5

G

G*十一.相對(duì)補(bǔ)圖設(shè)G1=<V1,E1>是圖G=<V,E>的子圖,如果有G2=<V2,E2>使得E2=E-E1且V2中僅包含E2中的邊所關(guān)聯(lián)的結(jié)點(diǎn),則稱G2是G1相對(duì)G的補(bǔ)圖.可見G2是G3相對(duì)G的補(bǔ)圖.G3也是G2相對(duì)G的補(bǔ)圖.而G1不是G3相對(duì)G的補(bǔ)圖(多了一個(gè)結(jié)點(diǎn)).但是G3是G1相對(duì)G的補(bǔ)圖.可見:相對(duì)補(bǔ)圖無相互性.abcdeGG1abcdecdbeG2abcdeG3十二.圖的同構(gòu)設(shè)G=<V,E>和G’=<V’,E’>是圖,如果存在雙射f:VV’且任何vi,vj∈V,若邊(vi,vj)∈E,當(dāng)且僅當(dāng)邊(f(vi),f(vj))∈E’,(或若邊<vi,vj>∈E,當(dāng)且僅當(dāng)邊<f(vi),f(vj)>∈E’),則稱G與G’同構(gòu),記作G≌G’.(同構(gòu)圖要保持邊的“關(guān)聯(lián)”關(guān)系)例如:右邊所示的兩個(gè)圖:G=<V,E>G’=<V’,E’>構(gòu)造映射f:VV’兩個(gè)圖同構(gòu)的必要條件:1.結(jié)點(diǎn)個(gè)數(shù)相等.2.邊數(shù)相等.3.度數(shù)相同的結(jié)點(diǎn)數(shù)相等.4.對(duì)應(yīng)的結(jié)點(diǎn)的度數(shù)相等.abcd1432a1b2c3d4a1b2c3d4下面是同構(gòu)的圖:右面兩個(gè)圖不同構(gòu):左圖中四個(gè)3度結(jié)點(diǎn)構(gòu)成四邊形,而右圖,則不然.練習(xí):請(qǐng)畫出K4的所有不同構(gòu)的生成子圖.afbecd351624312abc

abecd13452

練習(xí):請(qǐng)畫出K4的所有不同構(gòu)的生成子圖.本節(jié)要求:準(zhǔn)確掌握如下基本概念和定理:1.有向邊,無向邊,孤立結(jié)點(diǎn),平行邊,環(huán).2.有向圖,無向圖,零圖,平凡圖,簡(jiǎn)單圖,多重圖,完全圖,子圖,生成子圖,補(bǔ)圖,相對(duì)補(bǔ)圖3.四個(gè)定理(關(guān)于結(jié)點(diǎn)度,以及結(jié)點(diǎn)度與邊數(shù)關(guān)系)4.圖的同構(gòu)(會(huì)判斷).作業(yè):P279(1)(2)(4)(5)

8-2.路與回路在實(shí)際應(yīng)用中,比如在市內(nèi)乘出租車去參觀一個(gè)博覽會(huì),一定要司機(jī)選一條最短的路.到博覽會(huì)后,最好選一條這樣到路徑,使得每個(gè)展臺(tái)都參觀一次后,再回到原來存包處.這就是路與回路的問題.一.路的概念

1.路的定義:給定圖G=<V,E>設(shè)v0,v1,v2,,…,vn∈V,

e1,e2,,…,en∈E其中ei是關(guān)聯(lián)vi-1,vi的邊,則稱結(jié)點(diǎn)和邊的交叉序列v0e1v1e2v2…envn是連接v0到vn的路.v0是此路的起點(diǎn),vn是此路的終點(diǎn).路中含有的邊數(shù)n稱之為路的長(zhǎng)度.例如上圖中:v0e2v3e6v2是一條長(zhǎng)度為2的路.

v3

v2v1

v0e1e2e3e4e5e6如果圖是個(gè)簡(jiǎn)單圖,則路可以只用結(jié)點(diǎn)序列表示.如右圖中,路:abcad如果圖是個(gè)有向圖,則路可以只用邊序列表示.

如有向圖中e1e5e2e3e6是一條路.2.回路:如果一條路的起點(diǎn)和終點(diǎn)是一個(gè)結(jié)點(diǎn),則稱此路是一個(gè)回路.如右圖中的L1=v0e1v1e5v3e6v2e4v0L2=

v0e1v1e5v3e2v03.跡與閉跡如果一條路中,所有邊都不同,則稱此路為跡.如果一條回路中,所有邊都不同,則稱此回路為閉跡.

v3

v2v1

v0e1e2e3e4e5e6cbad

v3

v2v1

v0e1e2e3e4e5e64.通路與圈如果一條路中,所有結(jié)點(diǎn)都不同,則稱此路為通路.如果一條回路中,除起點(diǎn)和終點(diǎn)外,其余結(jié)點(diǎn)都不同,則稱此回路為圈.例如右圖中:L1=v0e1v1e5v3e6v2e4v0L2=

v0e1v1e5v3e2v0L3=v0e1v1e5v3e2v0e3v3e6v2e4v0L1和L2是閉跡,也是圈.L3是閉跡,而不是圈.

v3

v2v1

v0e1e2e3e4e5e6定理8-2.1在一個(gè)有n個(gè)結(jié)點(diǎn)的圖中,如果從結(jié)點(diǎn)vi到vj存在一條路,則從vi到vj必存在一條長(zhǎng)度不多于n-1的路.*證明:設(shè)vi到vj存在一條路:vivi+1vi+2,…,vj,設(shè)此路的長(zhǎng)度為k.假設(shè)k>n-1,則此路中有k+1個(gè)結(jié)點(diǎn),k+1>n,而G中只有n個(gè)結(jié)點(diǎn),所以此路中必有兩個(gè)結(jié)點(diǎn)相同,假設(shè)vs=vt,(t>s)于是此路為:從圖看出,此路中有一個(gè)從vs到vt的回路,此回路中,有t-s條邊(t-s>1),如果刪去這個(gè)回路,就得到一條vi到vj更短的路.如果新的路長(zhǎng)度還大于n-1,說明此路中還有回路,再刪去回路,如此進(jìn)行下去.最后必可找到長(zhǎng)度小于n-1的路.

vs-1

vi+1

vt+1

vs

=vt

vs+1vi

vt-1

vj

vj-1…...…..….…..應(yīng)用:擺渡人Ferryman,狼Wolf,羊Sheep,干草Hay過河問題.如何擺渡使得它們不能互相傷害.實(shí)際上,這是個(gè)在圖上找一條路的問題.FWSH_WHFSFSWHFSFWSFHHSFWFHFWFSWFSHHFSWFSFSHWSHFWFWFHF--HWFSFS二.無向圖的連通性1.兩個(gè)結(jié)點(diǎn)是連通的:在無向圖中,結(jié)點(diǎn)u和v之間如果存在一條路,則稱u與v是連通的.

我們規(guī)定:對(duì)任何結(jié)點(diǎn)u,u與u是連通的.2.結(jié)點(diǎn)之間的連通關(guān)系是個(gè)等價(jià)關(guān)系.令G=<V,E>是無向圖,R是V上連通關(guān)系,即

R={<u,v>|u和v是連通的}顯然R具有自反、對(duì)稱和傳遞性.于是可以求商集V/R.例1.給定圖G1如右上圖所示:

V/R={{a,b,g},{c,d,e,f},{h}}例2.給定圖G2如右下圖所示:

V/R={{1,3,5},{2,4,6}}ghabefcd2645133.連通分支:令G=<V,E>是無向圖,R是V上連通關(guān)系,設(shè)R對(duì)V的商集中有等價(jià)類V1,V2,V3,…,Vn,這n個(gè)等價(jià)類構(gòu)成的n個(gè)子圖分別記作G(V1),G(V2),G(V3),…,G(Vn),并稱它們?yōu)镚的連通分支.并用W(G)表示G中連通分支數(shù).下邊例中W(G1)=3W(G2)=2W(G3)=14.連通圖:如果一個(gè)圖G只有一個(gè)連通分支(W(G)=1),則稱G是連通圖.

W(G3)=1,G3是連通圖ghabefcd264513G1G2

G3定理8-2.2:圖G=<V,E>是連通的,當(dāng)且僅當(dāng)對(duì)V的任何分成V1、V2的劃分,恒存在一條邊,使得它的兩個(gè)端點(diǎn)分別屬于V1和V2.*證明:必要性.已知G是連通的.令{V1,V2}是V的一個(gè)劃分.任取v1∈V1,

v2∈V2,由于G是連通的,必存在一條路

v1…….

v2,在此路上必存在結(jié)點(diǎn)u和v,使得u∈V1,

v∈V2,且(u,v)是此路中的一條邊.充分性:已知對(duì)V的任何分成V1、V2的劃分,恒存在一條邊,(反證法)假設(shè)G不是連通的.則G至少有兩個(gè)連通分支G1、

G2,令V1=V(G1)

V2=V-V(G1),根據(jù)連通分支定義知,不存在端點(diǎn)分別屬于V1和V2的邊,與已知矛盾.所以G是連通的.V1V2uvv1

v2…..…..三.割集(CutSet)

割集在圖論中是個(gè)重要概念,在圖論的理論和應(yīng)用中,都具有重要地位.比如有交通圖:結(jié)點(diǎn)u,邊e就是至關(guān)重要的.割集就是使得原來連通的圖,變成不連通,需要?jiǎng)h去的結(jié)點(diǎn)集合或邊的集合.1.點(diǎn)割集與割點(diǎn):令G=<V,E>是連通無向圖,結(jié)點(diǎn)集合V1,V1V,如果刪去V1中所有結(jié)點(diǎn)后,G就變得不連通了,而刪去V1的任何真子集中的所有結(jié)點(diǎn),得到的子圖仍然連通.則稱V1是G的一個(gè)點(diǎn)割集.如果點(diǎn)割集V1中只有一個(gè)結(jié)點(diǎn),則稱此結(jié)點(diǎn)為割點(diǎn).

u

e右圖中:{b,f},{b,g},{f,k},{k,g}以及{a,d,i,l}是點(diǎn)割集.不存在割點(diǎn).2.點(diǎn)連通度:若G不是完全圖,定義:

k(G)=min{|V1||V1是G的點(diǎn)割集}為G的點(diǎn)連通度.

點(diǎn)連通度k(G)是表示使G不連通,至少要?jiǎng)h去的結(jié)點(diǎn)數(shù).

上例中k(G)=2

具有割點(diǎn)圖的點(diǎn)連通度k(G)=1gcbegcaiejdhlkgcabiejfdhlkjfhk

u

定理8-2.3:一個(gè)連通圖中結(jié)點(diǎn)v是割點(diǎn)的充分且必要條件是存在兩個(gè)結(jié)點(diǎn)u和w,使得從u到w的任何路都通過v.證明:略上邊是通過刪去結(jié)點(diǎn)的辦法使連通圖變得不連通的.也可以通過刪去邊的辦法使連通圖變得不連通.3.邊割集與割邊(橋)令G=<V,E>是連通無向圖,邊的集合E1,E1E,如果刪去E1中所有邊后,G就變得不連通了,而刪去E1的任何真子集中的所有邊,得到的子圖仍然連通.則稱E1是G的一個(gè)邊割集.如果邊割集E1中只有一條邊,則稱此邊為割邊,也稱之為橋.右圖中,e就是橋.

e4.邊連通度:若G不是平凡圖,定義:

λ(G)=min{|E1||E1是G的邊割集}為圖G的邊連通度.邊連通度λ(G)是表示使G不連通,至少要?jiǎng)h去的邊數(shù).顯然,如果G不是連通圖,則k(G)=λ(G)=0*定理8-2.4G是無向圖,則k(G)≤λ(G)≤δ(G)證明:當(dāng)G是不連通時(shí),顯然有k(G)=λ(G)=0≤δ(G)成立.當(dāng)G是連通時(shí):1)先證λ(G)≤δ(G)2)再證k(G)≤λ(G)四.有向圖的連通性

1.結(jié)點(diǎn)間的可達(dá)性:G=<G,E>是有向圖,u,v∈V,如果從

u到v有一條路,則稱從u到v可達(dá).右圖中:a可達(dá)b和d,但是a不可達(dá)c.

顯然結(jié)點(diǎn)間的可達(dá)關(guān)系,具有自反性和傳遞性.

2.結(jié)點(diǎn)u到v的距離:如果u可達(dá)v,可能從u到v有多條路,其中最短的路的長(zhǎng)度,稱之為從u到v的距離.記作d<u,v>.

上例中d<a,b>=1

d<a,d>=2d<a,a>=0d<b,c>=∞

3.可達(dá)性的性質(zhì):1).d<u,v>≥02)d<u,u>=03)d<u,v>+d<v,w>≥d<u,w>(如上圖的c,a,b)4)如果從u到v不可達(dá),則d<u,v>=∞(如b,c)5)如從u可達(dá)v,從v也可達(dá)u,但d<u,v>不一定等于d<v,u>(如a,d)dcab4.圖的直徑:

G是個(gè)有向圖,定義

為圖G的直徑.上圖中,圖的直徑D=∞(因?yàn)閐<b,c>=∞)5.強(qiáng)連通、單側(cè)連通和弱連通在簡(jiǎn)單有向圖G中,如果任何兩個(gè)結(jié)點(diǎn)間相互可達(dá),則稱G是強(qiáng)連通.如果任何一對(duì)結(jié)點(diǎn)間,至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá),則稱G是單側(cè)連通.如果將G看成無向圖后(即把有向邊看成無向邊)是連通的,則稱G是弱連通.(a)有回路adbca,強(qiáng)連通.(b)a到d,d到a,都不可達(dá)是弱連通.(c)單側(cè)連通.dcabD=max{d<u,v>}

u,v∈Vdcabdcabdcab(a)(b)(c)定理8-2.5:一個(gè)有向圖G是強(qiáng)連通的,當(dāng)且僅當(dāng)G中有一個(gè)回路,此回路至少包含每個(gè)結(jié)點(diǎn)一次.證明:充分性:顯然成立.因?yàn)槿绻鸊中有一個(gè)回路,它至少包含每個(gè)結(jié)點(diǎn)一次,就使得任何兩個(gè)結(jié)點(diǎn)間相互可達(dá),所以G是強(qiáng)連通的.必要性:如果G是強(qiáng)連通的,則任何兩個(gè)結(jié)點(diǎn)間相互可達(dá).所以可以構(gòu)造一個(gè)回路經(jīng)過所有結(jié)點(diǎn).否則必有一個(gè)回路不包含某個(gè)結(jié)點(diǎn)v,所以v與回路上的各結(jié)點(diǎn)都不相互可達(dá).這與G是強(qiáng)分圖矛盾.所以G必有回路至少包含每個(gè)結(jié)點(diǎn)一次.

所以可以應(yīng)用此定理判斷G是否為強(qiáng)連通,就是看它是否有包含每個(gè)結(jié)點(diǎn)的回路.6.強(qiáng)分圖、單側(cè)分圖和弱分圖在簡(jiǎn)單有向圖中,具有強(qiáng)連通的最大子圖,稱為強(qiáng)分圖.具有單側(cè)連通的最大子圖,稱為單側(cè)分圖.具有弱連通的最大子圖,稱為弱分圖.這些分圖用結(jié)點(diǎn)的集合表示.

例如,給定有向圖G,如圖所示:求它的強(qiáng)分圖、單側(cè)分圖和弱分圖.解:強(qiáng)分圖:由{a,g,h}{c}zj79fpz{e}{f}導(dǎo)出的子圖.單側(cè)分圖:由{a,g,h,b,f,d,e}{b,c,f,d,e}導(dǎo)出的子圖.弱分圖:G本身是弱分圖.

在有向圖中,每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)強(qiáng)分圖中efcdghab定理8-2.6在有向圖中,每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)強(qiáng)分圖中.證明:令G=<V,E>是有向圖,任取結(jié)點(diǎn)v∈V,令S是所有與v相互可達(dá)的結(jié)點(diǎn)集合,當(dāng)然v∈S∴S≠Φ,而S是一個(gè)強(qiáng)分圖,所以v必位于一個(gè)強(qiáng)分圖中.如果v位于兩個(gè)不同的強(qiáng)分圖S1、S2中,于是v與S1中每個(gè)結(jié)點(diǎn)相互可達(dá),v也與

S2中每個(gè)結(jié)點(diǎn)相互可達(dá),所以S1中每個(gè)結(jié)點(diǎn)都與S2中每個(gè)結(jié)點(diǎn)通過v相互可達(dá),這說明S1與S2是一個(gè)強(qiáng)分圖,與已知S1、S2是兩個(gè)不同的強(qiáng)分圖矛盾.所以每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)強(qiáng)分圖中.在給定的簡(jiǎn)單有向圖中找強(qiáng)分圖----回路中的結(jié)點(diǎn)構(gòu)成一個(gè)強(qiáng)分圖,不在回路中的結(jié)點(diǎn),自己構(gòu)成一個(gè)強(qiáng)分圖.作業(yè)P286(3)(5)(8)8-3.圖的矩陣表示圖的矩陣表示不僅是給出圖的一種表示方法,還可以通過這些矩陣討論有關(guān)圖的若干性質(zhì),更重要的是可以用矩陣形式將圖存入計(jì)算機(jī)中,在計(jì)算機(jī)中對(duì)圖作處理.這里主要討論圖的三種矩陣.一.鄰接矩陣這是以結(jié)點(diǎn)與結(jié)點(diǎn)之間的鄰接關(guān)系確定的矩陣.1.定義:設(shè)G=<V,E>是個(gè)簡(jiǎn)單圖,V={v1,v2,v3,…,vn

},一個(gè)n×n階矩陣A=(aij)稱為G的鄰接矩陣.其中:aij

={1vi與vj鄰接,即(vi,vj)∈E或<vi,vj>∈E0否則例如,給定無向圖G1和有向圖G2如圖所示:2.從鄰接矩陣看圖的性質(zhì):

無向圖:每行1的個(gè)數(shù)=每列1的個(gè)數(shù)=對(duì)應(yīng)結(jié)點(diǎn)的度

有向圖:每行1的個(gè)數(shù)=對(duì)應(yīng)結(jié)點(diǎn)的出度每列1的個(gè)數(shù)=對(duì)應(yīng)結(jié)點(diǎn)的入度v1

v5v4

v2

v3G1v3

v2

v4

v5v1

G23.鄰接矩陣的乘積在(A(G1))2中a342

=2表示從v3到v4有長(zhǎng)度為2的路有2條:

在(A(G1))3中a233

=6表示從v2到v3有長(zhǎng)度為3的路有6條:v2v1v2v3,v2v4v2v3,v2v3v2v3,v2v3v1v3,v2v3v5v3,v2v4v5v3.v1

v5v4

v2

v3G1v3v2v4,

v3v5v4定理8-3.1設(shè)G=<V,E>是簡(jiǎn)單圖,令V={v1,v2,v3,…,vn},G的鄰接矩陣(A(G))k中的第i行第j列元素aijk=m,表示在圖G中從vi到vj長(zhǎng)度為k的路有m條.可以用歸納法證明.(見教材P290)在實(shí)際應(yīng)用中,有時(shí)只關(guān)心從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路,而不關(guān)心路有多長(zhǎng),比如電話網(wǎng)絡(luò).這就促使我們定義可達(dá)矩陣.二.可達(dá)性矩陣1.定義:設(shè)G=<V,E>是個(gè)簡(jiǎn)單圖,V={v1,v2,v3,…,vn

},一個(gè)n×n階矩陣P=(pij)稱為G的可達(dá)性矩陣.其中:pij

={1vi到vj可達(dá),(至少有一條路)0否則2.求可達(dá)矩陣可以根據(jù)鄰接矩陣A求可達(dá)矩陣.設(shè)|V(G)|=n

令A(yù)(k)是將Ak中的非0元素都寫成1,而得到的只含有0和1的0-1矩陣.于是可達(dá)矩陣P為:

P=A∨A(2)∨A(3)∨...∨A(n)

其中∨是邏輯或.有兩種方法求P

方法1.按照矩陣相乘分別求出A(k)(k≥2),然后再∨.

方法2.用求傳遞閉包的Warshall算法,見P124.例如,G2如圖所示,求它的可達(dá)矩陣P.

v3

v2

v4

v5v1

G2

P=A∨A(2)∨A(3)∨A(4)∨A(5)3.用可達(dá)矩陣求強(qiáng)分圖.

以G2為例,從圖看出有兩個(gè)強(qiáng)分圖:{v1,v3}和{v2,v4,v5}下面看怎樣用P求強(qiáng)分圖.0010000010100100100100010A=1001001011011010001001001A(2)=0110101011100100100000010A(3)=1001001011011010001001001A(4)==A(2)A(5)=A(3)1111101011111110101101011P=v3

v2

v4

v5v1

G2先將P=(pij)轉(zhuǎn)置得PT=(pTij),如果vi與vj相互可達(dá),則

pij=pTij=1對(duì)P∧PT進(jìn)行初等變換,第2行與第3行交換,再第2列與第3列交換,最后得兩個(gè)強(qiáng)分圖:{v1,v3}和{v2,v4,v5}三.完全關(guān)聯(lián)矩陣此矩陣是按照結(jié)點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系確定的矩陣.1.無向圖的完全關(guān)聯(lián)矩陣1111101011111110101101011P=1010011111101001111111111PT=P∧PT=10100010111010001011010111100011000001110011100111初等變換得v1v3v2v4v51.無向圖的完全關(guān)聯(lián)矩陣1).定義:設(shè)G=<V,E>是個(gè)無向圖,V={v1,v2,v3,…,vm

},E={e1,e2,e3,…,en},一個(gè)m×n階矩陣M=(mij)稱為G的完全關(guān)聯(lián)矩陣.其中:2).從關(guān)聯(lián)矩陣看圖的性質(zhì):

a)每列只有二個(gè)1.(因?yàn)槊織l邊只關(guān)聯(lián)兩個(gè)結(jié)點(diǎn))

b)每行中1的個(gè)數(shù)為對(duì)應(yīng)結(jié)點(diǎn)的度數(shù).

c)如果兩列相同,則說明對(duì)應(yīng)的兩條邊是平行邊.mij

={1vi與ej關(guān)聯(lián)0

否則v1

v5v4

v2

v3e1e2e3e5e7e6e4

e1

e2e3e4e5

e6e7v11100000v21011100v30111010v40000101v50000011M=2.有向圖的完全關(guān)聯(lián)矩陣1).定義:設(shè)G=<V,E>是個(gè)簡(jiǎn)單有向圖,V={v1,v2,v3,…,vm

},E={e1,e2,e3,…,en},一個(gè)m×n階矩陣M=(mij)稱為G的完全關(guān)聯(lián)矩陣.其中:

2).從關(guān)聯(lián)矩陣看圖的性質(zhì):

a)每列只有一個(gè)1和一個(gè)-1.(每條邊有一個(gè)起點(diǎn)一個(gè)終點(diǎn))

b)每行中1的個(gè)數(shù)為對(duì)應(yīng)結(jié)點(diǎn)的出度.-1個(gè)數(shù)是結(jié)點(diǎn)入度mij

={1vi是ej的起點(diǎn)

-1vi是ej的終點(diǎn)

0

vi與ej不關(guān)聯(lián)

e1

e2e3e4e5

e6e7v1-1100000v210-10-100v30-11-10-10v40001101v5000001-1M=v1

v5v4

v2

v3e1e2e3e5e7e6e4本節(jié)重點(diǎn)掌握:圖的三個(gè)矩陣的求法由圖的矩陣,看圖的性質(zhì).作業(yè)P300(3)*8-4.帶權(quán)圖的最短路與關(guān)鍵路在實(shí)際應(yīng)用中,一些圖的邊上標(biāo)有數(shù)字,用以表示兩結(jié)點(diǎn)間的距離、或路費(fèi)等等.然后求兩點(diǎn)間的最短路徑.這是很有意義的問題.一.帶權(quán)圖(賦權(quán)圖)

1.定義:設(shè)G=<V,E,W>,是個(gè)圖,如果G的每條邊e上都標(biāo)有實(shí)數(shù)c(e)(c(e)∈W),稱這個(gè)數(shù)為邊e的權(quán),稱此圖為帶權(quán)圖.

規(guī)定:u,v∈V,邊(u,v)的權(quán)記作

c(u,v)1)c(u,u)=02)如果結(jié)點(diǎn)u與v之間無邊相連,則c(u,v)=∞

2.帶權(quán)圖的路長(zhǎng):結(jié)點(diǎn)u與v之間的路長(zhǎng)是指該路所包含的各邊權(quán)的總和.例如右圖中v1v2v3v6的路長(zhǎng)為12.3.帶權(quán)圖的兩點(diǎn)間距離:結(jié)點(diǎn)u與v之間的最短路的長(zhǎng)稱為結(jié)點(diǎn)u與v之間的距離.記作d(u,v).如果G是有向帶權(quán)圖,稱為結(jié)點(diǎn)u到v的距離,記作d<u,v>

例如上圖中d(v2,v5)=24.帶權(quán)圖中求一個(gè)結(jié)點(diǎn)到各點(diǎn)的最短路的算法:此算法是于1959年由E.W.Dijkstra提出的.基本思想:若使(u0,u1,u2,…,un-1,un)最短,就要使(u0,u1,u2,…,un-1)最短,即保證從u0到以后各點(diǎn)的路都是最短的.v6v5v4v1

v3v2365112336令圖G=<V,E,W>,集合SiVSi’=V-Si

,

令|V|=nSi={u|從u0到u的最短路已求出}

Si’={u’|從u0到u’的最短路未求出}Dijkstra算法:(求從u0到各點(diǎn)u的最短路長(zhǎng))第一步.置初值:d(u0,u0)=0d(u0,v)=∞(其中v≠u0)i=0S0={u0}第二步.若i=n-1則停.否則轉(zhuǎn)第三步第三步.對(duì)每個(gè)u’∈Si’

計(jì)算d(u0,u’)=min{d(u0,u’),d(u0,ui)+c(ui,u’)}

計(jì)算min{d(u0,u’)}

并用ui+1記下達(dá)到該最小值的那個(gè)結(jié)點(diǎn)u’

置Si+1=Si∪{ui+1} i=i+1轉(zhuǎn)第二步.ui∈Siu’∈Si’例.求右圖中從v1到v6的最短路1.置初值:u0=v1d(u0,u0)=0d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=∞2.3.i=0S0={v1}S0’={v2,v3,v4,v5,v6}d(u0,v2)=min{d(u0,v2),d(u0,u0)+c(u0,v2)}=min{∞,0+3}=3d(u0,v3)=min{d(u0,v3),d(u0,u0)+c(u0,v3)}=min{∞,0+∞}=∞d(u0,v4)=min{d(u0,v4),d(u0,u0)+c(u0,v4)}=min{∞,0+5}=5d(u0,v5)=min{d(u0,v5),d(u0,u0)+c(u0,v5)}=min{∞,0+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u0)+c(u0,v6)}=min{∞,0+∞}=∞min{3,∞,5,∞,∞}=3

ui+1=u1=v2,

實(shí)際已求出d(u0,v2)=3,路是u0v2v6v5v4v1

v3v2365113336i=1S1={v1,

v2}S1’={v3,v4,v5,v6}u1=v2d(u0,u1)=3d(u0,v3)=min{d(u0,v3),d(u0,u1)+c(u1,v3)}=min{∞,3+6}=9d(u0,v4)=min{d(u0,v4),d(u0,u1)+c(u1,v4)}=min{5,3+1}=4d(u0,v5)=min{d(u0,v5),d(u0,u1)+c(u1,v5)}=min{∞,3+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u1)+c(u1,v6)}=min{∞,3+∞}=∞min{9,4,∞,∞}=4

ui+1=u2=v4,實(shí)際已求出d(u0,v4)=4,路是u0v2v4v6v5v4v1

v3v2365113336i=2S2={v1,

v2,v4}S2’={v3,v5,v6}u2=v4d(u0,u2)=4d(u0,v3)=min{d(u0,v3),d(u0,u2)+c(u2,v3)}=min{9,4+3}=7d(u0,v5)=min{d(u0,v5),d(u0,u2)+c(u2,v5)}=min{∞,4+1}=5d(u0,v6)=min{d(u0,v6),d(u0,u2)+c(u2,v6)}=min{∞,4+∞}=∞min{7,5,∞}=5

ui+1=u3=v5,實(shí)際已求出d(u0,v5)=5,路是u0v2v4v5v6v5v4v1

v3v2365113336i=3S3={v1,

v2,v4,v5}S3’={v3,v6}u3=v5d(u0,u3)=5d(u0,v3)=min{d(u0,v3),d(u0,u3)+c(u3,v3)}=min{7,5+3}=7d(u0,v6)=min{d(u0,v6),d(u0,u3)+c(u3,v6)}=min{∞,5+6}=11min{7,11}=7

ui+1=u4=v3,實(shí)際已求出d(u0,v3)=7,路是u0v2v4v3i=4S3={v1,

v2,v4,v5,

v3}S3’={v6}u4=v3d(u0,u4)=7d(u0,v6)=min{d(u0,v6),d(u0,u4)+c(u4,v6)}=min{11,7+3}=10min{10}=10

ui+1=u5=v6,實(shí)際已求出d(u0,v6)=10,路是u0v2v4v3v6i=5(n-1)時(shí)算法停止.v6v5v4v1

v3v2365113336二.求關(guān)鍵路徑問題實(shí)施一項(xiàng)工程計(jì)劃時(shí),若將整個(gè)工程分成若干個(gè)工序,有些工序可以同時(shí)實(shí)施,有些工序必須在另一些工序完成之后才能實(shí)施,工序之間的次序關(guān)系用有帶權(quán)的向圖表示,這種有向圖稱為PERT圖(計(jì)劃評(píng)審技術(shù)圖).(ProgramEvaluationandReviewTechnique)1.PERT圖定義:

D=<V,E,W>是有向帶權(quán)圖,|V|=n,如果滿足:(1).D是簡(jiǎn)單圖.(2).D中無回路.(3).有一個(gè)結(jié)點(diǎn)入度為0,稱此結(jié)點(diǎn)為發(fā)點(diǎn);有一個(gè)結(jié)點(diǎn)出度為0,稱此結(jié)點(diǎn)為收點(diǎn).(4).邊<vi,vj>帶的權(quán)記作wij,通常表示時(shí)間.稱此圖D為PERT圖.如右圖就是個(gè)PERT圖.在PERT圖中只要是找出關(guān)鍵路徑,即是影響工程工期的關(guān)鍵路徑.就是通過求從發(fā)點(diǎn)到收點(diǎn)的一條最長(zhǎng)路徑,通過求各個(gè)結(jié)點(diǎn)的最早完成時(shí)間,來求關(guān)鍵路徑.為此先給出兩個(gè)概念:

2.結(jié)點(diǎn)v的先驅(qū)元集:令D=<V,E>為有向圖,v∈V,稱集合為v的先驅(qū)元集.3.結(jié)點(diǎn)v的后繼元集:令D=<V,E>為有向圖,v∈V,稱集合為v的后繼元集..v8v5v4v1

v7v214203461v6v323144

4.最早完成時(shí)間:自發(fā)點(diǎn)(記作v1)開始沿最長(zhǎng)路徑(按權(quán)計(jì)算)到達(dá)vi,稱為vi的最早完成時(shí)間,記作TE(vi),i=1,2,…n

顯然TE(v1)=0,

收點(diǎn)vn最早完成時(shí)間TE(vn)就是從v1到vn的最長(zhǎng)路徑的長(zhǎng).

5.最晚完成時(shí)間:在保證收點(diǎn)vn的最早完成時(shí)間不增加的條件下,自發(fā)點(diǎn)(記作v1)最遲到達(dá)vi的時(shí)間,稱為vi的最晚完成時(shí)間,記作TL(vi),i=1,2,…n

顯然TL(vn)=TE(vn),v1

vj

vi

wijTL(vj)TL(vi)v1

vj

vi

wjiTE(vj)TE(vi)

6.緩沖時(shí)間:稱TS(vi)=TL(vi))－TE(vi)i=1,2,…n為vi的緩沖時(shí)間.

7.關(guān)鍵路徑:就是各個(gè)結(jié)點(diǎn)的緩沖時(shí)間均為0的路徑.可見在關(guān)鍵路徑上,如果一個(gè)工序增加了時(shí)間t,則整個(gè)工程就推遲了時(shí)間t.所以才稱之為關(guān)鍵路徑.例如,求右圖的關(guān)鍵路徑(1)求各個(gè)結(jié)點(diǎn)的最早完成時(shí)間:TE(v1)=0TE(v2)=max{0+1}=1(v1)TE(v3)=max{0+2,1+0}=2(v1v2)TE(v4)=max{0+3,2+2}=4(v1v3)TE(v5)=max{1+3,4+4}=8(v2v4)TE(v6)=max{2+4,8+1}=9(v3v5)TE(v7)=max{1+4,2+4}=6(v2v3)TE(v8)=max{9+1,6+6}=12(v6v7)v8v5v4v1

v7v214203461v6v323144(2)求各個(gè)結(jié)點(diǎn)的最晚完成時(shí)間:TL(v8)=TE(v8)=12TL(v7)=min{12-6}=6(v8)TL(v6)=min{12-1}=11(v8)TL(v5)=min{11-1}=10(v6)TL(v4)=min{10-4}=6(v5)TL(v3)=min{6-2,11-4,6-4}=2(v4v6v7)TL(v2)=min{2-0,10-3,6-4}=2(v3v5v7)TL(v1)=min{2-1,2-2,6-3}=0(v2v3v4)(3)求各個(gè)結(jié)點(diǎn)的緩沖時(shí)間TS(vi)=TL(vi)-TE(vi)iv1v2v3v4v5v6v7v8TL(vi)02261011612TE(vi)012489612TS(vi)010

22200v8v5v4v1

v7v214203461v6v323144關(guān)鍵路徑為:v1v3v7v88-5.歐拉圖與漢密爾頓圖這里主要討論圖的遍歷問題,一個(gè)是遍歷過程中要求經(jīng)過的所有邊都不同;一個(gè)是遍歷過程中要求經(jīng)過的所有結(jié)點(diǎn)都不同.歐拉在1736年發(fā)表了第一篇關(guān)于圖論的論文,就是就七橋問題.ABCDABCDe1e5e7e6e3e4e2一.歐拉圖:

1.歐拉路:在無孤立結(jié)點(diǎn)的圖G中,如果存在一條路,它經(jīng)過圖中每條邊一次且僅一次,稱此路為歐拉路.

2.歐拉回路:在無孤立結(jié)點(diǎn)的圖G中,若存在一條回路,它經(jīng)過圖中每條邊一次且僅一次,稱此回路為歐拉回路.稱此圖為歐拉圖,或E圖.(Euler)

在G1中:有歐拉路:

acbefgdcfh在G2中:有歐拉回路:

v1v2v3v4v5v2v4v6v5v3v1如何判定一個(gè)圖中是否有歐拉路,或有歐拉回路?v1

v5v4

v2

v3

v6a

ge

b

d

hc

f

G1G2abcd14323.有歐拉路與有歐拉回路的判定:定理8-5.1:無向圖G具有歐拉路,當(dāng)且僅當(dāng)G是連通的,且有零個(gè)或兩個(gè)奇數(shù)度的結(jié)點(diǎn).*證明:必要性,設(shè)G有歐拉路.(見教材P302)充分性,(證明的過程就是一個(gè)構(gòu)造歐拉路的過程)如果G有兩個(gè)奇數(shù)度結(jié)點(diǎn):就從一個(gè)奇數(shù)度結(jié)點(diǎn)出發(fā),每當(dāng)?shù)竭_(dá)一個(gè)偶數(shù)度結(jié)點(diǎn),必然可以再經(jīng)過另一條邊離開此結(jié)點(diǎn),如此重復(fù)下去,經(jīng)過所有邊后到達(dá)另一個(gè)奇數(shù)度結(jié)點(diǎn)如果G無奇數(shù)度結(jié)點(diǎn),則可以從任何一個(gè)結(jié)點(diǎn)出發(fā),去構(gòu)造一條歐拉路.推論:無向圖G具有歐拉回路,當(dāng)且僅當(dāng)G是連通的,且所有結(jié)點(diǎn)的度都是偶數(shù).abcd1243從此推論得知,七橋問題的圖不是歐拉圖.4.求歐拉回路的算法:ABCDe1e5e7e6e3e4e2G有E回路?停止N選結(jié)點(diǎn)v

以v為起點(diǎn)找閉跡E1

E1包含所有邊Y打印E1在G-E1中找一個(gè)閉跡E2使E1與E2至少有一個(gè)公共點(diǎn)N以某公共點(diǎn)為起、末點(diǎn),對(duì)

E1∪E2中的邊重新排序得新的閉跡C

E1:=CY用上述算法求右圖中歐拉回路.此圖中所有結(jié)點(diǎn)度均為偶數(shù),所以有歐拉回路.a)選以1為起點(diǎn)的閉跡E1:1261b)E1不包含所有邊.c)在G-E1中找新閉跡E2:6356(6是E1與E2的公共點(diǎn))d)以公共點(diǎn)6為起點(diǎn),對(duì)E1∪E2中的邊排序:C=6356126e)E1:=Cf)E1不包含所有邊.g)在G-E1中找新閉跡E2:52345(5是E1與E2的公共點(diǎn))h)以公共點(diǎn)5為起點(diǎn),對(duì)E1∪E2中的邊排序:

C=52345612635i)E1:=Cj)E1包含所有邊.k)打印E1=52345612635

l)停止.16253416

2534歐拉路與歐拉回路問題,也稱一筆畫問題.*5.歐拉圖的應(yīng)用----計(jì)算機(jī)鼓輪的設(shè)計(jì)早期向計(jì)算機(jī)輸入數(shù)據(jù),為簡(jiǎn)單,以輸入八進(jìn)制數(shù)為例(0,1,2,3,4,5,6,7,即000,001,010,011,100,101,110,111)鼓輪表面分成23等分,每一等分分別用絕緣體或?qū)w組成,絕緣部分輸出0,導(dǎo)體部分輸出1.有三個(gè)觸點(diǎn)分別與三個(gè)部分接觸,以讀取三個(gè)數(shù)字.如圖所示:轉(zhuǎn)動(dòng)鼓輪,分別輸出8個(gè)數(shù):000,001,010,011,100,101,110,111下面介紹此鼓輪的設(shè)計(jì)過程:00001111

此輪的設(shè)計(jì):以兩位二進(jìn)制數(shù)V={00,01,10,11}為結(jié)點(diǎn),畫帶權(quán)圖(即邊上標(biāo)有數(shù)字--稱為邊的權(quán)),從任何a1a2∈V結(jié)點(diǎn)畫有向邊,標(biāo)的權(quán)0(或1),該邊指向結(jié)點(diǎn)a20(或a21),于是構(gòu)成邊a1a20,(或a1a21),這八條邊分別表示八個(gè)二進(jìn)制數(shù):000,001,010,011,100,101,110,111從此圖上取一個(gè)回路:e0e1e2e5e3e7e6e4將上述各邊的末位數(shù)字寫成序列:01011100,于是就按照此序列將鼓輪進(jìn)行加工,標(biāo)0部分用絕緣體,標(biāo)1部分用導(dǎo)體.001001111e0=000e1=001e3=011e4=100e5=101e2=010110=e6e7=11100001111

二.漢密爾頓圖(H圖)(Hamilton圖)Hamilton是英國(guó)數(shù)學(xué)家,在1959年,他提出Hamilton回路.H圖起源于一種游戲,這個(gè)游戲就是所謂周游世界問題.例如,某個(gè)城市的街道如圖所示:該城市的所有交叉路口都有形象各異的精美的雕塑,吸引著許多游客,人人都想找到這樣的路徑:游遍各個(gè)景點(diǎn)再回到出發(fā)點(diǎn)----H回路.1.定義:設(shè)G=<V,E>是個(gè)無向有限圖,

漢密爾頓路:通過G中每個(gè)結(jié)點(diǎn)恰好一次的路.

漢密爾頓回路(H回路):通過G中每個(gè)結(jié)點(diǎn)恰好一次的回路.

漢密爾頓圖(H圖):具有漢密爾頓回路(H回路)的圖.例如右圖中,就是H圖,因?yàn)樗蠬回路:12345612.漢密爾頓圖的判定:到目前為止并沒有判定H圖的充分和必要條件.定理8-5.2(充分條件):G是完全圖,則G是H圖.證明:略定理8-5.3(充分條件)設(shè)G是有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,若對(duì)G中每對(duì)結(jié)點(diǎn)度數(shù)之和大于n-1(n),則G有一條H路(H回路)證明:先證明G是連通的.(反證法)見書P307

再構(gòu)造H路(H回路)162534

K2K3K4K5在圖G1中,滿足充分條件Δ(G)=4δ(G)=2任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于5,所以是H圖.

注意:上述條件只是充分條件,而不是必要條件,即不滿足這個(gè)條件的,也可能有H路.例如:在圖G2中,并不滿足任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于3,但是卻有H路.15243dc

abG1G2定理8-5.4:(必要條件)若圖G=<V,E>有H回路,則對(duì)V的任何非空子有限集S,均有W(G-S)≤|S|,其中W(G-S)是從G中刪去S中所有結(jié)點(diǎn)及與這些結(jié)點(diǎn)關(guān)聯(lián)的邊所得到的子圖的連通分支數(shù).證明:設(shè)C是圖G的一條H回路,則對(duì)于V的任何非空子集S,在C中刪去S中任意一個(gè)結(jié)點(diǎn)v1后,則C-v1仍是連通的路,若再刪去S中的另一個(gè)結(jié)點(diǎn)v2,則W(C-v1-

v2)≤2,若|S|=n則刪去S中的n個(gè)結(jié)點(diǎn),有W(C-v1-

v2-...-vn)≤n,所以W(C-v1-

v2-...-vn)≤|S|.因?yàn)镃是H回路,所以它包含了G的所有結(jié)點(diǎn),即C是G的生成子圖.所以C-S也是G-S的生成子圖,故W(G-S)≤|S|.

用此定理可以判斷一個(gè)圖不是H圖.如右圖G,取S={c}不滿足W(G-S)≤|S|.c

ebad3.用“最鄰近法”求H回路如果已經(jīng)確定圖G有H回路.a).任選一個(gè)初始結(jié)點(diǎn)u,找一個(gè)最鄰近(或權(quán)最小)的結(jié)點(diǎn)x.b).設(shè)x是新加入到這條路的結(jié)點(diǎn),再從不在此路上的結(jié)點(diǎn)中找到一個(gè)與x鄰近(或權(quán)最小)的結(jié)點(diǎn),加到此路中.c).重復(fù)b),直到G中所有結(jié)點(diǎn)都在此路上.d).最后再回到起點(diǎn),構(gòu)成回路.就是H回路.例如右圖初始結(jié)點(diǎn)為a,

逐漸選鄰近結(jié)點(diǎn)c,e,d,b,a.得H回路acedba.此回路的總權(quán)為:20但是對(duì)帶權(quán)圖來說,此方法求的H回路不一定是最短的.例如,實(shí)際上此圖最短的H回路是acebda總權(quán)為17abecd12345678910本節(jié)重點(diǎn)掌握:歐拉路及歐拉回路的判定,能求歐拉路和歐拉回路.

H路及H回路的判定,能求H路和H回路.以及歐拉圖和漢密爾頓圖的應(yīng)用.

作業(yè)P311(1)(2)(6)8-6二部圖BipartiteGraph

在實(shí)際應(yīng)用中,有些如對(duì)策、二人對(duì)弈、工作分配等問題,例如有A,B,C,D四個(gè)人,有a,b,c,d,e五種工作,如果某人可以做某種工作,則它們之間連一直線.請(qǐng)給他們安排工作.1.定義:令G=<V,E>是無向圖,如果可以將V劃分成兩個(gè)子集V1,V2,使得任何邊(vi,vj)∈E,vi∈V1,vj∈V2,則稱G是二部圖,也稱二分圖.并稱V1,V2是G的互補(bǔ)的結(jié)點(diǎn)子集.DCABcbaed2.完全二部圖:令G=<V,E>是以V1,V2為互補(bǔ)的結(jié)點(diǎn)子集的二部圖,如果V1中的每個(gè)結(jié)點(diǎn)都與V2中每個(gè)結(jié)點(diǎn)相鄰接,則稱G是完全二部圖.如果|V1|=m,|V2|=n

則G記作Km,n

而下面兩個(gè)圖,就是不可以畫成二部圖.V1={1,3}V2={2,4}?,

V1={1,3,4}?V2={2,5}afbecdceafbd12431342K2,2K3,312433125413425K2,33.二部圖的判定:定理8-6.1

G=<V,E>是二部圖當(dāng)且僅當(dāng)它的所有回路的長(zhǎng)度都是偶數(shù).證明:必要性:假設(shè)G是個(gè)以V1,V2為互補(bǔ)的結(jié)點(diǎn)子集的二部圖,設(shè)任意長(zhǎng)度為n的回路:vi0vi1vi2,…,vin-1vi0,假設(shè)vi0vi2vi4,…,vin-2∈V1,vi1vi3vi5,…,vin-1∈V2,可見n-1是奇數(shù),所以n是偶數(shù).充分性:設(shè)G的每個(gè)回路長(zhǎng)度均為偶數(shù),a)設(shè)G是連通的.定義結(jié)點(diǎn)集合:

V1={vi|vi和某個(gè)固定結(jié)點(diǎn)v之間的距離為偶數(shù)}

V2=V-V1={vi|vi和某個(gè)固定結(jié)點(diǎn)v之間的距離為奇數(shù)}

下面證明E中任何邊,其端點(diǎn)分別屬于V1和V2.(用反證法)假設(shè)有一條邊(vi,vj)∈E,使得vi∈V1,

vj∈V1

由V1的定義可知:結(jié)點(diǎn)v到vi有最短路長(zhǎng)為m(是偶數(shù)),v到vj有最短路長(zhǎng)為n(是偶數(shù)),所以再加上邊(vi,vj),就得到一條長(zhǎng)度為(m+n+1)的回路,可是此回路長(zhǎng)為奇數(shù),與已知條件矛盾.所以vi和vj不能屬于同一個(gè)結(jié)點(diǎn)子集.

類似地,假設(shè)有一條邊(vi,vj)∈E,使得vi∈V2,

vj∈V2,由V2的定義可知:結(jié)點(diǎn)v到vi有最短路長(zhǎng)為m(是奇數(shù)),v到vj有最短路長(zhǎng)為n(是奇數(shù)),所以再加上邊(vi,vj),就得到一條長(zhǎng)度為(m+n+1)的回路,可是此回路長(zhǎng)為奇數(shù),與已知條件矛盾.所以vi和vj不能屬于同一個(gè)結(jié)點(diǎn)子集.

G是個(gè)以V1,V2為互補(bǔ)的結(jié)點(diǎn)子集的二部圖,

b)如果G不是連通圖時(shí),可以對(duì)G的每個(gè)分圖,重復(fù)上述證明,得到同樣結(jié)論.最后得,G必是二部圖.

vvi

vjm