離散數(shù)學(xué)及其應(yīng)用課件第7章圖論

1、離散數(shù)學(xué)及其應(yīng)用離散數(shù)學(xué)及其應(yīng)用第7章 圖7.1 圖的基本概念7.2 通路與回路、連通的概念7.3 圖的表示7.4 圖的運(yùn)算2第7章 圖7.1 圖的基本概念2ABCD圖論起源公元十八世紀(jì)有這樣一個(gè)問(wèn)題：在東普魯士有個(gè)哥尼斯堡城（ konigsberg，后屬于蘇聯(lián)立陶宛蘇維埃社會(huì)主義共和國(guó)，現(xiàn)名為加里寧格勒；現(xiàn)屬于立陶宛共和國(guó)）。哥尼斯堡城位于pregel河畔，河中有兩個(gè)島，城市中的各個(gè)部分由七座橋相連。ABCD圖論起源公元十八世紀(jì)有這樣一個(gè)問(wèn)題：在東普魯士有個(gè)哥 最早引入圖論處理的問(wèn)題就是哥尼斯堡七橋問(wèn)題。 1736年，瑞士數(shù)學(xué)家 L.Eluer （歐拉）在他發(fā)表的“哥尼斯堡七座橋”的著名文章

2、中闡述了解決這個(gè)問(wèn)題的觀點(diǎn)，從而被譽(yù)為圖論之父。 當(dāng)時(shí)，城中的居民熱衷于這樣一個(gè)問(wèn)題，從四塊陸地的任一塊出發(fā)，怎樣才能做到經(jīng)過(guò)每座橋一次且僅一次，然后回到出發(fā)點(diǎn)。問(wèn)題看來(lái)并不復(fù)雜，但當(dāng)?shù)氐木用窈陀稳俗隽瞬簧俚膰L試，卻都沒(méi)有取得成功。 最早引入圖論處理的問(wèn)題就是哥尼斯堡七橋問(wèn)題。 Euler將四塊陸地表示成四個(gè)結(jié)點(diǎn)，凡陸地間有橋相連的，便在兩點(diǎn)間連一條邊。ABCD Euler將四塊陸地表示成四個(gè)結(jié)點(diǎn)，凡陸地間有橋相 此時(shí)，哥尼斯堡七橋問(wèn)題歸結(jié)為： 從A, B, C, D 任一點(diǎn)出發(fā)，通過(guò)每條邊一次且僅一次而返回出發(fā)點(diǎn)的回通路是否存在？DCAB 此時(shí)，哥尼斯堡七橋問(wèn)題歸結(jié)為：DCAB 歐拉斷言這樣

3、的回通路是不存在的。 理由是： 從圖中的任一點(diǎn)出發(fā)，為了要回到原來(lái)的出發(fā)點(diǎn)，要求與每個(gè)點(diǎn)相關(guān)聯(lián)的邊數(shù)均為偶數(shù)。 這樣才能保證從一條邊進(jìn)入某點(diǎn)后，再?gòu)牧硪粭l邊出去，從一個(gè)點(diǎn)的不同的兩條邊一進(jìn)一出才能回到出發(fā)點(diǎn)。 而圖中的A, B, C, D全是與奇數(shù)條邊相連，由此可知所要求的回通路是不可能存在的。 歐拉斷言這樣的回通路是不存在的。 理由是：7.1 圖的基本概念7.1.1 無(wú)向圖和有向圖7.1.2 度的概念7.1.3 圖的分類7.1.4 子圖與補(bǔ)圖7.1.5 圖的同構(gòu)87.1 圖的基本概念7.1.1 無(wú)向圖和有向圖87.1.1 無(wú)向圖和有向圖定義7.1.1 一個(gè)無(wú)向圖可以表示為G =（V，E），其

4、中V是非空有限結(jié)點(diǎn)集，稱V中的元素為結(jié)點(diǎn)或頂點(diǎn)；E是邊集，其中的元素是由V中的元素組成的無(wú)序?qū)?，稱E中的元素為邊。若（v，w）是無(wú)序?qū)?，則（v，w）=（w，v）。 例如, G=如圖所示, 其中V=v1, v2, ,v5 E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 9e1e2e3e4e5e6e7v5v1v2v3v47.1.1 無(wú)向圖和有向圖定義7.1.1 一個(gè)無(wú)向圖可以表示有向圖定義7.1.2 一個(gè)有向圖可以表示為D=（V，E），其中V是非空有限結(jié)點(diǎn)集，稱V中的元素為結(jié)點(diǎn)或頂點(diǎn)；E是有向邊集，E中的元素是由V中的

5、元素組成的有序?qū)?，稱E中的元素為有向邊。 有向圖D=（V，E）。結(jié)點(diǎn)集V= v1，v2，v3，v4，有向邊集E=，。在有向圖中，10有向圖定義7.1.2 一個(gè)有向圖可以表示為D=（V，E），其圖的術(shù)語(yǔ)定義7.1.3 如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的邊多于一條，則稱這些邊為平行邊。如果有邊關(guān)聯(lián)于一對(duì)結(jié)點(diǎn)，則稱這對(duì)結(jié)點(diǎn)是鄰接的。一條邊的兩個(gè)端點(diǎn)如果關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)，則稱為環(huán)，和任何邊都不關(guān)聯(lián)的點(diǎn)稱為孤立點(diǎn)。邊e2和e3是平行邊，邊e1關(guān)聯(lián)結(jié)點(diǎn)v1和v3，則稱v1和v3是鄰接的，邊e5=（v3，v3）是環(huán)，v4是孤立點(diǎn)。圖的術(shù)語(yǔ)定義7.1.3 如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的邊多于一條，則稱圖的術(shù)語(yǔ)如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的方向相同的

6、有向邊多于一條，則稱這些有向邊為多重有向邊或平行邊。如關(guān)聯(lián)于結(jié)點(diǎn)v1和v2的兩條有向邊是平行邊，而關(guān)聯(lián)于結(jié)點(diǎn)v3和v4的兩條有向邊方向相反，不是平行邊。（v1，v1）稱為環(huán)。對(duì)于有向邊（v2，v3），稱v2為起點(diǎn)，v3為終點(diǎn)，v2和v3是鄰接的。圖的術(shù)語(yǔ)如果關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的方向相同的有向邊多于一條，則稱這些圖的術(shù)語(yǔ)n 階圖: n個(gè)頂點(diǎn)的圖零圖: E=的圖平凡圖: 1 階零圖在圖的定義中規(guī)定結(jié)點(diǎn)集合V為非空集，但在運(yùn)算中可能產(chǎn)生結(jié)點(diǎn)集為空集的運(yùn)算結(jié)果，因此規(guī)定結(jié)點(diǎn)集為空集的圖為空?qǐng)D，記為圖的術(shù)語(yǔ)n 階圖: n個(gè)頂點(diǎn)的圖7.1.2 度的概念定義7.1.6 設(shè)G=為無(wú)向圖, vV, v所關(guān)聯(lián)的邊數(shù)稱為

7、 v的度數(shù)，簡(jiǎn)稱度，記作d(v)。懸掛頂點(diǎn): 度數(shù)為1的頂點(diǎn)懸掛邊: 與懸掛頂點(diǎn)關(guān)聯(lián)的邊G的最大度(G)=maxd(v)| vVG的最小度(G)=mind(v)| vV例如 d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是懸掛頂點(diǎn), e7是懸掛邊, e1是環(huán)14e1e2e3e4e5e6e7v5v1v2v3v47.1.2 度的概念定義7.1.6 設(shè)G=為無(wú)向頂點(diǎn)的度數(shù)(續(xù))定義7.1.7 設(shè)D=為有向圖, vV, 以v為起點(diǎn)所關(guān)聯(lián)的邊數(shù)稱為v的出度，記作d+(v)；以v為終點(diǎn)所關(guān)聯(lián)的邊數(shù)稱為v的入度，記作d(v)。v的總度數(shù)(度) d(v)是v的出度和入度

8、之和： d(v)= d+(v)+ d-(v)+(D), +(D), (D), (D), (D), (D)懸掛頂點(diǎn), 懸掛邊例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3,+=4, +=0, =3, =1, =5, =315e1e2e3e4e5e6e7dabc頂點(diǎn)的度數(shù)(續(xù))定義7.1.7 設(shè)D=為有向圖,握手定理定理7.1.1 設(shè)圖G=(V, E)為無(wú)向圖或有向圖，G有n個(gè)結(jié)點(diǎn)v1,v2,vn，e條邊(無(wú)向或有向), 則圖G中所有結(jié)點(diǎn)的度數(shù)之和為邊數(shù)的兩倍，即證 圖中每條邊(包括環(huán))均有兩個(gè)端點(diǎn), 所以在計(jì)算各頂點(diǎn)度數(shù)之和時(shí), 每條邊

9、均提供2度, m條邊共提供2m度.推論 任何圖(無(wú)向圖和有向圖)中，度數(shù)為奇數(shù)的結(jié)點(diǎn)的個(gè)數(shù)為偶數(shù)。16握手定理定理7.1.1 設(shè)圖G=(V, E)為無(wú)向圖或有向圖定理7.1.2定理7.1.2 在有向圖中，所有結(jié)點(diǎn)的入度之和與所有結(jié)點(diǎn)的出度之和相等，都等于圖中的有向邊數(shù)。證 在有向圖中，每條有向邊均有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)。于是在計(jì)算圖中各結(jié)點(diǎn)的出度之和與各結(jié)點(diǎn)的入度之和時(shí)，每條有向邊各提供一個(gè)出度和一個(gè)入度。當(dāng)然e條有向邊共提供e個(gè)出度和e個(gè)入度。因此所有結(jié)點(diǎn)的入度之和與所有結(jié)點(diǎn)的出度之和相等，都等于圖中的有向邊數(shù)e。定理7.1.2定理7.1.2 在有向圖中，所有結(jié)點(diǎn)的入度之圖的度數(shù)列設(shè)無(wú)向圖G的

10、頂點(diǎn)集V=v1，v2，vnG的度數(shù)列: d(v1), d(v2), , d(vn)如右圖度數(shù)列:4,4,2,1,3設(shè)有向圖D的頂點(diǎn)集V=v1，v2，vnD的度數(shù)列d(v1), d(v2), , d(vn)D的出度列: d+(v1), d+(v2), , d+(vn)D的入度列: d(v1), d(v2), , d(vn)如右圖度數(shù)列:5,3,3,3 出度列:4,0,2,1 入度列:1,3,1,218e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc圖的度數(shù)列設(shè)無(wú)向圖G的頂點(diǎn)集V=v1，v2，vn1例題 例 自然數(shù)序列(3，3，2，2，1)，(4，2，2，1，1

11、)能作為圖的結(jié)點(diǎn)的度數(shù)序列嗎？為什么？ 解 在(3，3，2，2，1)中各個(gè)數(shù)之和為奇數(shù)，由握手定理可知，(3，3，2，2，1)不能作為圖的結(jié)點(diǎn)的度數(shù)序列。 (4，2，2，1，1)能作為圖的結(jié)點(diǎn)的度數(shù)序列，下圖中的兩個(gè)圖都是以（4,2,2,1,1）為結(jié)點(diǎn)度數(shù)序列。例題 例 自然數(shù)序列(3，3，2，2，1)，(4，2實(shí)例20例2 已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小于等于2, 問(wèn)G至少有多少個(gè)頂點(diǎn)? 解 設(shè)G有n個(gè)頂點(diǎn). 由握手定理, 43+2(n-4)210解得 n8例3 已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和1,2,1,2,1, 求它的入度列解 2,1,1

12、,1,2實(shí)例20例2 已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)實(shí)例例4 證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的多面體.21證 用反證法. 假設(shè)存在這樣的多面體, 作無(wú)向圖G=,其中 V=v | v為多面體的面, E=(u,v) | u,vV u與v有公共的棱 uv.根據(jù)假設(shè), |V|為奇數(shù)且vV, d(v)為奇數(shù). 這與握手定理的推論矛盾.實(shí)例例4 證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的217.1.3 圖的分類定義7.1.8 設(shè)圖G=（V，E）為無(wú)向圖或有向圖，如果G中不含平行邊，也不含環(huán)，則稱為簡(jiǎn)單圖。定義7.1.9 設(shè)圖G=（V，E）為無(wú)向圖或有向圖，如果G中含有平行

13、邊，則稱為多重圖。簡(jiǎn)單圖多重圖多重圖簡(jiǎn)單圖7.1.3 圖的分類定義7.1.8 設(shè)圖G=（V，E）為無(wú)圖的應(yīng)用1、航班路線圖 有向多重圖2、微博關(guān)注圖 有向簡(jiǎn)單圖3、合作關(guān)系圖 無(wú)向簡(jiǎn)單圖或多重圖圖的應(yīng)用完全圖(1)定義7.1.10 設(shè)G =（V，E）是n階無(wú)向簡(jiǎn)單圖，若G中任何結(jié)點(diǎn)都與其余的n-1個(gè)結(jié)點(diǎn)相鄰，則稱G為n階無(wú)向完全圖，記作Kn。 圖7.1.7 完全圖 頂點(diǎn)數(shù)n, 邊數(shù)m=n(n-1)/2, (G)=(G)=n-1K3K5完全圖(1)定義7.1.10 設(shè)G =（V，E）是n階無(wú)完全圖(2)設(shè)G =（V，E）為n階有向簡(jiǎn)單圖，若對(duì)于V中任意的兩個(gè)結(jié)點(diǎn)u和v，既有有向邊(u，v)，又有

14、有向邊(v，u)，則稱G是n階有向完全圖。 頂點(diǎn)數(shù)n, 邊數(shù)m=n(n-1), +(D)=+(D)= -(D)= -(D)=n-1, (D)=(D)=2(n-1) 無(wú)特別說(shuō)明時(shí)，完全圖均指無(wú)向完全圖。完全圖(2)設(shè)G =（V，E）為n階有向簡(jiǎn)單圖，若對(duì)于V中任定理7.1.3定理7.1.3 設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則(G) n-1。證明：略定理7.1.3定理7.1.3 設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則例題例5 判斷下列各非負(fù)整數(shù)列是否是簡(jiǎn)單圖的結(jié)點(diǎn)度數(shù)序列？（1）（5,5,4,4,2,1）（2）（5,4,3,2,2）（3）（3,3,2,2,1,1）（4） 解 （1）根據(jù)握手定理的推論可知，不是圖的

15、結(jié)點(diǎn)度數(shù)序列，因?yàn)橛?個(gè)奇數(shù)。 （2）中有5個(gè)數(shù)，最大數(shù)是5，根據(jù)定理7.1.3，它不是簡(jiǎn)單圖的結(jié)點(diǎn)序列。 （3）是簡(jiǎn)單圖的結(jié)點(diǎn)序列。下圖的兩個(gè)無(wú)向簡(jiǎn)單圖都是（3,3,2,2,1,1）為結(jié)點(diǎn)度數(shù)序列。 （4）中的最大值d1n, 根據(jù)定理7.1.3，不是簡(jiǎn)單圖的結(jié)點(diǎn)序列。例題例5 判斷下列各非負(fù)整數(shù)列是否是簡(jiǎn)單圖的結(jié)點(diǎn)度數(shù)序列？正則圖定義7.1.11 設(shè)G為n階無(wú)向簡(jiǎn)單圖，若vV（G），均有d(v)=k,則稱G為k-正則圖。 K52正則圖4正則圖 3正則圖彼得松圖正則圖定義7.1.11 設(shè)G為n階無(wú)向簡(jiǎn)單圖，若vV（G正則圖 根據(jù)握手定理，n階k-正則圖的邊數(shù) 。當(dāng)k為奇數(shù)時(shí)，n為偶數(shù)。當(dāng)k=0

16、時(shí)，0-正則圖就是n階零圖。n階無(wú)向完全圖是(n-1)-正則圖。正則圖 根據(jù)握手定理，n階k-正則圖的邊數(shù) 環(huán)圖和輪圖定義7.1.12 如果圖G =（V，E）的結(jié)點(diǎn)集V=v1，v2，vn（n3），邊集E=（v1，v2），（v2，v3），（ vn-1，vn），（vn，v1），則稱G為環(huán)圖，記為Cn。下圖是C3,C4 ,C5 ,C6。定義7.1.13 當(dāng)給環(huán)圖Cn-1（n4）添加一個(gè)結(jié)點(diǎn)，并把這個(gè)結(jié)點(diǎn)和Cn-1里的每個(gè)結(jié)點(diǎn)逐個(gè)連接后得到的圖成為輪圖，記作Wn。下圖是輪圖W4，W5，W6，W7。環(huán)圖和輪圖定義7.1.12 如果圖G =（V，E）的結(jié)點(diǎn)集31定義7.1.14 如果圖G =（V，E）有2

17、n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)表示一個(gè)長(zhǎng)度為n的位串，任何兩個(gè)相鄰的結(jié)點(diǎn)表示的位串只有一位不同，則稱G稱為n方體圖，記作Qn。方體圖0 110110001010101100000111011001Q1 Q2 Q331定義7.1.14 如果圖G =（V，E）有2n個(gè)結(jié)點(diǎn)，方體圖對(duì)任意nN ，Qn 是將兩個(gè)Qn-1 圖的對(duì)應(yīng)結(jié)點(diǎn)連接起來(lái)的簡(jiǎn)單圖 . Q0 有 1 個(gè)結(jié)點(diǎn).Q0Q1Q2Q3Q4結(jié)點(diǎn)數(shù): 2n. 邊數(shù)： n2n-1方體圖對(duì)任意nN ，Qn 是將兩個(gè)Qn-1 圖的對(duì)應(yīng)結(jié)點(diǎn)連二分圖定義7.1.15 如果圖G =（V，E）的結(jié)點(diǎn)集V能劃分為兩個(gè)子集：V1和V2，使每條邊有一個(gè)端點(diǎn)在V1中,另一個(gè)端點(diǎn)在V

18、2中，則稱該圖為二分圖（或二部圖）。定義7.1.16 二分圖G =（V，E）的結(jié)點(diǎn)集V能劃分為兩個(gè)子集：V1和V2，若V1中的每個(gè)結(jié)點(diǎn)和V2中的每個(gè)結(jié)點(diǎn)均有邊相連，則稱G為完全二分圖。若|V1|=m，|V2|=n, 則可記為Km,n。下圖所示的是K2,3和K3,3。 二分圖定義7.1.15 如果圖G =（V，E）的結(jié)點(diǎn)集V能帶權(quán)圖定義7.1.17 每個(gè)結(jié)點(diǎn)或每條邊都帶有數(shù)值的圖稱為帶權(quán)圖。 可以用有序三元組或有序四元組表示帶權(quán)圖。如G=(V,E,f)，G=(V,E,g) 或G=(V,E,f,g)，其中V是結(jié)點(diǎn)集，E是邊集， f是結(jié)點(diǎn)所帶的權(quán)的集合，g是邊所帶的權(quán)的集合。下圖左邊為邊帶權(quán)圖，右邊

19、為結(jié)點(diǎn)帶權(quán)圖。 34 6 2 1帶權(quán)圖定義7.1.17 每個(gè)結(jié)點(diǎn)或每條邊都帶有數(shù)值的圖7.1.4 子圖與補(bǔ)圖定義7.1.18 設(shè)圖G=（V，E）設(shè)eE，從G圖中刪去邊e得到的圖表示為G-e,稱為刪除邊運(yùn)算；設(shè)E1E，從G圖中刪去E1的所有邊得到的圖表示為G- E1,稱為刪除邊集運(yùn)算。設(shè)vV，從G圖中刪去結(jié)點(diǎn)v及v關(guān)聯(lián)的所有邊得到的圖表示為Gv,稱為刪除結(jié)點(diǎn)運(yùn)算；設(shè)V1V，從G圖中刪去V1中所有結(jié)點(diǎn)及它們關(guān)聯(lián)的所有邊得到的圖表示為GV1,稱為刪除結(jié)點(diǎn)集運(yùn)算。設(shè)e=(u,v)E，從G圖中刪去邊e,將e的兩個(gè)端點(diǎn)u、v用一個(gè)新的結(jié)點(diǎn)w代替，將u,v關(guān)聯(lián)的所有邊都關(guān)聯(lián)結(jié)點(diǎn)w，稱為邊e的收縮，記為Ge。

20、設(shè)u,vV，在u,v之間加一條邊（u,v），稱為加新邊，表示為G(u,v)(或G+(u,v)。7.1.4 子圖與補(bǔ)圖定義7.1.18 設(shè)圖G=（V，例題在下圖中，(1)為圖G，(2)為G-e1, (3)為G-e1,e2， (4)為G-v3, (5)為G-v1,v3, (6)為Ge1。例題在下圖中，(1)為圖G，(2)為G-e1, (3)為G-子圖定義7.1.19 設(shè)G=（V，E）和G1=(V1，E1)是兩個(gè)圖。若V1V，且E1E，則稱G1是G的子圖，G是G1的母圖，記作G1 G。若G1 G且G1 G(即V1 V, 或E1 E)，則稱G1是G的真子圖。若G1G且V1 =V，則稱G1是G的生成子圖

21、。對(duì)圖G =（V，E），設(shè)V1V且V1 ，以V1為結(jié)點(diǎn)集，以兩端點(diǎn)均在V1中的全體邊為邊集的G的子圖，稱G1為G的由結(jié)點(diǎn)集V1導(dǎo)出的子圖，記為G（V1）。對(duì)圖G=（V，E），設(shè)E1E且E1 ，以E1為邊集，以E1中邊關(guān)聯(lián)的結(jié)點(diǎn)的全體為結(jié)點(diǎn)集的G的子圖，稱G1為G的由邊集E1導(dǎo)出的子圖，記為G（E1）。子圖定義7.1.19 設(shè)G=（V，E）和G1=(V1，E38例題(1),(2),(3)是(1)的子圖, (2),(3)是真子圖, (1)是母圖.(1),(3)是(1)的生成子圖.(2)是d,e,f 的導(dǎo)出子圖, 也是e5, e6, e7導(dǎo)出子圖.(3)是e1, e3, e5, e7的導(dǎo)出子圖aab

22、bccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)38例題(1),(2),(3)是(1)的子圖, (2),(3補(bǔ)圖定義7.1.20 設(shè)G=(V，E)是n階無(wú)向簡(jiǎn)單圖或有向簡(jiǎn)單圖。以V為結(jié)點(diǎn)，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱為G相對(duì)于完全圖的補(bǔ)圖，簡(jiǎn)稱G的補(bǔ)圖，記作G。 補(bǔ)圖定義7.1.20 設(shè)G=(V，E)是n階無(wú)向簡(jiǎn)單圖或例題證明：在任意6個(gè)人的集會(huì)上，總會(huì)有3個(gè)人以前互相認(rèn)識(shí)或有3個(gè)人以前互相不認(rèn)識(shí)（假設(shè)認(rèn)識(shí)是相互的）。即證明6個(gè)結(jié)點(diǎn)的無(wú)向圖G或其補(bǔ)圖G中至少有一個(gè)完全子圖K3。證明：

23、考慮完全圖K6,結(jié)點(diǎn)v1與其余5個(gè)結(jié)點(diǎn)各有一條邊相連，這5條邊一定有3條邊在G或G中。假設(shè)有3條邊在G圖中，這3條邊為（v1,v2）、（v1,v3）、（v1,v4）。對(duì)于結(jié)點(diǎn)v2、v3、v4，若在G中v2、v3、v4間無(wú)邊連接，則v2、v3、v4相互不認(rèn)識(shí)，如果至少存在一條邊，如v2、v3間存在一條邊，則在v1、v2、v3三個(gè)結(jié)點(diǎn)都有邊連接，構(gòu)成一個(gè)K3子圖，即有三個(gè)人相互認(rèn)識(shí)。因此，總會(huì)有三個(gè)人相互認(rèn)識(shí)或不認(rèn)識(shí)。例題證明：在任意6個(gè)人的集會(huì)上，總會(huì)有3個(gè)人以前互相認(rèn)識(shí)或有7.1.5 圖的同構(gòu)定義7.1.21 設(shè)兩個(gè)圖G=（V，E）和G=（V ，E），如果從V到V 存在雙射函數(shù)f，使得對(duì)于任意

24、的u，vV，(u，v) E, 當(dāng)且僅當(dāng)(f(u)，f(v) E ；如果在u，v間存在平行邊，則關(guān)聯(lián)于結(jié)點(diǎn)u，v的平行邊數(shù)與關(guān)聯(lián)于結(jié)點(diǎn)f(u)，f(v)的平行邊數(shù)相同，則稱G與G是同構(gòu)的，記作G G 。7.1.5 圖的同構(gòu)定義7.1.21 設(shè)兩個(gè)圖G=（V，E判斷兩個(gè)圖同構(gòu)的必要條件1)必須具有相同的頂點(diǎn)數(shù)；2)必須具有相同的邊數(shù)；3)度數(shù)相同的結(jié)點(diǎn)數(shù)相等。（對(duì)應(yīng)頂點(diǎn)的度數(shù)相同.）4)相同長(zhǎng)度的回路數(shù)相同。 判斷兩個(gè)圖同構(gòu)的必要條件1)必須具有相同的頂點(diǎn)數(shù)； 例題例6 畫(huà)出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖解 總度數(shù)為6, 分配給4個(gè)頂點(diǎn), 最大度為3, 且奇度頂點(diǎn)數(shù)為偶數(shù), 有下述3個(gè)度數(shù)列:

25、 (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.431,1,1,31,1,2,20,2,2,2 例題例6 畫(huà)出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖431,1例題例7 畫(huà)出3個(gè)以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的無(wú)向簡(jiǎn)單圖44例題例7 畫(huà)出3個(gè)以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的自互補(bǔ)圖定義7.1.22 如果一個(gè)圖同構(gòu)于它的補(bǔ)圖,則稱此圖為自互補(bǔ)圖。例8 試證明：一個(gè)圖為自互補(bǔ)圖，其對(duì)應(yīng)的完全圖的邊數(shù)必為偶數(shù)。 證明 設(shè)G為自互補(bǔ)圖，G有e條邊，并設(shè)G對(duì)應(yīng)的完全圖的邊數(shù)為m，則G的補(bǔ)圖的邊數(shù)為me。對(duì)于自互補(bǔ)圖G，有G G，所以e = me，m=2e 是偶數(shù)。 自

26、互補(bǔ)圖定義7.1.22 如果一個(gè)圖同構(gòu)于它的補(bǔ)圖,則稱7.2 通路與回路、連通的概念7.2.1 通路與回路7.2.2 連通的概念467.2 通路與回路、連通的概念7.2.1 通路與回路4647定義7.2.1 給定圖G=（V，E）中，以v0為起點(diǎn)，vn為終點(diǎn)的由結(jié)點(diǎn)和邊交替出現(xiàn)的序列v0e1v1e2v2vn-1envn稱為從結(jié)點(diǎn)v0到vn的長(zhǎng)度為n的通路。G是無(wú)向圖時(shí)，其中的邊ei的端點(diǎn)是vi-1和vi（i=1，2，n）；G是有向圖時(shí)，其中的有向邊ei的起點(diǎn)是vi-1，終點(diǎn)是vi（i=1，2，n）。 7.2.1 通路與回路47定義7.2.1 給定圖G=（V，E）中，以v0為起點(diǎn)，v通路與回路若一

27、條通路的起點(diǎn)和終點(diǎn)是同一點(diǎn)，稱它是一條回路。若通路中的所有邊互不相同，則稱它為簡(jiǎn)單通路或跡。若回路中的所有邊互不相同，則稱它為簡(jiǎn)單回路或閉跡。若通路中的所有結(jié)點(diǎn)互不相同，所有邊互不相同，則稱它為基本通路或初級(jí)通路、路徑。若回路中的所有結(jié)點(diǎn)互不相同，所有邊互不相同，則稱它為基本回路或初級(jí)回路、圈。一條通路或回路包含的邊的數(shù)目稱為通路或回路的長(zhǎng)度。如果一條回路的長(zhǎng)度為奇(偶)數(shù)，則稱為奇(偶)回路。通路與回路若一條通路的起點(diǎn)和終點(diǎn)是同一點(diǎn)，稱它是一條回路。例題v1e1v2e9v6e9v2e8v6e7v5是從結(jié)點(diǎn)v1到v5的長(zhǎng)度為5的通路，v2e4v4e5v5e6 v2e1v1e10v6是簡(jiǎn)單通路，

28、v2e4v4e5v5e6 v2e1v1e10v6e9v2是簡(jiǎn)單回路，v3e3v4e5v5e6v2e1v1e10v6是基本通路，v2e1v1e10v6e7v5e6 v2 是基本回路或圈。例題v1e1v2e9v6e9v2e8v6e7v5是從結(jié)點(diǎn)v1例題v1e2v2e5v4e4v3是從結(jié)點(diǎn)v1到v3的長(zhǎng)度為3的通路，v1e2v2e5v4e6v2是簡(jiǎn)單通路，v1e2v2e5v4e4v3 是基本通路。在有向圖中要注意邊的方向，通路上一條邊的終點(diǎn)是這條通路下一條邊的起點(diǎn)例題v1e2v2e5v4e4v3是從結(jié)點(diǎn)v1到v3的長(zhǎng)度為351說(shuō)明(1) 表示方法 按定義用頂點(diǎn)和邊的交替序列, =v0e1v1e2el

29、vl 用邊序列, =e1e2el 簡(jiǎn)單圖中, 用頂點(diǎn)序列, =v0v1vl(2) 在無(wú)向圖中, 長(zhǎng)度為1的圈由環(huán)構(gòu)成.長(zhǎng)度為2的圈由兩條平行邊構(gòu)成. 在無(wú)向簡(jiǎn)單圖中, 所有圈的長(zhǎng)度3. 在有向圖中, 長(zhǎng)度為1的圈由環(huán)構(gòu)成. 在有向簡(jiǎn)單圖中, 所有圈的長(zhǎng)度2.51說(shuō)明(1) 表示方法52說(shuō)明(續(xù))(3) 初級(jí)通路(回路)是簡(jiǎn)單通路(回路), 但反之不真初級(jí)通路非初級(jí)的簡(jiǎn)單通路初級(jí)回路非初級(jí)的簡(jiǎn)單回路52說(shuō)明(續(xù))(3) 初級(jí)通路(回路)是簡(jiǎn)單通路(回路), 定理定理7.2.1 在n階圖G中，若從結(jié)點(diǎn)u到v（uv）存在通路，則從u到v存在長(zhǎng)度小于或等于n-1的通路。證明： 見(jiàn)課本。推論 在n階圖G

30、中，若從結(jié)點(diǎn)u到v（uv）存在通路，則從u到v存在長(zhǎng)度小于或等于n1的基本通路。證明： 若通路中沒(méi)有相同的頂點(diǎn)(即基本通路), 長(zhǎng)度必 n1.若有相同的頂點(diǎn), 刪去這兩個(gè)頂點(diǎn)之間的這一段, 仍是u到v的通路. 重復(fù)進(jìn)行, 直到?jīng)]有相同的頂點(diǎn)為止.定理定理7.2.1 在n階圖G中，若從結(jié)點(diǎn)u到v（uv）定理定理7.2.2 在n階圖G中，若從結(jié)點(diǎn)u到自身存在回路，則回路的長(zhǎng)度小于或等于n。推論 在n階圖G中，若從結(jié)點(diǎn)u到自身存在回路，則一定存在從結(jié)點(diǎn)u到自身的長(zhǎng)度小于或等于n的基本回路。定理定理7.2.2 在n階圖G中，若從結(jié)點(diǎn)u到自身存在回路55短程線與距離設(shè)u,v為圖G中任意兩個(gè)結(jié)點(diǎn)，u與v之

31、間的短程線:u與v之間長(zhǎng)度最短的通路(設(shè)u與v連通)u與v之間的距離d(u,v):u與v之間短程線的長(zhǎng)度若u與v不連通, 規(guī)定d(u,v)=.性質(zhì)：(1) d(u,v)0, 且d(u,v)=0 u=v(2) d(u,v)=d(v,u)(3) d(u,v)+d(v,w)d(u,w) 例如 a與e之間的短程線:ace,afe. d(a,e)=2, d(a,h)=abcde f ghi55短程線與距離設(shè)u,v為圖G中任意兩個(gè)結(jié)點(diǎn)，例如 a與e通路的應(yīng)用六度分割理論電影演員合作圖中的貝肯數(shù)（bacon number）論文合作關(guān)系圖中的埃德斯數(shù)(Erds number)通路的應(yīng)用六度分割理論7.2.2

32、連通的概念定義7.2.3 若無(wú)向圖G中任意兩結(jié)點(diǎn)間都有一條通路(長(zhǎng)度1)，則稱G是連通圖；否則，稱G是非連通圖。連通關(guān)系 R=| u,v V且u與v連通. R是等價(jià)關(guān)系連通分支: V關(guān)于R的等價(jià)類的導(dǎo)出子圖設(shè)V/R=V1,V2,Vk, G的連通分支為GV1,GV2,GVk連通分支數(shù)W(G)=kG是連通圖 W(G)=1 7.2.2 連通的概念定義7.2.3 若無(wú)向圖G中任意兩結(jié)定理定理7.2.3 設(shè)簡(jiǎn)單圖G=（V，E）有n個(gè)結(jié)點(diǎn)，e條邊，w個(gè)連通分支，則n-we。證明 (用歸納法來(lái)證明)（1）當(dāng)e=0時(shí)，也就是對(duì)于n個(gè)結(jié)點(diǎn)的零圖，w=n，則n-we成立。 （2）假定邊數(shù)為e-1的簡(jiǎn)單圖結(jié)論成立。

33、對(duì)于邊數(shù)為e的簡(jiǎn)單圖G，從G中刪去一條邊，得到邊數(shù)為e-1的簡(jiǎn)單圖G。分兩種情況分析：(a) 刪去一條邊的圖G的連通分支數(shù)沒(méi)有增加，即G有n個(gè)結(jié)點(diǎn)，w個(gè)分支，e-1條邊，由歸納假設(shè)有n-w e-1，所以n-we成立。(b) 刪去一條邊的圖G的連通分支數(shù)增加，即G有n個(gè)結(jié)點(diǎn)，w+1個(gè)分支，e-1條邊，由歸納假設(shè)有n-(w+1) e-1,所以n-we成立。定理定理7.2.3 設(shè)簡(jiǎn)單圖G=（V，E）有n個(gè)結(jié)點(diǎn)，e條點(diǎn)割集和邊割集定義7.2.4 設(shè)無(wú)向圖G=(V,E), VV, 若W(GV)W(G)且VV, W(GV)=W(G), 則稱V為G的點(diǎn)割集. 若v為點(diǎn)割集, 則稱v為割點(diǎn).設(shè)EE, 若W(G

34、E)W(G)且EE, W(GE)=W(G), 則稱E為G的邊割集. 若e為邊割集, 則稱e為割邊或橋.abcde fge1e2e3e4e5e6e7e8e9e, f點(diǎn)割集:e,f ,割點(diǎn):c,d 橋:e8,e9邊割集:e8,e9,e1,e2,e1, e3, e6,e1, e3, e4, e7點(diǎn)割集和邊割集定義7.2.4 設(shè)無(wú)向圖G=(V,E), 60說(shuō)明Kn無(wú)點(diǎn)割集n階零圖既無(wú)點(diǎn)割集，也無(wú)邊割集.若G連通，E為邊割集，則W(GE)=2若G連通，V為點(diǎn)割集，則W(GV)260說(shuō)明Kn無(wú)點(diǎn)割集例題例7.2.2 試證明2n個(gè)城市，如果每個(gè)城市至少可以和另外n個(gè)城市可以相互直航，那么這2n個(gè)城市中任何兩

35、個(gè)之間可互相通航 (有些可能要通過(guò)另外的城市中轉(zhuǎn))（即證明:2n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度數(shù) n的簡(jiǎn)單圖是連通的。）證明 設(shè)有2n個(gè)結(jié)點(diǎn)的圖G不連通，則G中至少包含兩個(gè)連通分支,而且必有一個(gè)分支的結(jié)點(diǎn)數(shù) n，即使這個(gè)分支是完全圖，其每個(gè)結(jié)點(diǎn)的度數(shù)d(v) n-1，和d(v) n矛盾。所以圖G只有一個(gè)連通分支，G是連通的。例題例7.2.2 試證明2n個(gè)城市，如果每個(gè)城市至少可以有向圖的連通性及其分類定義7.2.5 設(shè)G=（V，E）是一個(gè)有向圖，對(duì)G中任意兩個(gè)結(jié)點(diǎn)u和v，若從u到v存在通路，則稱由u到v是可達(dá)的，否則稱由u到v是不可達(dá)的。若從u到v存在通路，且從v到u存在通路，則稱u和v是相互可達(dá)的。規(guī)

36、定一個(gè)結(jié)點(diǎn)到自己總是可達(dá)的。有向圖的結(jié)點(diǎn)之間的可達(dá)關(guān)系具有自反性和傳遞性，不具有對(duì)稱性。62有向圖的連通性及其分類定義7.2.5 設(shè)G=（V，E）是一個(gè)有向連通圖定義7.2.6 設(shè)G=（V，E）是有向圖。如果圖G的任意兩個(gè)結(jié)點(diǎn)間至少?gòu)囊粋€(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱G是單向連通的。如果圖G的任意兩個(gè)結(jié)點(diǎn)間是互相可達(dá)的，則稱G是強(qiáng)連通的。如果圖G在略去有向邊的方向后得到的無(wú)向圖是連通的，則稱G是弱連通的。 具有三種連通性中的任何一種的有向圖都稱為有向連通圖。有向連通圖定義7.2.6 設(shè)G=（V，E）是有向圖。64實(shí)例 強(qiáng)連通單連通弱連通64實(shí)例 強(qiáng)連通單連通弱連通頂點(diǎn)集上的互相可達(dá)關(guān)系 對(duì)于u

37、，vV，u與v有關(guān)系，當(dāng)且僅當(dāng)從u可達(dá)v，并且從v可達(dá)u。頂點(diǎn)集上的互相可達(dá)關(guān)系是等價(jià)關(guān)系。 利用互相可達(dá)關(guān)系可將頂點(diǎn)集V劃分為V1，V2，,Vw,每個(gè)Vi的任兩個(gè)頂點(diǎn)都是互相可達(dá)的.所以每個(gè)Vi導(dǎo)出的子圖Gi是強(qiáng)連通的,稱為G的一個(gè)強(qiáng)分圖.頂點(diǎn)集上的互相可達(dá)關(guān)系頂點(diǎn)集上的互相可達(dá)關(guān)系 對(duì)于u，vV，u與v有關(guān)系，有向圖的強(qiáng)連通分支.GG(V1)G(V2)G(V3)V1=v1,v7 V2=v2,v3, v5,v6 V3=v4 注意:有向圖中不一定每條邊都一定屬于一個(gè)強(qiáng)連通分支.而無(wú)向圖中每條邊必屬于一個(gè)連通分支. 有向圖中每個(gè)頂點(diǎn)必屬于一個(gè)強(qiáng)連通分支.定理7.2.4 ：有向圖G是強(qiáng)連通的當(dāng)且僅

38、當(dāng)G中存在經(jīng)過(guò)每個(gè)結(jié)點(diǎn)的回路。有向圖的強(qiáng)連通分支.GG(V1)G(V2)G(V3)V1=有向圖的應(yīng)用資源分配圖是有向圖：G=（V，E）,其中V是頂點(diǎn)的集合，E是邊的集合。頂點(diǎn)集合分為兩部分：（1）P=P1,P2,Pn,它由進(jìn)程集合的所有活動(dòng)進(jìn)程組成。（2） R=r1,r2,rm,它由進(jìn)程集合所涉及的全部資源類型組成。邊集合分為以下兩種：（1）申請(qǐng)邊(Pi，rj),表示進(jìn)程Pi申請(qǐng)一個(gè)單位的rj資源，但當(dāng)前Pi在等待該資源。（2）賦給邊(rj，Pi),表示有一個(gè)單位的rj資源已分配給進(jìn)程Pi。有向圖的應(yīng)用資源分配圖是有向圖：G=（V，E）,其中V是頂點(diǎn)資源分配圖（1）G1 (2)G2圖G1中有一

39、個(gè)回路，所以是死鎖狀態(tài)。圖G2也有一個(gè)回路：P1r1P3r2P1，然而沒(méi)有出現(xiàn)死鎖。因?yàn)檫M(jìn)程P2和P4能釋放占有的資源r1和r2,然后就可以將r1和r2分給P1和P3,這樣環(huán)路就打開(kāi)了。資源分配圖中存在回路是死鎖存在的必要條件，但不是充分條件。P1P3r2r1r1P1P2P3P4r2資源分配圖（1）G1 697.3 圖的表示7.3.1 鄰接表7.3.2 鄰接矩陣7.3.3 可達(dá)矩陣7.3.4 關(guān)聯(lián)矩陣697.3 圖的表示7.3.1 鄰接表70定義7.3.1 列出圖的每一個(gè)結(jié)點(diǎn)和它的所有鄰接結(jié)點(diǎn)的表稱為鄰接表。例 1 用鄰接表表示無(wú)向簡(jiǎn)單圖。例 2 用鄰接表表示有向簡(jiǎn)單圖。7.3.1 鄰接表無(wú)向

40、簡(jiǎn)單圖的鄰接表結(jié)點(diǎn)鄰接結(jié)點(diǎn)ab,cba,c,dca,b,d,edb,cec有向圖的鄰接表起點(diǎn)終點(diǎn)abbc,dca,b,d,edeb,c70定義7.3.1 列出圖的每一個(gè)結(jié)點(diǎn)和它的所有鄰接結(jié)點(diǎn)的表7.3.2 鄰接矩陣定義7.3.2 設(shè)圖G=（V，E）是有向圖，V=v1，v2，vn，G的鄰接矩陣為 ，其中7.3.2 鄰接矩陣定義7.3.2 設(shè)圖G=（V，E）是72例題A=1 1 0 00 0 1 01 0 0 01 0 2 0v1v2v3v472例題A=1 1 0 0v1v2v3v4有向圖中的通路數(shù)與回路數(shù)定理7.3.1 設(shè)A是有向圖G=（V，E）的鄰接矩陣，V=v1，v2，vn， ，則 表示G中

41、從vi到vj的長(zhǎng)度為k的所有有向路的數(shù)目，其中 是從vi到自身的長(zhǎng)度為k的所有回路的數(shù)目。證明 用歸納法證明，對(duì)k作歸納。當(dāng)k=1時(shí)，由鄰接矩陣的定義知結(jié)論成立。設(shè)k=m時(shí)，結(jié)論成立。當(dāng)k=m+1時(shí)，有 ，從而 。顯然 等于從vi出發(fā)經(jīng)vp到vj的長(zhǎng)度為m+1的有向路的數(shù)目。由于p的任意性 等于G中從vi到vj的長(zhǎng)度為m+1的所有有向路的數(shù)目。73有向圖中的通路數(shù)與回路數(shù)定理7.3.1 設(shè)A是有向圖G=有向圖中的通路數(shù)與回路數(shù)(續(xù))推論設(shè)矩陣 則Bl中的元素表示圖G中從結(jié)點(diǎn)vi到vj的長(zhǎng)度小于等于l的所有通路的總數(shù)。其中bii(l)是從vi到自身的長(zhǎng)度小于等于l的所有回路的總數(shù)目。74有向圖中

42、的通路數(shù)與回路數(shù)(續(xù))推論設(shè)矩陣 74實(shí)例(續(xù)) 75A=1 1 0 00 0 1 01 0 0 01 0 2 0A2=1 1 1 01 0 0 01 1 0 03 1 0 0A3=2 1 1 01 1 0 01 1 0 03 3 1 0A4=3 2 1 01 1 0 02 1 1 04 3 1 0v1到v2長(zhǎng)為3的通路有1條v1到v3長(zhǎng)為3的通路有1條v1到自身長(zhǎng)為4的回路有3條D中長(zhǎng)為3的通路共有15條,其中回路3條v1v2v3v4實(shí)例(續(xù)) 75A=1 1 0 0A2=1 1 無(wú)向圖的鄰接矩陣定義7.3.3 設(shè)圖G=（V，E）是無(wú)向圖，V=v1，v2，vn，G的鄰接矩陣為 ，其中例3 寫(xiě)

43、出如下圖所示的無(wú)向圖G的鄰接矩陣。解 鄰接矩陣為無(wú)向圖的鄰接矩陣定義7.3.3 設(shè)圖G=（V，E）是無(wú)向圖例題例4 畫(huà)出給定的鄰接矩陣所表示的圖。（1） （2） （a） （b）abcabc (c)v1v2v4v3解 （1）鄰接矩陣（1）所表示的圖可以是無(wú)向圖（a）或有向圖（b）。 （2）鄰接矩陣（2）所表示的圖見(jiàn)圖（c)。例題例4 畫(huà)出給定的鄰接矩陣所表示的圖。abcabcv1例題例5 判定下面的鄰接矩陣A所表示的圖G是否強(qiáng)連通圖？解因?yàn)锽3中存在為0的元素，所以圖G不是強(qiáng)連通圖。v1v2v3例題例5 判定下面的鄰接矩陣A所表示的圖G是否強(qiáng)連通圖？v1例題例6 判斷下面的兩個(gè)圖是否同構(gòu)？解 兩

44、個(gè)圖的鄰接矩陣為： 將矩陣A2的第2行元素和第3行元素交換，得到矩陣 ，然后將矩陣 的第2列元素和第3列元素交換，得到矩陣 。 矩陣 和矩陣 相同，所以兩個(gè)圖同構(gòu)。例題例6 判斷下面的兩個(gè)圖是否同構(gòu)？ 7.3.3 可達(dá)矩陣定義7.3.4 設(shè)圖G=（V，E）是有向圖，V=v1，v2，vn，A是G的鄰接矩陣， G的可達(dá)矩陣為 ， i，j=1,2，n, 其中 7.3.3 可達(dá)矩陣定義7.3.4 設(shè)圖G=（V，E）是例題 寫(xiě)出右圖的可達(dá)矩陣。解 所以可達(dá)矩陣為例題 寫(xiě)出右圖的可達(dá)矩陣。由可達(dá)矩陣求強(qiáng)連通分支對(duì)可達(dá)矩陣P求轉(zhuǎn)置PT，PT中的(i,j)的元素為 ，定義一個(gè)矩陣P PT，使得它的(i,j)的元素為 ，于是矩陣P PT的第i行的“1”對(duì)應(yīng)的結(jié)點(diǎn)組成一個(gè)含有結(jié)點(diǎn)vi的強(qiáng)連通分支。矩陣P PT的第2行的兩個(gè)“1”表明結(jié)點(diǎn)v2和v3是一個(gè)強(qiáng)連通分支。由可達(dá)矩陣求強(qiáng)連通分支對(duì)可達(dá)矩陣P求轉(zhuǎn)置PT，PT中的(i,83則稱(mij)nm為G的關(guān)聯(lián)矩陣, 記為M(G).定義7.3.5 設(shè)圖G=(V,E)是無(wú)環(huán)的有向圖, V=v1, v2, , vn, E=e1, e2, , em. 令7.3.4 關(guān)聯(lián)矩陣83則稱(mij)nm為G的關(guān)聯(lián)矩陣, 記為M(G).定義84例題e