離散數(shù)學(xué)課件第7章

1、《離散數(shù)學(xué)》教案,計算機科學(xué)與技術(shù)學(xué)院課程學(xué)時：64主 講：宋 成,河南理工大學(xué)電子教案,圖論是最近幾年發(fā)展迅速而又應(yīng)用廣泛的一門新興科學(xué)。圖論是一個重要的數(shù)學(xué)分支。它最早起源一些數(shù)學(xué)游戲的難題研究，數(shù)學(xué)家歐拉1736年發(fā)表了關(guān)于圖論的第一篇論文，解決了著名的哥尼斯堡七橋問題。克?；舴?qū)﹄娐肪W(wǎng)絡(luò)的研究、凱來在有機化學(xué)的計算中都應(yīng)用了樹和生成樹的概念。以及在民間廣為流傳的一些游戲問題：例如迷宮問題、棋盤上馬的行走路線問題等等。

2、這些古老的問題當(dāng)時吸引了許多學(xué)者的注意，從而在這些問題研究的基礎(chǔ)上，又提出了著名的四色猜想和環(huán)游世界各國的問題,第四篇：圖論,第四篇篇：圖論,圖論的不斷發(fā)展，他在解決運籌學(xué)、網(wǎng)絡(luò)理論、信息論、控制論、博弈論以及計算機科學(xué)等各個領(lǐng)域的問題時，顯示出越來越大的效果 對于這樣一門應(yīng)用廣泛的學(xué)科，其包含的內(nèi)容是豐富的，本篇首先給出圖、簡單圖、完全圖、子圖、路和圖的同構(gòu)等概念，接著研究了連通圖性質(zhì)和規(guī)律，給出了鄰接矩陣、可達(dá)性矩

3、陣、連通矩陣和完全關(guān)聯(lián)矩陣的定義。最后介紹了歐拉圖與哈密爾頓圖、平面圖、對偶圖與著色、樹與生成樹。為今后有關(guān)學(xué)科及課程的學(xué)習(xí)和研究提供方便,第七章：圖論,§7.1 圖的基本概念§7.2 路與回路§7.3 圖的矩陣表示§7.4 歐拉圖與哈密爾頓圖§7.5 平面圖§7.6 對偶圖和著色 §7.7 樹與生成樹,第七章：圖論,教學(xué)目的及要求： 深刻理解和掌握

4、圖的有關(guān)概念和表示教學(xué)類容： 圖的基本概念、路與回路、圖的矩陣表示、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與生成樹。教學(xué)重點： 圖、路、圖的矩陣表示、平面圖、對偶圖與著色、樹與生成樹教學(xué)難點： 樹與生成樹。,第七章：圖論,§7.1 圖的基本概念,7.1.1圖  兩個個體x，y的無序序列稱為無序?qū)Γ洖?x,y)。在無序?qū)?x,y)中，x，y是無序的，它們的順序可以顛倒，即(

5、x,y)=(y,x)?！径x7.1.1】 圖G是一個三重組?V(G),E(G),?G? 其中：V(G)是非空結(jié)點集。 E(G)是邊集。 ?G是邊集到結(jié)點的有序?qū)?無序?qū)系暮瘮?shù)。,第七章：圖論,【例7.1】G=?V(G),E(G),?G?

6、 其中：V(G)=?a,b,c,d? E(G)=?e1,e2,e3,e4? ?G：?G(e1)=(a,b) ?G(e2)=(b,c) ?G(e3)=(a,c)

7、 ?G(e4)=(a,a)試畫出G的圖形。 解：G的圖形如圖7.1所示。,第七章：圖論,由于在不引起混亂的情況下，圖的邊可以用有序?qū)驘o序?qū)χ苯颖硎?。因此，圖可以簡單的表示為： G=?V,E? 其中：V是非空的結(jié)點集。 E是邊的有序?qū)驘o序?qū)M成的集合。

8、 按照這種表示法，例7.1中的圖可以簡記為： G=?V,E? 其中：V=?a,b,c,d? E=?(a,b), (b,c), (a,c), (a,a)?,第七章：圖論,【定義7.1.2 】 若圖G有n個結(jié)點，則稱該圖為n階圖?！径x7.1.3】 設(shè)G為圖，如果G的所有邊都

9、是有向邊，則稱G為有向圖。如果G的所有邊都是無向邊，則稱G為無向圖。如果G中既有有向邊，又有無向邊，則稱G為混合圖。 圖7.2的(a)是無向圖，(b)是有向圖，(c)是混合圖。,第七章：圖論,在一個圖中，若兩個結(jié)點由一條邊(有向邊或無向邊)關(guān)聯(lián)，則稱其中的一個結(jié)點是另一個結(jié)點的鄰接點。并稱這兩個結(jié)點相互鄰接。 在一個圖中不與任何結(jié)點相鄰接的結(jié)點，稱為孤立點。 在一個圖中，如果兩條邊關(guān)聯(lián)于同一個結(jié)點，則稱其中的一個

10、邊是另一個邊的鄰接邊。并稱這兩個邊相互鄰接。關(guān)聯(lián)于同一個結(jié)點的一條邊叫做環(huán)或自回路。在有向圖中環(huán)的方向可以是順時針，也可以是逆時針，它們是等效的?！径x7.1.4】 由孤立點組成的圖叫做零圖。由一個孤立點組成的圖叫做平凡圖。 根據(jù)定義7.1.4，平凡圖一定是零圖。,第七章：圖論,7.1.2結(jié)點的度及其性質(zhì)【定義7.1.5】設(shè)G=?V,E?是圖，v?V，與v相關(guān)聯(lián)的邊數(shù)叫做結(jié)點v的度。記為deg(v)。規(guī)定，自回路為所在結(jié)點

11、增加2度。 在圖G=?V,E?中，度數(shù)最大(小)的結(jié)點的度叫做圖G的最大(小)度，記為?(G)(?(G))。圖G的最大度和最小度表示為： ?(G)=max? deg(v) | v?V ? ?(G)= min? deg(v) | v?V ? 在圖7.1中， ?(G)=4，?(G)=0。,第七章：圖論,【定理7.1.1】在任何圖G=?V,E?中，所有結(jié)點度數(shù)的和等于邊數(shù)的2倍。即：

12、= 2|E| 證明：圖的每一條邊都和兩個結(jié)點相關(guān)聯(lián)，為每個相關(guān)聯(lián)的結(jié)點增加一度, 給圖增加兩度。所以所有結(jié)點度數(shù)的和等于邊數(shù)的2倍。 推論 在任何圖G=?V,E?中，度數(shù)為奇數(shù)的結(jié)點必為偶數(shù)個。,第七章：圖論,【定義7.1.6】設(shè)G=?V,E?是有向圖，v?V，射入(出)結(jié)點v的邊數(shù)稱為結(jié)點v的入(出)度。記為deg－(v) (deg＋(v))。 顯然，任何結(jié)點的入度與出度的和等于該結(jié)點

13、的度數(shù)，即deg(v)=deg－(v)+deg＋(v)。【定理7.1.2】在有向圖中，所有結(jié)點入度的和等于所有結(jié)點出度的和。 證明：在有向圖中每一條邊對應(yīng)一個入度和一個出度，為圖的入度和出度各增加1。所以，所有結(jié)點入度的和等于邊數(shù)，所有結(jié)點出度的和也等于邊數(shù)。,第七章：圖論,7.1.3多重圖、簡單圖、完全圖和正則圖【定義7.1.7 】 在圖G中，連接同一對結(jié)點的多條相同邊稱為平行邊。平行邊的條數(shù)稱為該平行邊的重數(shù)。含

14、平行邊的圖叫多重圖。不含平行邊和環(huán)的圖叫簡單圖。 例如，在圖7.3(a)中結(jié)點a和b之間有兩條平行邊，結(jié)點b和c之間有三條平行邊，結(jié)點b上有兩條平行邊，這兩條平行邊都是環(huán)。圖7.3(a)不是簡單圖。 又如，在圖7.3(b)中結(jié)點v1和v2之間有兩條平行邊。v2和v3之間的兩條邊，因為方向不同，所以不是平行邊。圖7.3(b)不是簡單圖。 簡單圖不含平行邊和環(huán)。,第七章：圖論,第七章：圖論,【定理7.

15、1.3 】 設(shè)G為n階簡單無向圖，則?(G)≤n–1。 證明：因為G有n個結(jié)點，G的任何結(jié)點v最多只能與其余的n–1結(jié)點相鄰接；又因為G為簡單圖，既無平行邊，又無環(huán)。所以deg(v)≤n–1。由v的任意性，就有 ?(G) =max?deg(v) | v?V?≤n–1?！径x7.1.8 】 設(shè)G為n階簡單無向圖，若G中的每個結(jié)點都與其余的n–1個結(jié)點相鄰接，則稱G為n階無向完全圖。記為Kn

16、。在n階無向完全圖中，給每一條邊任意確定一個方向，所得到的圖稱為n階有向完全圖。也記為Kn。 今后，將n階無向完全圖和n階有向完全圖統(tǒng)稱為n階完全圖。,第七章：圖論,【定理7.1.4】 n階完全圖Kn的邊數(shù)為 證明：在Kn中，每個結(jié)點都與其余的n–1結(jié)點相鄰接，即任何一對結(jié)點之間都有一條邊，故邊數(shù)應(yīng)為 【定義7.1.9 】設(shè)G為n階簡單無向圖，若G中每個結(jié)點都是k度的，則稱G為k次正則圖。,第七章：圖論,7.

17、1.4圖的同構(gòu) 在圖論中只關(guān)心結(jié)點間是否有連線，而不關(guān)心結(jié)點的位置和連線的形狀。因此，對于給定的圖而言，如果將圖的各結(jié)點安排在不同的位置上，并且用不同形狀的弧線或直線表示各邊，則可以得到各種不同圖形。所以，同一圖的圖形并不惟一。由于這種圖形表示的任意性，可能出現(xiàn)這樣的情況：看起來完全不同的兩種圖形，卻表示著同一個圖。 例如，在圖7.4中，(a)和(b)兩個圖的圖形不同，但它們的結(jié)構(gòu)完全相同，是同一個圖。 為了描述

18、看起來不同，而其結(jié)構(gòu)完全相同的圖，引入了同構(gòu)的概念。,第七章：圖論,第七章：圖論,【定義7.1.10】 設(shè)G1=?V1,E1?與G2=?V2,E2?是兩個無向圖(有向圖)，若存在雙射函數(shù)f：V1?V2，?v1?V1，?v2?V1(v1,v2)?E1(?v1,v2??E1)當(dāng)且僅當(dāng)(f(v1),f(v2))?E2)(?f(v1),f(v2)??E2)并且(v1,v2)(?v1,v2?)與(f(v1),f(v2))(?f(v1),f

19、(v2)?)的重數(shù)相同，則稱圖G1與圖G2同構(gòu)。記為G1≌G2。雙射函數(shù)f稱為圖G1與圖G2的同構(gòu)函數(shù)。,第七章：圖論,兩個圖同構(gòu)必須滿足下列條件： ①結(jié)點數(shù)相同。 ②邊數(shù)相同。 ③度數(shù)相同的結(jié)點數(shù)相同。 這三個條件是兩個圖同構(gòu)的必要條件，不是充分條件。一般的，用上述三個必要條件判斷兩個圖是不同構(gòu)的。 兩個圖同構(gòu)，它們的同構(gòu)函數(shù)必須實現(xiàn)同度結(jié)點對應(yīng)同度結(jié)點。,第七章：圖論,7.1.

20、5補圖、子圖和生成子圖【定義7.1.11】設(shè)G=?V,E?是n階簡單無向圖，G中的所有結(jié)點和所有能使G成為完全圖的添加邊組成的圖稱為圖G的相對于完全圖的補圖，簡稱為G的補圖。記為 。若G≌ ，則稱G為自補圖。,在圖7.5中，(b)是(a)的補圖，(a)與(b)同構(gòu)，所以(a)是自補圖。,第七章：圖論,【定義7.1.12】設(shè)G=?V,E?與G1=?V1,E1?是兩個圖。如果V1?V且E1?E，則稱G1是G的子圖，G是

21、G1的母圖；如果V1?V且E1?E，則稱G1是G的真子圖；如果V1＝V且E1?E則稱G1是G的生成子圖。,在圖7.6中，(b)是(a)的子圖、真子圖、生成子圖。,第七章：圖論,§7.2 路和回路,【定義7.2.1】 設(shè)G=?V,E?是圖，G中的結(jié)點與邊的交替序列L：v0e1v1e2v2…envn叫做v0到vn的路。其中vi-1與vi是ei的端點，i=1,…,n。v0和vn分別叫做路L的始點和終點。路L中邊的條數(shù)叫做該路的長度

22、。 例如，在圖7.7中， L1：v5e8v4e5v2e6v5e7v3 是從v5到v3的路，v5是始點， v3是終點，長度為4。 L2：v1e1v2e3v3 是從v1到v3的路，v1是始點，

23、 v3是終點，長度為2。 在簡單圖中沒有平行邊和環(huán)，路L：v0e1v1e2v2…envn完全由它的結(jié)點序列v0v1v2… vn確定。所以，在簡單圖中的路可以用結(jié)點序列表示。,第七章：圖論,【定義7.2.2】 設(shè)G=?V,E?是圖，L是從 v0到vn的路。若v0=vn，則稱L為回路。若L中所有邊各異，則稱L為簡單路。若此時又有v0=vn，則稱L為簡單回路。若L中所有結(jié)點各異，則稱L為基本路。若此時又

24、有v0=vn，則稱L為基本回路。若L既是簡單路，又是基本路，則稱L為初級路。若此時又有v0=vn，則稱L為初級回路。 在圖7.7中，L1是一條簡單路。L2是一條簡單路、基本路、初級路。,第七章：圖論,【 定理7.2.1】 在n階圖G中，若從結(jié)點vi到vj(vi≠vj)存在一條路，則必存在長度小于等于n-1的路。 證明：設(shè)L：vie1v1e2v2…ejvj是G中一條從結(jié)點vi到vj長度為l的路，路上有l(wèi)+1個結(jié)點

25、。 若l≤n-1，則定理已證。 否則，l＞n-1，此時，l+1＞n，即路L上的結(jié)點數(shù)l+1大于圖G中的結(jié)點數(shù)n，此路上必有相同結(jié)點。設(shè)vk和vs相同。于是，此路兩次通過同一個結(jié)點vk(vs)，所以在L上存在vs到自身的回路Cks。在L上刪除Cks上的一切邊和除vs以外的一切結(jié)點，得路L1：vie1v1…ekvs…ejvj。L1仍為從結(jié)點vi到vj的路，且長度至少比L減少1。若路L1的長度小于等于n-1，則

26、定理已證。否則，重復(fù)上述過程。由于G有n個結(jié)點，經(jīng)過有限步后，必得到從vi到vj長度小于等于n-1的路。,第七章：圖論,推論 在n階圖G中，若從結(jié)點vi到vj(vi≠vj)存在路，則必存在長度小于等于n-1的初級路。 由定理7.2.1的證明過程知，本推論成立。 類似的可證明下列定理和推論?！径ɡ?.2.2】 在n階圖G中，若存在結(jié)點vi到自身的回路，則必存在vi到自身長度小于等于n的回路。 推

27、論 在n階圖G中，若存在結(jié)點vi到自身的簡單回路，則必存在vi到自身長度小于等于n的初級回路。,【定義7.2.3】 在無向圖G中，如果結(jié)點u和結(jié)點v之間存在一條路，則稱結(jié)點u和結(jié)點v連通。記為u～v。規(guī)定，G中任意結(jié)點v和自身連通，即v～v。 在無向圖中，如果結(jié)點u和結(jié)點v連通，即u～v，那么，結(jié)點v和結(jié)點u連通，即v～u。所以，無向圖結(jié)點間的連通是對稱的。 設(shè)G=?V,E?是無向圖，在圖G的結(jié)點集V上

28、建立一個二元關(guān)系R：R=??u,v? | u?V∧v?V∧u和v連通? R叫做無向圖G的結(jié)點集V上的連通關(guān)系。 因為R是自反的、對稱的、傳遞的，所以R是V上的等價關(guān)系。無向圖G的結(jié)點集V上的連通關(guān)系是等價關(guān)系。,第七章：圖論,設(shè)G是圖7.8。結(jié)點集V上的連通關(guān)系為R，以下驗證R是V上的等價關(guān)系，并找出所有等價類。 R=??a,a?,?a,b?,?a,c?,?b,a?,?b,b?,?

29、b,c?,?c,a?,?c,b?, ?c,c?,?d,d?,?e,e?,?e,f?,?e,g?,?e,h?,?f,e?, ?f,f?, ?f,g?,?f,h?,?g,e?,?g,f?,?g,g?,?g,h?,?h,e?,?h,f?, ?h,g?,?h,h?? =?a,b,c?×?a,b,c?∪?d?×

30、;?d?∪?e,f,g,h?×?e,f,g,h?,根據(jù)定義，R是V上的等價關(guān)系。等價類有三個，分別是：?a,b,c?，?d?，?e,f,g,h?。,第七章：圖論,【定義7.2.4】 若無向圖G中的任何兩個結(jié)點都是連通的，則稱G為連通圖。規(guī)定，平凡圖是連通圖?！径x7.2.5】 設(shè)G=?V,E?是圖 ⑴V1?V且V1≠Æ，E1是G中兩個端點都在V1中的邊組成的集合，圖G1=?V1,E1?叫做G的由V

31、1導(dǎo)出的子圖，記為G[V1]。 ⑵E2?E且E2≠Æ，V2是由E2中的邊所關(guān)聯(lián)的結(jié)點組成的集合，圖G2=?V2,E2?叫做G的由E2導(dǎo)出的子圖，記為G[E2]。 在圖7.9中，設(shè)圖G為(a)，取V1=?a,b,c?，則G的由V1導(dǎo)出的子圖G[V1]是(b)。取E2=?(a,b),(d,c)?，G的由E2導(dǎo)出的子圖G[E2]是(c)。,第七章：圖論,第七章：圖論,【定義7.2.6】 設(shè)G=?V

32、,E?是無向圖， R是V上的連通關(guān)系，V/R=?Vi?Vi是R的等價類，i=1,…,k ?是V關(guān)于R的商集，G[Vi]是Vi導(dǎo)出的子圖，稱G[Vi]( i=1,…, k)為G的連通分支。G的連通分支數(shù)記為W(G)。 設(shè)圖7.8為G，在G中，連通關(guān)系R的三個等價類是?a,b,c?，?d?，?e,f,g,h ?，它們導(dǎo)出的G的子圖分別是圖7.8中的(a)，(b)，(c)。它們都是G的連通分支。G的連通分支數(shù)W(G)=3。

33、 每一個連通分支中任何兩個結(jié)點是連通的，而位于不同連通分支中的任何兩個結(jié)點是不連通的。即每一個連通分支都是原圖的最大的連通子圖。在圖7.8中，(a)，(b)，(c)都是最大的連通子圖。,第七章：圖論,【定義7.2.7】 設(shè)u，v是無向圖G中的任意兩個結(jié)點，若u和v連通，則u和v之間最短路的長叫做結(jié)點u與結(jié)點v的距離，記為d(u,v)。若u和v不連通，規(guī)定，u與v的距離為∞。即d(u,v)=∞ 設(shè)G=?V,E?是無

34、向圖，u、v和w是V中的任意結(jié)點，G的結(jié)點間的距離有以下的性質(zhì)： ① d(u,v)≥0 ② d(u,u)=0 ③ d(u,v)＋d(v,w)≥d(u,w) ④ d(u,v)=d(v,u) 在n階無向完全圖Kn中，每兩個不同結(jié)點間都有一條邊，它們的距離是1。在零圖中，每兩個不同結(jié)點間都沒有路，它們的距離都是∞。 在圖G中刪除一個結(jié)點，就是將這個結(jié)點與它

35、的所有關(guān)聯(lián)邊全部刪除。刪除一個邊，則僅去掉這個邊。,第七章：圖論,【定義7.2.8】設(shè)G=?V,E?是無向連通圖，V1?V且V1≠Æ，滿足： ⑴刪除V1的所有結(jié)點，得到的子圖是不連通的。 ⑵刪除V1的任何真子集，得到的子圖是連通的。則稱V1是G的點割集。如果某一個結(jié)點組成了點割集，則稱該點為割點。,在圖7.10中，?b,d?，?c?，?e?都是點割集，結(jié)點c和結(jié)點e都是割點。雖然刪除結(jié)點a和c

36、圖成為不連通的，但因?c?是?a,c?的真子集，所以?a,c?不是點割集。,第七章：圖論,【定義7.2.9】設(shè)G=?V,E?是無向連通圖，如果G不是完全圖，k(G)=min?|V1|?V1是G的點割集?稱為圖G的點連通度。如果G是完全圖，規(guī)定n階無向完全圖Kn的點連通度為n–1，即k(Kn)=n–1。規(guī)定不連通圖G的點連通度為0。即k(G)= 0。 圖7.10是無向連通圖，但不是完全圖，存在割點c和e，所以點連通度是1。

37、 無向連通圖的點連通度的物理意義是：要使G成為不連通的最少要刪除的結(jié)點數(shù)。圖7.10的點連通度是1，最少刪除一個結(jié)點，圖成為不連通的，例如刪除結(jié)點c或結(jié)點e。,第七章：圖論,【定義7.2.10】設(shè)G=?V,E?是無向連通圖，E1?E且E1≠Æ，滿足： ⑴刪除E1的所有邊，得到的子圖是不連通的。 ⑵刪除E1的任何真子集，得到的子圖是連通的則稱E1是G的邊割集。如果某一條邊組成了邊割集，則稱該邊為

38、割邊或橋。 在圖7.10中，集合?(c,e)?、?(e,f)?、?(a,b),(d,c)?和?(a,d),(b,c)?都是G的邊割集，無向邊(c,e)和(e,f)為割邊。雖然刪除邊(a,d)、(a,b)和(d,c)圖成為不連通的，但因集合?(a,b),(d,c)?是集合?(a,d),(a,b),(d,c)?的真子集，所以?(a,d),(a,b),(d,c)?不是邊割集。,第七章：圖論,【定義7.2.11】設(shè)G=?V,E?

39、是無向連通圖，如果G是非平凡圖，?(G)=min?|E1|?E1是G的邊割集?稱為G的邊連通度。如果G是平凡圖，規(guī)定G的邊連通度為0。規(guī)定不連通圖G的邊連通度為0，即?(G)=0。 圖7.10是無向連通圖，但不是平凡圖，存在割邊(c,e)和(e,f)，所以，它的邊連通度是1。 無向連通圖的邊連通度的物理意義是：要使G成為不連通的最少要刪除的邊數(shù)。圖7.10的邊連通度是1，最少刪除一條邊，圖就會成為不連通的，

40、例如刪除割邊(c,e)或(e,f)。 無向圖G的點連通度k(G)、邊連通度?(G)和最小度? (G)有下列的關(guān)系：,第七章：圖論,【定理7.2.3】設(shè)G=?V,E?為任意無向圖，則k(G)≤?(G)≤? (G) 證明：⑴如果G是不連通的，由點連通度和邊連通度的定義有k(G)=?(G)=0，所以 k(G)≤?(G)≤? (G) ⑵如果G是連通圖。

41、 ①先證明?(G)≤? (G) 如果G是平凡圖，?(G)=0≤?(G)，即?(G)≤? (G) 如果G是非平凡圖，設(shè)n=?(G)=min?deg(v)|v?V?，則存在G的一個結(jié)點v，它關(guān)聯(lián)了n條邊，而其它結(jié)點關(guān)聯(lián)的邊數(shù)大于等于n，將v關(guān)聯(lián)的這n條邊刪除，G成為不連通的。從而這n條邊或這n條邊中的幾條邊組成一個邊割集，即存在一個邊割集的基數(shù)小于等于n，所以,第七章：圖論,min?|E 1| | E 1是

42、G的邊割集?≤n=min?deg(v) | v?V ?，即 ?(G)≤? (G) ②再證k(G)≤?(G) 設(shè)?(G)=1，G有一條割邊，此邊的任一端點是割點，k(G)=1。所以k(G)≤?(G)成立。 設(shè)?(G)≥2，則可刪除某?(G)條邊，使G成為不連通的，而刪除其中的?(G)–1條邊，它仍然是連通的且有一個橋，設(shè)該橋為e=(u,v)。對這?(G)–1條邊選取一個不同于u，也不同于v的

43、端點，把這些端點刪除，則必至少刪除了這?(G)–1條邊。若這樣產(chǎn)生的圖是不連通的，則k(G)≤?(G)–1≤?(G)。若這樣產(chǎn)生的圖是連通的，則e=(u,v)仍是橋。此時再刪除u或v，就必產(chǎn)生了一個不連通圖，故k(G)≤?(G) 由⑴和⑵得k(G)≤?(G)≤? (G),第七章：圖論,圖7.11是無向連通圖，點連通度k(G)=1，邊連通度?(G)=2，最小度?(G)=3，此圖滿足k(G)≤?(G)≤? (G)。,第七章：圖論,【

44、定理7.2.4】在無向連通圖G中，結(jié)點v是割點的充分必要條件是存在兩個結(jié)點u和w，使結(jié)點u和w之間的每一條路都通過v。 證明：設(shè)v是割點，證明存在兩個結(jié)點u和w，使結(jié)點u和w之間的每一條路都通過v。 v是割點，刪除v得G′，G′至少包含兩個連通分支，設(shè)其中的兩個為G1=?V1,E1?和G2=?V2,E2?，?u?V1，?w?V2，因為G連通，在G中u和w之間必有路，設(shè)L是它們之間任意一條路。在G′中，由

45、于u和w屬于兩個不同連通分支，所以，u和w之間必沒有路。故L必通過v。 設(shè)存在兩個結(jié)點u和w，使結(jié)點u和w之間的每一條路都通過v，證明v是割點。 刪除v得子圖G′，因為結(jié)點u和w之間的每一條路都通過v，所以在G′中結(jié)點u和w之間必?zé)o路，即結(jié)點u和w不連通。由連通圖的定義知，G′是不連通的，故v是G的割點。,第七章：圖論,【定義7.2.12】在有向圖G中，結(jié)點u到結(jié)點v存在一條路，則稱結(jié)點u到結(jié)點v可達(dá)。記為u→v

46、。如果u到v可達(dá)且v到u也可達(dá)，稱結(jié)點u和結(jié)點v相互可達(dá)。記為u?v。 規(guī)定，G中任何結(jié)點v自己到自己可達(dá)，即v?v。【定義7.2.13】在有向圖G=?V,E?中，u?V，v?V，若結(jié)點u到結(jié)點v可達(dá)，u到v最短路的長稱為結(jié)點u到結(jié)點v的距離。記為d?u,v?。若u到v不可達(dá)，規(guī)定，u到v的距離為∞。即d?u,v?=∞。 對于有向圖G中的任意結(jié)點u,v和w，結(jié)點間的距離有以下的性質(zhì)： ① d?u,v?

47、≥0 ② d?u,u?=0 ③ d?u,v?＋d?v,w?≥d?u,w?,第七章：圖論,【定義7.2.14】在簡單有向圖G中，對于任意兩個結(jié)點u和v， ⑴如果結(jié)點u到結(jié)點v可達(dá)或結(jié)點v到結(jié)點u可達(dá)，則稱G為單向(側(cè))連通的。 ⑵如果結(jié)點u和結(jié)點v互相可達(dá)，則稱G為強連通的。 ⑶如果略去方向得到的無向圖是連通的，則稱G為弱連通的。 在圖7.12中，(

48、a)是強連通的、單向(側(cè))連通的和弱連通的。(b)是單向(側(cè))連通的和弱連通的，但不是強連通的。(c)是弱連通的，但不是單向(側(cè))連通的，也不是強連通的。,第七章：圖論,一般地說，若有向圖G是強連通的，則必是單向(側(cè))連通的和弱連通的；若有向圖G是單向(側(cè))連通的，則必是弱連通的。反之不真。,第七章：圖論,【定理7.2.5】一個有向圖G是強連通的充分必要條件是G中有一個回路至少包含G的每個結(jié)點一次。 證明：設(shè)G中有一個回

49、路至少包含G的每個結(jié)點一次，下證G是強連通的。 G中有一個回路至少包含每個結(jié)點一次，則G中的任意兩個結(jié)點通過回路互相可達(dá)。所以G是強連通的。 設(shè)G是強連通的，下證G中有一個回路至少包含G的每個結(jié)點一次。 若不然，存在結(jié)點v不在G的回路上，且v不與其它所有結(jié)點不能互相可達(dá)，這與G是強連通的矛盾。故G中有一個回路至少包含G的每個結(jié)點一次。,第七章：圖論,【定理7.2.6】一個有向圖G是單向連通

50、的充分必要條件是G中有一個路至少包含每個結(jié)點一次。 證明略?！径x7.2.15】在簡單有向圖G中，具有強(單向，弱)連通性質(zhì)的最大子圖叫做強(單向，弱)分圖。 在圖7.13(a)中，由?v1,v2,v3,v4?導(dǎo)出的子圖是強分圖，?v5?導(dǎo)出的子圖也是強分圖。由?v1,v2,v3,v4,v5?導(dǎo)出的子圖是單向分圖，也是弱分圖。 在圖7.13 (b) 中，?v1?，?v2?，?v3?，?v4?導(dǎo)出的子圖是

51、強分圖，?v1,v2,v3?，和?v1,v3,v4?導(dǎo)出的子圖是單向分圖，?v1,v2,v3,v4?導(dǎo)出了弱分圖。,第七章：圖論,第七章：圖論,【定理7.2.7】在有向圖G=?V,E?中，每一個結(jié)點位于且只位于一個強分圖中。 證明：⑴?v?V，令V1是G中所有與v互相可達(dá)的結(jié)點組成的集合，當(dāng)然v?V1， V1導(dǎo)出的子圖是G的強分圖。故G的每一個結(jié)點位于一個強分圖中。 ⑵設(shè)G1=?V1,E1?和G2=?V2,E2?

52、是G的兩個強分圖，設(shè)v?V1且v?V2，則v與G1中的所有結(jié)點相互可達(dá)且與G2中的所有結(jié)點相互可達(dá)。于是G1中的結(jié)點與G2中的結(jié)點通過v相互可達(dá)。這與G1和G2是強分圖相矛盾。故G的每一個結(jié)點只位于一個強分圖中。,第七章：圖論,,,§7.3圖的矩陣表示,【定義7.3.1】設(shè) G=?V,E?是一個簡單圖，V=?v1,v2,…,vn? A(G)=(aij) n×n

53、 其中： i ,j=1,…,n稱A(G)為G的鄰接矩陣。簡記為A。,第七章：圖論,例如圖7.14的鄰接矩陣為：,第七章：圖論,又如圖7.15(a)的鄰接矩陣為：,,第七章：圖論,鄰接矩陣具有以下性質(zhì)： ①鄰接矩陣的元素全是0或1。這樣的矩陣叫布爾矩陣。鄰接矩陣是布爾矩陣。 ②無向圖的鄰接矩陣是對稱陣，有向圖的鄰接矩陣不一定是

54、對稱陣。 ③鄰接矩陣與結(jié)點在圖中標(biāo)定次序有關(guān)。例如圖7.15(a)的鄰接矩陣是A(G)，若將圖7.15(a)中的接點v1和v2的標(biāo)定次序調(diào)換，得到圖7.15(b)，圖9.23(b)的鄰接矩陣是A′(G)。,,第七章：圖論,考察A(G)和A′(G)發(fā)現(xiàn)，先將A(G)的第一行與第二行對調(diào)，再將第一列與第二列對調(diào)可得到A′(G)。稱A′(G)與A(G)是置換等價的。 一般地說，把n階方陣A的某些行對調(diào)，再把相應(yīng)

55、的列做同樣的對調(diào)，得到一個新的n階方陣A′，則稱A′與A是置換等價的。可以證明置換等價是n階布爾方陣集合上的等價關(guān)系。 雖然，對于同一個圖，由于結(jié)點的標(biāo)定次序不同，而得到不同的鄰接矩陣，但是這些鄰接矩陣是置換等價的。今后略去結(jié)點標(biāo)定次序的任意性，取任意一個鄰接矩陣表示該圖。 ④對有向圖來說，鄰接矩陣A(G)的第i行1的個數(shù)是vi的出度， 第j列1的個數(shù)是vj的入度。 ⑤零圖的鄰接矩陣的

56、元素全為零，叫做零矩陣。反過來，如果一個圖的鄰接矩陣是零矩陣，則此圖一定是零圖。,第七章：圖論,,,,,,,,【定理7.3.1】設(shè)A(G)是圖G的鄰接矩陣，A(G)k=A(G)A(G)k-1，A(G)k的第i行，第j列元素 等于從vi到vj長度為k的路的條數(shù)。其中 為vi到自身長度為k的回路數(shù)。 推論 設(shè)G=?V,E?是n階簡單有向圖，A是有向圖G的鄰接矩陣，Bk=A＋A2＋…＋Ak，Bk=( )

57、n×n，則 是G中由vi到vj長度小于等于k的路的條數(shù)。 是G中長度小于等于k的路的總條數(shù)。 是G中長度小于等于k的回路數(shù)。【例7.3.1】 設(shè)G=?V,E?為簡單有向圖，圖形如圖7.16，寫出G的鄰接矩陣A，算出A2，A3，A4且確定v1到v2有多少條長度為3的路? v1到v3有多少條長度為2的路? v2到自身長度為3和長度為4的回路各多少條?,第七章：圖論,解：鄰接矩陣A和A2，A3，A4

58、如下：,,,,第七章：圖論,,,,,,=2，所以v1到v2長度為3的路有2條，它們分別是：v1v2v1v2和v1v2v3v2。 =1，所以v1到v3長度為2的路有1條：v1v2v3。 =0，v2到自身無長度為3的回路。 =4，v2到自身有4條長度為4的回路，它們分別是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v

59、3v2。,第七章：圖論,【 定義7.3.2】設(shè)G=?V,E?是簡單有向圖，V=?v1,v2,…,vn? P(G)=(pij)n×n 其中：pij = i,j=1,…,n稱P(G)為G的可達(dá)性矩陣。簡記為P。 在定義7.2.

60、12中，規(guī)定了有向圖的任何結(jié)點自己和自己可達(dá)。所以可達(dá)性矩陣P(G)的主對角線元素全為1。,第七章：圖論,,,,,設(shè)G=?V,E?是n階簡單有向圖，V=?v1,v2,…,vn?，由可達(dá)性矩陣的定義知，當(dāng)i≠j時，如果vi到vj有路，則pij=1；如果vi到vj無路，則pij=0；又由定理7.2.1知，如果vi到vj有路，則必存在長度小于等于n–1的路。依據(jù)定理7.3.1的推論，如下計算圖G的可達(dá)性矩陣P： 先計算Bn–1

61、=A＋A2＋…＋An–1，設(shè)Bn–1=( )n×n。若 ≠0，則令pij=1，若 =0，則令pij =0，i,j=1,…,n。 再令pii=1，i=1,…,n。就得到了圖G的可達(dá)性矩陣P。 令A(yù)0為n階單位陣，則上述算法也可以改進(jìn)為： 計算Cn–1= A0＋Bn–1=A0＋A＋A2＋…＋An-1，設(shè)Cn–1=( )n×

62、n。若 ≠0，則令pij=1， 若 =0，則令pij=0，i,j=1,…,n。,第七章：圖論,使用上述方法，計算例7.3.1中圖G的可達(dá)性矩陣，,C4= A0＋A＋A2＋A3＋A4 =,,,P=,第七章：圖論,,,,,,,計算簡單有向圖G的可達(dá)性矩陣P，還可以用下述方法： 設(shè)A是G的鄰接矩陣，令A(yù)=(aij)n×n，A(k

63、) =( )n×n，A0為n階單位陣。 A(2)=A°A，其中 =(ai1∧a1j)∨(ai2∧a2j)∨…∨(ain∧anj) i,j=1,…,n。 A(3)=A°A(2)，其中 (ai1∧ )∨… ∨(ain∧

64、 ) i,j=1,…,n。 …… P= A0∨A∨A(2)∨A(3)∨…∨A(n–1)。 其中，運算∨是矩陣對應(yīng)元素的析取。 可達(dá)性矩陣用來描述有向圖的一個結(jié)點到另一個結(jié)點是否有路，即是否可達(dá)。無向圖也可以用矩陣描述一個結(jié)點到另一個結(jié)點是否有路。在無向

65、圖中，如果結(jié)點之間有路，稱這兩個結(jié)點連通，不叫可達(dá)。所以把描述一個結(jié)點到另一個結(jié)點是否有路的矩陣叫連通矩陣，而不叫可達(dá)性矩陣。,第七章：圖論,,【定義7.3.3】設(shè)G=?V,E?是簡單無向圖，V=?v1,v2,…,vn? P(G)=( pij) n×n 其中：

66、 i,j=1,…,n稱P(G)為G的連通矩陣。簡記為P。 無向圖的鄰接矩陣是對稱陣，無向圖的連通矩陣也是對稱陣。求連通矩陣的方法與可達(dá)性矩陣類似。,第七章：圖論,,【定義7.3.4】 設(shè)G=?V,E?是無向圖，V=?v1,v2,…,vp?，E=?e1,e2,…,eq? M(G)=( mij) p×q 其中：

67、 i=1,…,p，j=1,…,q稱M(G)為無向圖G的完全關(guān)聯(lián)矩陣。簡記為M。,第七章：圖論,,例如圖7.17的完全關(guān)聯(lián)矩陣為：,M(G) =,第七章：圖論,設(shè)G=?V,E?是無向圖，G的完全關(guān)聯(lián)矩陣M(G)有以下的性質(zhì)： ①每列元素之和均為2。這說明每條邊關(guān)聯(lián)兩個結(jié)點。 ②每行元素之和是對應(yīng)結(jié)點的度數(shù)。 ③所有元素之和是圖各結(jié)點度數(shù)的和，也是邊數(shù)的2倍。

68、④兩列相同，則對應(yīng)的兩個邊是平行邊。 ⑤某行元素全為零，則對應(yīng)結(jié)點為孤立點?！径x7.3.5 】設(shè)G=?V,E?是有向圖，V=?v1,v2,…,vp?，E=?e1,e2,…,eq? M(G)=( mij) p×q 其中： i=1,…,p，j=1,…,q

69、 稱M(G)為有向圖G的完全關(guān)聯(lián)矩陣。簡記為M。,,第七章：圖論,圖7.18的完全關(guān)聯(lián)矩陣為：,M(G)=,,第七章：圖論,設(shè)G=?V,E?是有向圖，G的完全關(guān)聯(lián)矩陣M(G)有以下的性質(zhì)： ①每列有一個1和一個-1，這說明每條有向邊有一個始點和一個終點。 ②每行1的個數(shù)是對應(yīng)結(jié)點的出度，-1的個數(shù)是對應(yīng)結(jié)點的入度。 ③所有元素之和是0，這說明所有