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

1、第八章 圖論,一. 圖的概念 一個(gè)圖 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),8-1

2、. 圖的基本概念,在圖中, 結(jié)點(diǎn)的相對(duì)位置、邊的曲直、長(zhǎng)短無關(guān)緊要.鄰接點(diǎn): 與一邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn). 鄰接邊: 關(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). 零圖:僅由一些孤立結(jié)點(diǎn)構(gòu)成的圖.

3、 即此圖的邊的集合E=Φ 平凡圖:僅由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的零圖. |V(G)|=1, |E(G)|=0 ?u,四. 簡(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ù)

4、,稱之為結(jié)點(diǎn)v的度. 記作 deg(v).(或d(v)).deg(a)=3 deg(b)=5 deg(c)=4 deg(d)=2 一個(gè)環(huán)給結(jié)點(diǎn)的度是2. 2.圖的結(jié)點(diǎn)度序列:令G=是圖, 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) :

5、G=是圖, Δ(G) =max{deg(v)|v∈G} δ(G) =min{deg(v)|v∈G},4. 定理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

6、=是圖,將V分成兩個(gè)子集V1 和V2,其中 V1 ---是度數(shù)是奇數(shù)的結(jié)點(diǎn)集合, V2 ---是度數(shù)是偶數(shù)的結(jié)點(diǎn)集合 也是偶數(shù), 于是奇數(shù)度的結(jié)點(diǎn)數(shù)是偶數(shù).,∑deg(v)=2|E|v∈V,∑deg(v) + ∑deg(v) =2|

7、E|v∈V1 v∈V2,而∑deg(v)是偶數(shù)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.已知

8、無向簡(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) 可能是,如下圖所示:2.解:已知邊數(shù)|E|=10, ∑deg(v)=2|E|=20其中有4個(gè)3度結(jié)點(diǎn)

9、, 余下結(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)的出度和入度:(in degree out degree) G=是有向圖,v∈V v的出度: 從結(jié)點(diǎn)v發(fā)出的邊數(shù). 記作deg+(v) 或 dego(v) v的入度: 指向結(jié)點(diǎn)v的邊數(shù). 記作deg-(v)

10、或 degi(v)degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0定理8-1.3 G=是有向圖, 則G的所有結(jié)點(diǎn)的出度之和等于入度之和.證明: 因?yàn)閳D中每條邊對(duì)應(yīng)一個(gè)出度和一個(gè)入度. 所以所有結(jié)點(diǎn)的出度之和與所有結(jié)點(diǎn)的入度之和都等于有向邊數(shù).必然有所有結(jié)點(diǎn)的出度之和等于

11、入度之和.,八. 完全圖1.無向完全圖 定義:G是個(gè)簡(jiǎn)單圖, 如果每對(duì)不同結(jié)點(diǎn)之間都有邊相連則稱G是個(gè)完全圖. n個(gè)結(jié)點(diǎn)的無向完全圖G記作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|=,2. 有向圖的完全圖 (注:這里的定義與教材不

12、同) 1).有向簡(jiǎn)單完全圖:G是個(gè)有向簡(jiǎn)單圖,如果任何兩個(gè)不同結(jié)點(diǎn)之間都有相互連接的邊,則稱它是有向簡(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)之間都有相互連接的邊,則稱它是有向完全圖. 其圖形如下:,所以有n個(gè)結(jié)點(diǎn)

13、的有向完全圖, 有邊數(shù) n2.九.子圖和生成子圖1.子圖:設(shè)G=是圖,如果G’=且V’?V, V’≠Φ, E’?E, 則稱G’是G的子圖.可見G1,G2,G3都是K5的子圖.,2. 生成子圖設(shè)G=是圖, G’=, G’是G的子圖,如果V’=V, 則稱G’是G的生成子圖.上例中, G1是K5的生成子圖.十. 補(bǔ)圖由G的所有結(jié)點(diǎn)和為使G變成完全圖,所需要添加的那些邊組成的圖, 稱之為G相對(duì)完全圖的補(bǔ)圖,簡(jiǎn)稱G的補(bǔ)圖

14、,記作,十一.相對(duì)補(bǔ)圖設(shè)G1=是圖G=的子圖,如果有G2= 使得E2=E-E1且V2中僅包含E2中的邊所關(guān)聯(lián)的結(jié)點(diǎn),則稱G2是G1相對(duì)G的補(bǔ)圖.可見G1是G3相對(duì)G的補(bǔ)圖. G3也是G1相對(duì)G的補(bǔ)圖.而G2不是G3相對(duì)G的補(bǔ)圖(多了一個(gè)結(jié)點(diǎn)).但是G3是G2相對(duì)G的補(bǔ)圖.可見: 相對(duì)補(bǔ)圖無相互性.,十二. 圖的同構(gòu)設(shè)G=和G’=是圖,如果存在雙射f:V?V’ 且任何vi,vj∈V,若邊(vi,vj)∈E,

15、當(dāng)且僅當(dāng) 邊(f(vi),f(vj))∈E’,(或若邊∈E,當(dāng)且僅當(dāng) 邊∈E’),則稱G與G’同構(gòu),記作G≌G’. (同構(gòu)圖要保持邊的“關(guān)聯(lián)”關(guān)系)例如:右邊所示的兩個(gè)圖:G= G’=構(gòu)造映射f:V?V’兩個(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ù)相等.,下面是否同構(gòu)的圖?右面兩個(gè)圖不同構(gòu):左圖中四個(gè)3度結(jié)點(diǎn)構(gòu)成四邊形,而右圖

16、則不然.,練習(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ì),

17、 一定要司機(jī)選一條最短的路. 到博覽會(huì)后, 最好選一條這樣到路徑,使得每個(gè)展臺(tái)都參觀一次后,再回到原來存包處. 這就是路與回路的問題.一. 路的概念 1.路的定義: 給定圖G=設(shè)v0 ,v1,v2,,…,vn∈V, e1,e2,,…,en∈E 其中ei是關(guān)聯(lián)vi-1 ,vi的邊, 則稱結(jié)點(diǎn)和邊的交叉序列v0 e1v1 e2v2…envn是連接v0到vn的路. v0是此路的起點(diǎn),vn是此路的終點(diǎn). 路中含有的邊數(shù)

18、n稱之為路的長(zhǎng)度.例如上圖中 v0 e2v3 e6v2是一條長(zhǎng)度為2的路.,如果圖是個(gè)簡(jiǎn)單圖, 則路可以只用結(jié)點(diǎn)序列表示. 如右圖中, 路:abcad如果圖是個(gè)有向圖, 則路可以只用邊序列表示. 如右邊有向圖中 e1 e5e2e3 e6 是一條路.2. 回路:如果一條路的起點(diǎn)和終點(diǎn)是一個(gè)結(jié)點(diǎn),則稱此路是一個(gè)回路. 如右圖中 L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0

19、 e1v1 e5v3e2v03. 跡與閉跡 如果一條路中,所有邊都不同,則稱此路為跡. 如果一條回路中,所有邊都不同,則稱此回路為閉跡.,4. 通路與圈如果一條路中,所有結(jié)點(diǎn)都不同,則稱此路為通路.如果一條回路中,除起點(diǎn)和終點(diǎn)外,其余結(jié)點(diǎn)都不同,則稱此回路為圈.例如右圖中:L1=v0 e1v1 e5v3 e6v2e4v0 L2= v0 e1v1 e5v3e2v0L3=v0 e1v1 e5v3 e2v0 e3v

20、3 e6v2e4v0 L1和L2是閉跡, 也是圈.L3是閉跡,而不是圈.,定理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&

21、gt;s)于是此路為:從圖看出,此路中有一個(gè)從vs到vt的回路, 此回路中,有t-s條邊( t-s>1), 如果刪去這個(gè)回路, 就得到一條vi到vj更短的路.如果新的路長(zhǎng)度還大于n-1, 說明此路中還有回路,再刪去回路, 如此進(jìn)行下去. 最后必可找到長(zhǎng)度小于n-1的路.,二. 無向圖的連通性1.兩個(gè)結(jié)點(diǎn)是連通的: 在無向圖中,結(jié)點(diǎn)u和v之間如果存在一條路, 則稱u與v是連通的. 我們規(guī)定: 對(duì)任何結(jié)點(diǎn)u,

22、u與u是連通的.2.結(jié)點(diǎn)之間的連通關(guān)系是個(gè)等價(jià)關(guān)系. 令G=是無向圖, R是V上連通關(guān)系, 即 R={|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}},3.連通分支:令G=是無向圖, R是V上連通關(guān)系, 設(shè)R對(duì)V的

23、商集中有等價(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ù).下邊例中4.連通圖: 如果一個(gè)圖G只有一個(gè)連通分支(W(G)=1),則稱G是連通圖. W(G3)=1 , G3是連通圖,W(G1)=3,W(G2)=2,W(G3)=1,定理8-2.2: 圖G=是連通圖,當(dāng)且僅當(dāng) 對(duì)V

24、的任何分成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的劃分,恒存在一條邊,使它的兩個(gè)端點(diǎn)分別屬于V1和V2 (反證

25、法)假設(shè)G不是連通的. 則G至少有兩個(gè)連通分支G1、 G2,令V1 =V(G1) V2=V-V(G1), 根據(jù)連通分支定義知, 不存在端點(diǎn)分別屬于V1和V2的邊, 與已知矛盾. 所以G是連通的.,三. 割集 (Cut Set) 割集在圖論中是個(gè)重要概念, 在圖論的理論和應(yīng)用中, 都具有重要地位. 比如有交通圖:結(jié)點(diǎn)u, 邊e就是至關(guān)重要的.割集就是使得原來連通的圖, 變成不連通, 需要?jiǎng)h去的結(jié)點(diǎn)集合或邊的集合

26、.1.點(diǎn)割集與割點(diǎn):令G=是連通無向圖, 結(jié)點(diǎn)集合V1 , V1?V, 如果刪去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).注:在圖中刪除結(jié)點(diǎn)u,是指把u以及與u關(guān)聯(lián)的邊都刪除.在圖中刪除某邊,僅需把該邊刪除.,左上圖中:{b,f}, {b,g}, {f,k},{k,g}以及{a,d,i,l}是點(diǎn)

27、割集.不存在割點(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)=1,如右圖,,,,定理8-2.3 :一個(gè)連通圖中結(jié)點(diǎn)v是割點(diǎn)的充分且必要條件是存在兩個(gè)結(jié)點(diǎn)u和w, 使得從u到w的任何路都通過 v .證明:略上邊是通過刪去結(jié)

28、點(diǎn)的辦法使連通圖變得不連通的. 也可以通過刪去邊的辦法使連通圖變得不連通.3. 邊割集與割邊(橋)令G=是連通無向圖, 邊的集合E1,E1?E, 如果刪去E1中所有邊后,G就變得不連通了, 而刪去E1的任何真子集中的所有邊,得到的子圖仍然連通.則稱E1是G的一個(gè)邊割集. 如果邊割集E1中只有一條邊, 則稱此邊為割邊, 也稱之 為橋.如右圖中e就是橋.,4.邊連通度:若G不是平凡圖, 定義: λ(G)=min{

29、 |E1| | E1是G的邊割集}為圖G的邊連通度. 邊連通度λ(G)是表示為使G不連通,至少要?jiǎng)h去的邊數(shù).顯然,如果G不是連通圖, 則 k(G)=λ(G)=0*定理8-2.4 對(duì)于任何一個(gè)圖G,有 k(G)≤λ(G)≤δ(G)證明: 略(可參考書P283中定理7-2.2),四. 有向圖的連通性 1.結(jié)點(diǎn)間的可達(dá)性: G=是有向圖, u,v∈V, 如果從 u到v有一條路, 則稱從u到v可達(dá). 右圖中

30、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. 上例中 d=1 d=2 d=0 d=∞ 3. 可達(dá)性的性質(zhì): 1). d≥0 2) d=0 3) d + d≥d (如上圖的c,a,

31、b) 4) 如果從u到v不可達(dá),則d=∞ (如b,c) 5)如從u可達(dá)v,從v也可達(dá)u, 但d不一定等于d. 例如 d≠d,4. 圖的直徑: G是個(gè)圖, 定義 為圖G的直徑.上圖中, 圖的直徑D=∞ (因?yàn)閐=∞)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è)連通. 如果

32、將G看成無向圖后(即把有向邊看成無向邊)是連通的,則稱G是弱連通.(a)強(qiáng)連通.(b)a到d, d到a, 都不可達(dá) 是弱連通.(c)單側(cè)連通.,D=maxqtyzarf u,v∈V,定理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)連通的. 必要性

33、:如果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)連通性質(zhì)的最大子圖,稱為強(qiáng)分圖.具有單側(cè)連通的最大子圖,稱為單側(cè)分圖. 具有弱連通的

34、最大子圖,稱為弱分圖. 這些分圖用結(jié)點(diǎn)的集合表示. 例如,給定有向圖G,如圖所示:求它的強(qiáng)分圖、單側(cè)分圖和弱分圖.解: 強(qiáng)分圖:由{a,g,h}{c} pjnymkl{e}{f}導(dǎo)出的子圖.單側(cè)分圖:由{a,g,h,b,f,d,e}{b,c,f,d,e}導(dǎo)出的子圖.弱分圖:G本身是弱分圖.,定理8-2.6 在有向圖中,每個(gè)結(jié)點(diǎn)必位于一個(gè)且只位于一個(gè)強(qiáng)分圖中.證明:令G=是有向圖, 任取結(jié)點(diǎn)v∈V, 令S是所有與v

35、 相互可達(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é)

36、點(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=是個(gè)簡(jiǎn)單圖,V={v1,v2,

37、v3,…,vn }, 一個(gè)n×n階矩陣A=(aij)稱為G的鄰接矩陣. 其中:,例如, 給定無向圖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)的入度,3.鄰接矩陣的乘積在(A(G1))2 中a342 =2 表示從v3到v4有長(zhǎng)

38、度為2的路有2條: 在(A(G1))3中a233 =6 表示從v2到v3有長(zhǎng)度為3的路有6條:v2v1v2v3 , v2v4v2v3 , v2v3v2v3 , v2v3v1v3 , v2v3v5v3 , v2v4v5v3 .,定理8-3.1設(shè)G=是簡(jiǎn)單圖,令V={v1,v2,v3,…,vn}, G的鄰接矩陣(A(G))k中的第 i行第j列元素aijk=m, 表示在圖G中從vi到vj長(zhǎng)度為k的路有m條.可以用歸納法證明.(見教材P

39、290)在實(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=是個(gè)簡(jiǎn)單圖,V={v1,v2,v3,…,vn }, 一個(gè)n×n階矩陣P=(pij)稱為G的可達(dá)性矩陣. 其中:,2.求可達(dá)矩陣 可以根據(jù)鄰接矩陣A求可達(dá)矩陣. 設(shè)|V(G)|=n 令A(yù)(k)是將Ak中的非0元素都寫成1,而得到的只含有0和1的0-1

40、矩陣.于是可達(dá)矩陣P為: P=A∨A(2)∨A(3)∨...∨A(n) 其中∨是邏輯或. 有兩種方法求P 方法1. 按照矩陣相乘分別求出A(k) (k≥2), 然后再∨. 方法2.用求傳遞閉包的Warshall算法,見P124.例如,G2如圖所示, 求它的可達(dá)矩陣P.,P=A∨A(2)∨A(3)∨A(4)∨A(5)3.用可達(dá)矩陣求強(qiáng)分圖. 以G2為例 從圖看出有兩個(gè)強(qiáng)分圖:{v1,v3

41、}和{v2,v4,v5}下面看怎樣用P求強(qiáng)分圖.,A(5)=A(3),先將P=(pij)轉(zhuǎn)置得PT=(pTij), 如果vi與vj相互可達(dá),則 pij= pTij =1進(jìn)而求P∧PT對(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)矩陣 1).定

42、義:設(shè)G=是個(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)的 兩條邊是平行邊.,2.有向圖的完全關(guān)聯(lián)矩陣 1).

43、定義:設(shè)G=是個(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)入度,本節(jié)重點(diǎn)掌握: 圖的三個(gè)矩陣的求法 由圖的矩陣,看圖的性質(zhì).

44、 作業(yè) P300 (3),一.歐拉圖: 1.歐拉路:在無孤立結(jié)點(diǎn)的圖G中,如果存在一條路,它經(jīng)過圖中每條邊一次且僅一次, 稱此路為歐拉路. 2.歐拉回路:在無孤立結(jié)點(diǎn)的圖G中,若存在一條回路,它經(jīng)過圖中每條邊一次且僅一次,稱此回路為歐拉回路. 稱此圖為歐拉圖,或E圖.(Euler) 在G1中:有歐拉路:acbefgdcfh在G2中:有歐拉回路:v1v2v3v4v5v2v4v6v5v3v1如何判定一

45、個(gè)圖中是否有歐拉路,或有歐拉回路?,8-4. 歐拉圖與漢密爾頓圖,3.有歐拉路與有歐拉回路的判定:定理8-4.1:無向圖G具有歐拉路,當(dāng)且僅當(dāng)G是連通的,且有零個(gè)或兩個(gè)奇數(shù)度的結(jié)點(diǎn).*證明:必要性.(見教材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)

46、 如果G無奇數(shù)度結(jié)點(diǎn),則可以從任何一個(gè)結(jié)點(diǎn)出發(fā),去構(gòu)造一條歐拉路.推論:無向圖G具有歐拉回路,當(dāng)且僅當(dāng)G是連通的,且所有結(jié)點(diǎn)的度都是偶數(shù).,用此推論判斷,七橋問題的圖是不是歐拉圖?4.求歐拉回路的算法:,不是,用上述算法求右圖中歐拉回路.此圖中所有結(jié)點(diǎn)度均為偶數(shù),所以有歐拉回路.a) 選以1為起點(diǎn)的閉跡E1:1261b) E1不包含所有邊.c) 在G- E1中找新閉跡E2: 6356 ( 6是E1與E2的公共點(diǎn))

47、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)停止.,?1,6?,?2,5?,?3,,,,,,,,,

48、?4,,,歐拉路與歐拉回路問題, 也稱一筆畫問題.*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ù):0

49、00,001,010,011,100,101,110,111 下面介紹此鼓輪的設(shè)計(jì)過程:,此輪的設(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從此

50、圖上取一個(gè)回路: e0e1e2e5 e3e7e6e4將上述各邊的末位數(shù)字寫成序列:01011100,于是就按照此序列將鼓輪進(jìn)行加工,標(biāo)0部分用絕緣體,標(biāo)1部分用導(dǎo)體.,二. 漢密爾頓圖(H圖) (Hamilton圖)Hamilton是英國(guó)數(shù)學(xué)家,在1959年,他提出Hamilton回路.H圖起源于一種游戲,這個(gè)游戲就是所謂周游世界問題. 例如,某個(gè)城市的街道如圖所示:該城市的所有交叉路口都有形象各異的精美的雕塑,吸引

51、著許多游客,人人都想找到這樣的路徑:游遍各個(gè)景點(diǎn)再回到出發(fā)點(diǎn)----H回路.1.定義:設(shè)G=是個(gè)無向有限圖, 漢密爾頓路:通過G中每個(gè)結(jié)點(diǎn)恰好一次的路. 漢密爾頓回路(H回路):通過G中每個(gè)結(jié)點(diǎn)恰好一次的回路. 漢密爾頓圖(H圖):具有漢密爾頓回路(H回路)的圖.,例如右圖中,就是H圖因?yàn)樗蠬回路:12345612.漢密爾頓圖的判定: 到目前為止并沒有判定H圖的充要條件.定理8-4.2 (充分條件):G是完全

52、圖,則G是H圖.證明:略定理8-4.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回路),在圖G1中滿足充分條件Δ(G)=4 δ(G)=2任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于5,所以是H圖. 注意:上述條件只是充分條件,而不是必要條件即不滿足這個(gè)條

53、件的, 也可能有H路.例如:在圖G2中并不滿足任意兩個(gè)結(jié)點(diǎn)度數(shù)之和大于3, 但是卻有H路.,定理8-4.4:(必要條件) 若圖G=有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

54、, 則W(C-v1 - v 2)≤2若|S|=n,由歸納法可證刪去S中的n個(gè)結(jié)點(diǎn),有W(C-v1 - v 2 -...-vn)≤n所以W(C-v1 - v 2 -...-vn)≤|S| .因?yàn)镃是H回路,所以它包含了G的所有結(jié)點(diǎn), 即C是G的生成子圖所以C-S 也是G-S 的生成子圖, 故 W(G-S)≤W(C-S)≤|S|. 用此定理可以判斷一個(gè)圖不是H圖.如右圖G, 取 S={c} 不滿足 W(G-S)≤|S|.

55、,3.用“最鄰近法”求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.

56、此回路的總權(quán)為:20但是對(duì)帶權(quán)圖來說,此方法求的H回路不一定是最短的.例如,實(shí)際上此圖最短的H回路是 acebda 總權(quán)為17,本節(jié)重點(diǎn)掌握: 歐拉路及歐拉回路的判定, 能求歐拉路 和歐拉回路. H路及H回路的判定, 能求H路和H回路. 以及歐拉圖和漢密爾頓圖的應(yīng)用. 作業(yè) P311 (1) (2) (3) (6),8-5 平面圖 Plane Graph,在實(shí)際應(yīng)用中,如高速公路

57、設(shè)計(jì)、印刷電路設(shè)計(jì),都要求線路不交叉,這就是平面圖, 一個(gè)圖能否畫在一個(gè)平面上,且任何邊都不交叉, 這就是圖的平面化問題. 近些年來, 特別是大規(guī)模集成電路的發(fā)展進(jìn)一步促進(jìn)了對(duì)平面圖的研究.1. 定義 設(shè)G是無向圖, 如果能將G的所有結(jié)點(diǎn)和邊都畫在一個(gè)平面上,且使得任何兩條邊除了端點(diǎn)外沒有其它交點(diǎn), 則稱G是個(gè)平面圖. 一個(gè)圖表面上是個(gè)非平面圖, 如果通過改變邊的位置就變成平面圖,稱此圖是可平面化的.,例如右圖.就是

58、可平面化的圖.下面是兩個(gè)重要的非平面圖:K5K3,3,2. 平面圖的面、邊界及面的次數(shù) 設(shè)G是個(gè)連通平面圖, 圖中邊圍成的區(qū)域,其內(nèi)部不含有結(jié)點(diǎn), 也不含有邊,稱這樣區(qū)域?yàn)镚的一個(gè)面. 面的邊界:圍成一個(gè)面r的所有邊構(gòu)成的回路,稱之為這個(gè)r面的邊界. 此回路中的邊數(shù),稱之為r面的次數(shù),記作deg(r). 有限面與無限面: 面的面積有限稱為有限面, 反之稱為無限面. 所有平面圖的外側(cè)都有一個(gè)無限面.

59、例如,上圖中 r1 : 邊界:ABCDFDA deg(r1)=6 r2 : 邊界:ABCA deg(r2)=3 r3 : 邊界:ACDA deg(r3)=3 r4 : 邊界:ADA

60、 deg(r4)=2,3.歐拉公式定理8-5.1 G是個(gè)連通的平面圖, 設(shè)v、e、r分別表示G中結(jié)點(diǎn)數(shù)、邊數(shù)、面數(shù), 則有 v-e+r=2. 稱此式為歐拉公式.證明: (對(duì)面數(shù)r歸納證明)⑴當(dāng)r=1 時(shí), 此時(shí)圖是連通無回路的, 如果有兩個(gè)結(jié)點(diǎn),則圖的圖形如右圖. 以后每加一條邊,也加一個(gè)結(jié)點(diǎn), 所以總是有 e=v-1, 于是 v-e+r=v-(v-1)+1=2 結(jié)論成立.⑵假設(shè)當(dāng)G有r≤

61、k-1個(gè)面時(shí), 結(jié)論成立.⑶當(dāng)G有r=k 個(gè)面且是連通圖時(shí),當(dāng)k≥2 時(shí), 至少有一個(gè)回路所以去掉此回路中的一條邊后得到子圖G’G’中有k-1個(gè)面, 結(jié)點(diǎn)數(shù)同G中結(jié)點(diǎn)數(shù)由⑵得v-(e-1)+(k-1)=2整理得 v-e+k=2 即 v-e+r=2 定理得證.,4.平面圖的判定定理8-5.2(必要條件) 設(shè)G是有v 個(gè)結(jié)點(diǎn)、e條邊的連通簡(jiǎn)單平面圖, 若v≥3, 則e≤3v-6.證明:⑴ 當(dāng)e=2 時(shí), 因?yàn)镚是簡(jiǎn)單

62、連通圖, 所以v=3, 顯然有 2≤3×3-6 即e≤3v-6⑵當(dāng)e>2時(shí), (通過計(jì)算每個(gè)面的邊界來證明)設(shè)G有r個(gè)面, 因?yàn)镚是簡(jiǎn)單圖, 所以每個(gè)面至少由三條邊圍成, 所以r個(gè)面的總次數(shù)和≥3r, 另外由書中定理7-5.1得所有面的次數(shù)總和=2e 所以有: 2e=(r個(gè)面次數(shù)總和)≥ 3r, 即2e≥3r 所以r≤2e/3由歐拉公式: v-e+r=2 得 v-e+2e/3≥2

63、 整理得 e≤3v-6用此定理可以判定一個(gè)圖不是平面圖例如證明K5不是平面圖: K5中有v=5 e=10 3v-6=3×5-6=9 不滿足 e≤3v-6, 所以K5不是平面圖.,上面定理是判定平面圖的必要條件,而不是充分條件. 即如果一個(gè)圖 滿足e≤3v-6, 它不一定是平面圖. 例如, K3,3中v=6 e=9 9≤3×6-6 滿足e≤3v-6, 但它不一定是平面圖. 下面要

64、介紹一個(gè)判定一個(gè)平面圖的充分且必要條件, 即Kuratowski(庫拉托夫斯基)定理. 在此之前先介紹一個(gè)新概念----在2度結(jié)點(diǎn)內(nèi)同構(gòu)(同胚).在一個(gè)圖中有2度結(jié)點(diǎn), 則這些結(jié)點(diǎn)不影響圖的平面性.例如下面兩個(gè)圖:我們稱這兩個(gè)圖是在2度結(jié)點(diǎn)內(nèi)同構(gòu)的圖.,定義:如果G1和G2是同構(gòu)的,或者通過反復(fù)插入或刪去度數(shù)為2的結(jié)點(diǎn), 使得它們變成同構(gòu)的圖, 稱G1和G2 是在2度結(jié)點(diǎn)內(nèi)同構(gòu).例如右邊3個(gè)圖就是在2度結(jié)點(diǎn)內(nèi)同構(gòu).定理

65、8-5.3 (Kuratowski定理)一個(gè)圖是平面圖的充分且必要條件是它不含有任何與K5、K3,3在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖. (此定理證明略.) 判斷下面彼得森(Peterser)圖是否為平面圖:,本節(jié)要求掌握:平面圖的概念, 平面圖的邊界, 歐拉公式及其應(yīng)用平面圖的判定.作業(yè): P317 (1) (3) (5) (7),8-6 著色與對(duì)偶圖,著色問題起源于對(duì)地圖著色, 使得相鄰國(guó)家用不同顏色, 需要多

66、少種不同的顏色?一百多年前,英國(guó)數(shù)學(xué)家格色里(Guthrie)提出了“四色猜想”, 這一猜想在圖論發(fā)展史上曾起過巨大的推動(dòng)作用. 1879年肯普(Kempe)給出了這個(gè)猜想的第一個(gè)證明. 1890年,希伍德(Hewood)發(fā)現(xiàn)肯普的證明是錯(cuò)誤的, 可是他指出肯普的方法,雖然不能證明地圖著色用四種顏色,但可以證明五種顏色就夠了. 直到1976年美國(guó)伊利諾斯(Illinois)大學(xué)的阿佩爾(K.Appel) 和黑肯(W.Haken)

67、把四色問題歸結(jié)為2000個(gè)不同的組合結(jié)構(gòu)圖形,利用三臺(tái)高速IBM360計(jì)算機(jī)對(duì)這些圖形進(jìn)行分析用了1200機(jī)時(shí),近百億次邏輯判斷, 證明了“四色定理”.,一.對(duì)偶圖(偶圖)的定義: 給定平面圖G=, 具有平面F1,F2,F3,…,Fn. 如果有圖G*=, 滿足下面條件:⑴對(duì)于G的任意平面Fi,,內(nèi)部有且僅有一個(gè)結(jié)點(diǎn)vi*∈V*.⑵對(duì)于圖G的面Fi與 Fj的公共邊界ek ,有且僅有一條邊 ek*∈E* ,使得 ek*

68、=(vi*,vj*), 且ek*與ek相交.(vi*在Fi內(nèi), vj*在Fj內(nèi))⑶當(dāng)且僅當(dāng)ek只是一個(gè)面Fi的邊界時(shí), vi*上有一個(gè)環(huán)ek* 與ek相交. 則稱圖G*是G的對(duì)偶圖.可見G*中的結(jié)點(diǎn)數(shù)等于G中的面數(shù). G*中的邊數(shù)等于G中的邊數(shù)。,二. 自對(duì)偶圖:如果圖G的對(duì)偶圖G*與G同構(gòu),則稱G是自對(duì)偶圖. 如下圖三.對(duì)偶圖與平面圖著色的關(guān)系: 對(duì)平面圖相鄰面用不同顏色的著色問題,可以歸結(jié)到對(duì)其對(duì)偶圖的相鄰