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

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

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

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

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

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

V={A,B,C,D}

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

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

5372一.

圖的概念

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

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

是G的邊的集合.有時簡記成E.

結(jié)點(Vertices):用

表示,旁邊標上該結(jié)點的名稱.邊(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é)點的相對位置不同,邊的曲直、長短無關(guān)緊要.鄰接點:與一邊關(guān)聯(lián)的兩個結(jié)點.u

va

b

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

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

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

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

u

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

即此圖的邊的集合E=Φ

b

c

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

G:

四.簡單圖與多重圖

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

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

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

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

2.無向圖的結(jié)點度序列:令G=<V,E>是無向圖,V={v1,v2,v3,…,vn},則稱:(der(v1),der(v2),der(v3),…,der(vn))為圖G的結(jié)點度序列.例如上圖的結(jié)點度序列為:(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每個無向圖所有結(jié)點度總和等于邊數(shù)的2倍.即證明:因為圖中每條邊關(guān)聯(lián)兩個結(jié)點,因此每條邊給予它所關(guān)聯(lián)的兩個結(jié)點的度各是1,即一條邊對應(yīng)的度數(shù)是2,所以整個圖的度數(shù)總和為邊數(shù)的2倍.定理8-1.2(握手定理)每個無向圖中,奇數(shù)度的結(jié)點必為偶數(shù)個.(一次集會中,與奇數(shù)個人握手的人,必是偶數(shù)個.)證明:令G=<V,E>是無向圖,將V分成兩個子集V1和V2,其中V1---是度數(shù)是奇數(shù)的結(jié)點集合,

V2---是度數(shù)是偶數(shù)的結(jié)點集合而是偶數(shù).所以也是偶數(shù),于是奇數(shù)度的結(jié)點數(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中,如果Δ(G)=δ(G)=k則稱G為k-正則圖.課堂練習:1.下面哪些數(shù)的序列,可能是一個圖的度數(shù)序列?如果可能,請試畫出它的圖.哪些可能不是簡單圖?

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

1.

a)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4)解:a)不是,因為有三個數(shù)字是奇數(shù).

b)是.

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

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

七.有向圖結(jié)點的出度和入度:(indegreeoutdegree)G=<V,E>是有向圖,v∈Vv的出度:從結(jié)點v射出的邊數(shù).記作deg+(v)或dego(v)v的入度:射入結(jié)點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é)點的出度之和等于入度之和.證明:因為圖中每條邊對應(yīng)一個出度和一個入度.所以所有結(jié)點的出度之和與所有結(jié)點的入度之和都等于有向邊數(shù).必然有所有結(jié)點的出度之和等于入度之和.abcd八.完全圖1.無向完全圖定義:G是個簡單圖,如果每對不同結(jié)點之間都有邊相連則稱G是個無向完全圖.如果G有n個結(jié)點,則記作Kn.定理8-1.4無向完全圖Kn,有邊數(shù)證明:因為Kn中每個結(jié)點都與其余n-1個結(jié)點關(guān)聯(lián),即每個結(jié)點的度均為n-1,所以Kn的所有結(jié)點度數(shù)總和為n(n-1),設(shè)邊數(shù)為|E|,于是n(n-1)=2|E|所以|E|=

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

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

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

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

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

所以有n個結(jié)點的有向完全圖,有邊數(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的生成子圖.十.補圖由G的所有結(jié)點和為使G變成完全圖,所需要添加的那些邊組成的圖,稱之為G相對完全圖的補圖,簡稱G的補圖,記作.G

K5

G

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

abecd13452

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

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

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

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

v3

v2v1

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

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

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

v3

v2v1

v0e1e2e3e4e5e6cbad

v3

v2v1

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

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

v3

v2v1

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

vs-1

vi+1

vt+1

vs

=vt

vs+1vi

vt-1

vj

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

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

R={<u,v>|u和v是連通的}顯然R具有自反、對稱和傳遞性.于是可以求商集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對V的商集中有等價類V1,V2,V3,…,Vn,這n個等價類構(gòu)成的n個子圖分別記作G(V1),G(V2),G(V3),…,G(Vn),并稱它們?yōu)镚的連通分支.并用W(G)表示G中連通分支數(shù).下邊例中W(G1)=3W(G2)=2W(G3)=14.連通圖:如果一個圖G只有一個連通分支(W(G)=1),則稱G是連通圖.

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

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

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

v1…….

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

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

G2,令V1=V(G1)

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

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

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

u

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

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

點連通度k(G)是表示使G不連通,至少要刪去的結(jié)點數(shù).

上例中k(G)=2

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

u

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

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

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

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

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

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

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

上例中d<a,b>=1

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

3.可達性的性質(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<u,v>=∞(如b,c)5)如從u可達v,從v也可達u,但d<u,v>不一定等于d<v,u>(如a,d)dcab4.圖的直徑:

G是個有向圖,定義

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

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

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

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

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

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

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

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

無向圖:每行1的個數(shù)=每列1的個數(shù)=對應(yīng)結(jié)點的度

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

v5v4

v2

v3G1v3

v2

v4

v5v1

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

=2表示從v3到v4有長度為2的路有2條:

在(A(G1))3中a233

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

v5v4

v2

v3G1v3v2v4,

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

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

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

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

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

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

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

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

v3

v2

v4

v5v1

G2

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

以G2為例,從圖看出有兩個強分圖:{v1,v3}和{v2,v4,v5}下面看怎樣用P求強分圖.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相互可達,則

pij=pTij=1對P∧PT進行初等變換,第2行與第3行交換,再第2列與第3列交換,最后得兩個強分圖:{v1,v3}和{v2,v4,v5}三.完全關(guān)聯(lián)矩陣此矩陣是按照結(jié)點與邊之間的關(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>是個無向圖,V={v1,v2,v3,…,vm

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

a)每列只有二個1.(因為每條邊只關(guān)聯(lián)兩個結(jié)點)

b)每行中1的個數(shù)為對應(yīng)結(jié)點的度數(shù).

c)如果兩列相同,則說明對應(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>是個簡單有向圖,V={v1,v2,v3,…,vm

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

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

a)每列只有一個1和一個-1.(每條邊有一個起點一個終點)

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

={1vi是ej的起點

-1vi是ej的終點

0

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

e1

e2e3e4e5

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

v5v4

v2

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

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

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

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

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

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

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

,

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

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

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

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

并用ui+1記下達到該最小值的那個結(jié)點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,

實際已求出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,實際已求出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,實際已求出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,實際已求出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,實際已求出d(u0,v6)=10,路是u0v2v4v3v6i=5(n-1)時算法停止.v6v5v4v1

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

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

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

v7v214203461v6v323144

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

顯然TE(v1)=0,

收點vn最早完成時間TE(vn)就是從v1到vn的最長路徑的長.

5.最晚完成時間:在保證收點vn的最早完成時間不增加的條件下,自發(fā)點(記作v1)最遲到達vi的時間,稱為vi的最晚完成時間,記作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.緩沖時間:稱TS(vi)=TL(vi))－TE(vi)i=1,2,…n為vi的緩沖時間.

7.關(guān)鍵路徑:就是各個結(jié)點的緩沖時間均為0的路徑.可見在關(guān)鍵路徑上,如果一個工序增加了時間t,則整個工程就推遲了時間t.所以才稱之為關(guān)鍵路徑.例如,求右圖的關(guān)鍵路徑(1)求各個結(jié)點的最早完成時間: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)求各個結(jié)點的最晚完成時間: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)求各個結(jié)點的緩沖時間TS(vi)=TL(vi)-TE(vi)iv1v2v3v4v5v6v7v8TL(vi)02261011612TE(vi)012489612TS(vi)010

22200v8v5v4v1

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

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

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

在G1中:有歐拉路:

acbefgdcfh在G2中:有歐拉回路:

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

v5v4

v2

v3

v6a

ge

b

d

hc

f

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

以v為起點找閉跡E1

E1包含所有邊Y打印E1在G-E1中找一個閉跡E2使E1與E2至少有一個公共點N以某公共點為起、末點,對

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

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

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

l)停止.16253416

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

則G記作Km,n

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

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

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

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

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

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

vj∈V1

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

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

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

G是個以V1,V2為互補的結(jié)點子集的二部圖,

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

vvi

vjm