ch10圖的基本概念

1、n如何找到物流運輸?shù)淖顑?yōu)路徑？n如何找到最優(yōu)的網(wǎng)絡(luò)通信線路？n如果你想周游全國所有城市，如何設(shè)計旅游線路？n化學(xué)化合物分析：結(jié)構(gòu)是否相同？n程序結(jié)構(gòu)度量：程序是否結(jié)構(gòu)相似？n如何為考試分配教室，使得資源利用率最優(yōu)？n如何安排工作流程而達(dá)到最高效率？n如何設(shè)計為眾多的電視臺頻道分配最優(yōu)方案？n如何設(shè)計通信編碼以提高信息傳輸效率？n操作系統(tǒng)中,如何調(diào)度進(jìn)程而使得系統(tǒng)效率最優(yōu)？n如何設(shè)計集成電路線路布局而達(dá)到最優(yōu)效率？n如何設(shè)計計算機鼓輪？n七枚同重量硬幣與一枚較輕的偽幣，使用天平秤多少次就能找出偽幣？n如何設(shè)計下棋程序？nn-皇后問題n最少用幾種顏色就能將世界地圖都著色？n如何使箱子盡可能裝滿物體

2、？ n一個船夫要把一只狼，一只羊和一棵白菜運過河。問題是當(dāng)人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個。那么他怎樣才能把三者都運過河呢？n旅行商問題：tsp問題n中國郵路問題n地圖著色問題：四色定理n最短路徑問題n網(wǎng)絡(luò)流n匹配n組合計數(shù)主要內(nèi)容主要內(nèi)容 1) 1) 圖的基本術(shù)語；圖的基本術(shù)語；2) 2) 結(jié)點的度，子圖，完全圖；結(jié)點的度，子圖，完全圖； 3) 3) 圖的連通性；圖的連通性；4) 4) 圖的運算，圖的矩陣表示及其性質(zhì)；圖的運算，圖的矩陣表示及其性質(zhì)；5) 5) 圖的同構(gòu)；圖的同構(gòu)；6)6) 歐拉圖與哈密爾頓圖的性質(zhì)及其應(yīng)用。歐拉圖與哈密爾頓圖的性質(zhì)及其應(yīng)用。 1

3、0.1 10.1 圖論概述圖論概述 圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載體，其突出的特點是直觀、形象。圖論，顧體，其突出的特點是直觀、形象。圖論，顧名思義是運用數(shù)學(xué)手段研究圖的性質(zhì)的理論，名思義是運用數(shù)學(xué)手段研究圖的性質(zhì)的理論，但這里的圖不是平面坐標(biāo)系中的函數(shù)，而是但這里的圖不是平面坐標(biāo)系中的函數(shù)，而是由一些點和連接這些點的線組成的結(jié)構(gòu)。圖由一些點和連接這些點的線組成的結(jié)構(gòu)。圖論是有許多應(yīng)用的古老學(xué)科，也一直以來都論是有許多應(yīng)用的古老學(xué)科，也一直以來都是一個熱門學(xué)科，它已經(jīng)被廣泛應(yīng)用于計算是一個熱門學(xué)科，它已經(jīng)被廣泛應(yīng)用于計算機科學(xué)、化學(xué)、運籌學(xué)、心理學(xué)等很多領(lǐng)

4、域。機科學(xué)、化學(xué)、運籌學(xué)、心理學(xué)等很多領(lǐng)域。10.2 10.2 圖與圖模型圖與圖模型 例例10.210.2 時間安排問題。某大學(xué)計算機學(xué)院的某教研時間安排問題。某大學(xué)計算機學(xué)院的某教研組共有組共有1010名教師，他們分別參加名教師，他們分別參加7 7個班級的討論課，個班級的討論課，每個班級可能同時需要多位教師參加，有的教師可每個班級可能同時需要多位教師參加，有的教師可能需要參加多個班級的討論，每個班級必須單獨開能需要參加多個班級的討論，每個班級必須單獨開展討論課，則如何安排才使得所有班級在最短時間展討論課，則如何安排才使得所有班級在最短時間段內(nèi)完成討論課？參加各個班級討論課的教師情況段內(nèi)完成討

5、論課？參加各個班級討論課的教師情況如下（如下（c ci i為班級編號，數(shù)字為班級編號，數(shù)字1-101-10為教師編號）：為教師編號）： c c1=1=1，2 2，33，c c2=1=1，3 3，4 4，55，c c3=2=2，5 5，6 6，77，c c4=2=2，6 6，77，c c5=4=4，7 7，8 8，99，c c6=8=8，9 9，1010，c c7=1=1，3 3，9 9，1010。 10.2 10.2 圖與圖模型圖與圖模型 這樣，一位教師如果給多個班級都授課，則在這樣，一位教師如果給多個班級都授課，則在討論課時間安排方面則不能沖突，如教師討論課時間安排方面則不能沖突，如教師1

6、1不能同不能同時參加班級時參加班級c c1 1與班級與班級c c2 2的討論課。這種情況可以用的討論課。這種情況可以用下下圖直觀地表示。圖直觀地表示。 在在上上圖中，共用了圖中，共用了7 7個小圓圈來表示班級，圓個小圓圈來表示班級，圓圈之間的線段表示存在同一個教師參加該二班級的圈之間的線段表示存在同一個教師參加該二班級的討論課，這樣就不能安排該二班級同時開展討論課。討論課，這樣就不能安排該二班級同時開展討論課。顯然，這就給上述問題構(gòu)建了一個直觀的圖的模型。顯然，這就給上述問題構(gòu)建了一個直觀的圖的模型。 c c6c c5c c4c c2c c3c c7c c110.2 10.2 圖與圖模型圖與圖

7、模型 定義定義10.110.1 圖圖g g包括一個非空的對象的集合包括一個非空的對象的集合v v與與有限的兩個對象構(gòu)成的有限的兩個對象構(gòu)成的v v的無序?qū)?gòu)成的集的無序?qū)?gòu)成的集合合e e，前者稱為的，前者稱為的結(jié)點集結(jié)點集，后者稱為，后者稱為邊集邊集。 令令v=vv=v1 1,v,v2 2, ,v,vn n 是包含是包含n n個結(jié)點的集個結(jié)點的集合，其合，其m m條邊的集合條邊的集合e=ee=e1 1,e,e2 2, ,e,em m ，其中，其中，每一條邊都是集合每一條邊都是集合v v的二元子集，如邊的二元子集，如邊e ei i=u=u，vv，常常簡記為，常常簡記為uvuv或或vuvu，其中

8、，其中u u、v v稱為邊稱為邊uvuv的的端點端點。這樣，一個圖事實上就是這樣，一個圖事實上就是v v與與e e構(gòu)成構(gòu)成的序偶，常常被記作的序偶，常常被記作g=(v,e)g=(v,e)。于是，也常。于是，也常常用常用v(g)v(g)和和e(g)e(g)來表示某一個圖來表示某一個圖g g的結(jié)點集的結(jié)點集與邊集。當(dāng)然，也可以使用其它符號來表示與邊集。當(dāng)然，也可以使用其它符號來表示圖，如用圖，如用f f或或h h，甚至，甚至g g1 1等等。等等。10.2 10.2 圖與圖模型圖與圖模型 集合集合v(g)v(g)的基數(shù)的基數(shù)n n表示表示圖圖g g的階的階（orderorder），集合），集合e(

9、g)e(g)的基數(shù)的基數(shù)m m表示表示圖圖g g的規(guī)模的規(guī)模（sizesize），有時也將圖），有時也將圖g g記作記作(n,m(n,m) )。在圖。在圖g g中，若邊集中，若邊集e(g)=,e(g)=,則稱則稱g g為為零圖零圖（null graphnull graph），此時，又若），此時，又若g g為為n n階圖，則稱階圖，則稱g g為為n n階零圖階零圖，記作，記作n nn n，特別地，稱，特別地，稱n n1 1為為平凡圖平凡圖（trivial trivial graphgraph）。在圖的定義中規(guī)定結(jié)點集）。在圖的定義中規(guī)定結(jié)點集v v為非空集，但為非空集，但在圖的運算中可能產(chǎn)生結(jié)點

10、集為空集的運算結(jié)果，在圖的運算中可能產(chǎn)生結(jié)點集為空集的運算結(jié)果，為此規(guī)定結(jié)點集為空集的圖為為此規(guī)定結(jié)點集為空集的圖為空圖空圖（empty graphempty graph），），并將空圖記為并將空圖記為。階為有限的圖稱為。階為有限的圖稱為有限圖有限圖(finite (finite graph)graph)，否則稱為，否則稱為無限圖無限圖(infinite graph)(infinite graph)。結(jié)點結(jié)點沒有標(biāo)號的圖稱為沒有標(biāo)號的圖稱為非標(biāo)號圖非標(biāo)號圖（unlabeled graphunlabeled graph），），否則為否則為標(biāo)號圖標(biāo)號圖（labeled graphlabeled g

11、raph）。）。 10.2 10.2 圖與圖模型圖與圖模型 如果圖中存在某兩條邊的端點都相如果圖中存在某兩條邊的端點都相同，則稱該圖為同，則稱該圖為多重圖多重圖(multigraph(multigraph) )，該兩條邊稱為該兩條邊稱為平行邊平行邊。如果一條邊關(guān)聯(lián)。如果一條邊關(guān)聯(lián)的兩個結(jié)點是相同的結(jié)點，則稱該邊為的兩個結(jié)點是相同的結(jié)點，則稱該邊為圈圈或或自環(huán)自環(huán)(loop)(loop)。不存在平行邊與圈的。不存在平行邊與圈的圖即稱為圖即稱為簡單圖簡單圖(simple graph)(simple graph)。 10.2 10.2 圖與圖模型圖與圖模型 定義定義10.210.2 如果如果uvuv

12、是圖是圖g g的邊，記為的邊，記為e e，即，即uvuv e(ge(g),),則則稱結(jié)點稱結(jié)點u u和和v v鄰接鄰接(adjacent),(adjacent),否則稱結(jié)點否則稱結(jié)點u u與與v v非鄰接非鄰接。這里，也稱結(jié)點這里，也稱結(jié)點u u或或v v與邊與邊e e是是關(guān)聯(lián)關(guān)聯(lián)（incidentincident）關(guān)系。）關(guān)系。與同一個結(jié)點關(guān)聯(lián)的兩條邊稱為與同一個結(jié)點關(guān)聯(lián)的兩條邊稱為鄰接邊鄰接邊。與結(jié)點。與結(jié)點v v關(guān)關(guān)聯(lián)的邊數(shù)稱為聯(lián)的邊數(shù)稱為結(jié)點結(jié)點v v的度的度，記作，記作deg(vdeg(v) )。與結(jié)點。與結(jié)點v v關(guān)關(guān)聯(lián)的環(huán)對聯(lián)的環(huán)對v v的度數(shù)的貢獻(xiàn)要計算兩次。如果結(jié)點的度數(shù)的貢

13、獻(xiàn)要計算兩次。如果結(jié)點v v的的度為度為0 0，則稱之為，則稱之為孤立點孤立點(isolated vertex)(isolated vertex)。一度。一度的結(jié)點稱為的結(jié)點稱為懸掛點懸掛點（pendant vertexpendant vertex）。圖）。圖g g的所有的所有結(jié)點度數(shù)的最小度數(shù)稱為結(jié)點度數(shù)的最小度數(shù)稱為g g的最小度的最小度，記作，記作 (g)(g)，而，而所有結(jié)點度數(shù)的最大者稱為所有結(jié)點度數(shù)的最大者稱為g g的最大度的最大度，記作，記作 (g)(g)。各結(jié)點的度均相同的圖稱為各結(jié)點的度均相同的圖稱為正則圖正則圖（regular regular graphgraph）。各結(jié)點

14、度均為）。各結(jié)點度均為k k的正則圖稱為的正則圖稱為k-k-正則圖正則圖。 10.2 10.2 圖與圖模型圖與圖模型 定義定義10.310.3 如果圖的每條邊是二結(jié)點構(gòu)成的有序?qū)Γ绻麍D的每條邊是二結(jié)點構(gòu)成的有序?qū)?，則該圖稱為則該圖稱為有向圖有向圖(directed graph)(directed graph)，上文所定義，上文所定義的圖都是的圖都是無向圖無向圖(undirected graph)(undirected graph)。有向圖中邊。有向圖中邊uvuv與與vuvu是兩條不同的邊，對于邊是兩條不同的邊，對于邊uvuv，稱，稱u u為為始點始點，v v為為終點終點。 有向圖中，結(jié)點有向

15、圖中，結(jié)點v v的度分為的度分為入度入度，即與該結(jié)點相，即與該結(jié)點相關(guān)聯(lián)并以該結(jié)點為終點的邊的數(shù)目，以及關(guān)聯(lián)并以該結(jié)點為終點的邊的數(shù)目，以及出度出度, ,即與即與該結(jié)點相關(guān)聯(lián)并以該結(jié)點為始點的邊的數(shù)目該結(jié)點相關(guān)聯(lián)并以該結(jié)點為始點的邊的數(shù)目, ,分別記分別記作作degdeg+ +(v(v) )，degdeg- -(v)(v)。 10.2 10.2 圖與圖模型圖與圖模型無向圖無向圖有向圖有向圖10.2 10.2 圖與圖模型圖與圖模型10.2 10.2 圖與圖模型圖與圖模型 練習(xí)練習(xí)1 1 設(shè)設(shè)g=(v,e)g=(v,e)是一無向圖，是一無向圖，v=vv=v1 1,v,v2 2, , v, v8 8

16、 ，e=(ve=(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v3 3,v,v1 1),(v),(v1 1,v,v5 5),(v),(v5 5,v,v4 4), ), (v(v4 4,v,v3 3),(v),(v7 7,v,v8 8) （1 1）畫出）畫出g g的圖解；的圖解； （2 2）指出與）指出與v v3 3鄰接的結(jié)點，以及和鄰接的結(jié)點，以及和v v3 3關(guān)聯(lián)的邊；關(guān)聯(lián)的邊； （3 3）指出與）指出與(v(v2 2,v,v3 3) )鄰接的邊和與鄰接的邊和與(v(v2 2,v,v3 3) )關(guān)聯(lián)的結(jié)點；關(guān)聯(lián)的結(jié)點； （4 4）該圖是否有孤立結(jié)點和孤立邊？）該圖

17、是否有孤立結(jié)點和孤立邊？ （5 5）求出各結(jié)點的度數(shù)，并判斷是否是完全圖和正）求出各結(jié)點的度數(shù)，并判斷是否是完全圖和正則圖？則圖？ （6 6）該）該(n,m(n,m) )圖中，圖中，n=n=？，？，m=m=？ 10.2 10.2 圖與圖模型圖與圖模型 圖的邊數(shù)與結(jié)點數(shù)的關(guān)系是圖最為重要的屬性，圖的邊數(shù)與結(jié)點數(shù)的關(guān)系是圖最為重要的屬性，結(jié)點的度數(shù)滿足一個非常簡單的關(guān)系，即圖的每條結(jié)點的度數(shù)滿足一個非常簡單的關(guān)系，即圖的每條邊都關(guān)聯(lián)于兩個結(jié)點，則每條邊對圖結(jié)點度數(shù)之和邊都關(guān)聯(lián)于兩個結(jié)點，則每條邊對圖結(jié)點度數(shù)之和的貢獻(xiàn)為的貢獻(xiàn)為2 2，從而有下面的定理：，從而有下面的定理： 定理定理10.110.1

18、（歐拉定理）（歐拉定理）在任何圖中，結(jié)點度的總和在任何圖中，結(jié)點度的總和等于邊數(shù)的兩倍。等于邊數(shù)的兩倍。 該定理也被稱為該定理也被稱為握手定理握手定理，被認(rèn)為圖論第一定，被認(rèn)為圖論第一定理，可以用于證明圖的相關(guān)性質(zhì)。理，可以用于證明圖的相關(guān)性質(zhì)。 推論推論10.110.1 在任意圖中，奇數(shù)度的結(jié)點個數(shù)為偶數(shù)。在任意圖中，奇數(shù)度的結(jié)點個數(shù)為偶數(shù)。 10.2 10.2 圖與圖模型圖與圖模型 例例10.310.3 設(shè)設(shè)g=g=，|v|=n, |e|=m|v|=n, |e|=m，證明：，證明： (g)2m/n(g)2m/n (g)(g)。 證明證明 由歐拉定理，由歐拉定理， deg(vdeg(v) )

19、=2m=2m。 對任意的對任意的v v v v，有有 (g)deg(v)(g)deg(v) (g(g) )，于于是是 n n (g)(g) deg(v)deg(v)nn (g(g) ) n n (g)2mn(g)2mn (g)(g) 即即 (g)2m/n(g)2m/n (g)(g)。 10.2 10.2 圖與圖模型圖與圖模型 例例10.410.4 請證明：有向圖中，所有結(jié)點出度請證明：有向圖中，所有結(jié)點出度之和等于所有結(jié)點入度之和。之和等于所有結(jié)點入度之和。 證明證明 在有向圖中，任意一條邊都有一個始在有向圖中，任意一條邊都有一個始點和一個終點，因而結(jié)論成立。點和一個終點，因而結(jié)論成立。 10

20、.2 10.2 圖與圖模型圖與圖模型 練習(xí)練習(xí)2 2 設(shè)設(shè)g=(v,e)g=(v,e)有有1212條邊，有條邊，有6 6個度為個度為3 3的的結(jié)點，其余結(jié)點的度數(shù)均小于結(jié)點，其余結(jié)點的度數(shù)均小于3 3，問，問g g中至少中至少有多少個結(jié)點？有多少個結(jié)點？10.2 10.2 圖與圖模型圖與圖模型 例例10.510.5 十字路口交通管理問題。下圖十字路口交通管理問題。下圖(a)(a)是某繁忙的城市十字是某繁忙的城市十字路口交通管理示意圖，其中路口交通管理示意圖，其中c c1 1 c c9 9表示可能的行車路線，為安全表示可能的行車路線，為安全考慮，顯然考慮，顯然c c1 1、c c5 5可以同時進(jìn)

21、入十字路口，但可以同時進(jìn)入十字路口，但c c1 1與與c c8 8卻不能同卻不能同時進(jìn)入十字路口，等等。本問題可以用圖來建模，如下圖（時進(jìn)入十字路口，等等。本問題可以用圖來建模，如下圖（b b）所示。其中，結(jié)點集為所有行車路線的構(gòu)成的集合，結(jié)點之間所示。其中，結(jié)點集為所有行車路線的構(gòu)成的集合，結(jié)點之間的邊表示相應(yīng)的二行車道不能同時開通。顯然此圖可以用于十的邊表示相應(yīng)的二行車道不能同時開通。顯然此圖可以用于十字路口交通信號燈的設(shè)計。字路口交通信號燈的設(shè)計。c4 c5c1 c2c3c8c7c6c3c4c9c1c5c2c7 c6c9 c8(a)(b)10.2 10.2 圖與圖模型圖與圖模型 例例10

22、.610.6 旅行售貨員問題?，F(xiàn)有旅行售貨員問題?，F(xiàn)有一個筆記本計算機代理商要從一個筆記本計算機代理商要從其所在的城市北京出發(fā)，乘飛其所在的城市北京出發(fā)，乘飛機去機去5 5個城市，然后回到出發(fā)點。個城市，然后回到出發(fā)點。如右圖所示。圖中結(jié)點代表城如右圖所示。圖中結(jié)點代表城市，邊代表城市間的直達(dá)航線。市，邊代表城市間的直達(dá)航線。他怎樣才能出差到每個城市恰他怎樣才能出差到每個城市恰巧一次，最后回到北京呢？巧一次，最后回到北京呢？ ?？诤？诔啥汲啥急本┍本┪錆h武漢廣州廣州上海上海這個問題的解答本身比較簡單，如可以選擇線路為北京這個問題的解答本身比較簡單，如可以選擇線路為北京- -成都成都- -武漢武

23、漢- -?？诤？? -廣州廣州- -上海上海- -北京。但對于更為復(fù)雜的北京。但對于更為復(fù)雜的情況就很難直接找到好的解答。本問題與后文將研究的情況就很難直接找到好的解答。本問題與后文將研究的hamiltonhamilton圖有關(guān)，將在那里做詳細(xì)討論。圖有關(guān)，將在那里做詳細(xì)討論。 10.2 10.2 圖與圖模型圖與圖模型 例例10.710.7 優(yōu)先圖。通過并發(fā)地執(zhí)行某些語句，計算機程序可以執(zhí)優(yōu)先圖。通過并發(fā)地執(zhí)行某些語句，計算機程序可以執(zhí)行得更快。如何確定哪些語句可以并發(fā)執(zhí)行是非常重要的，這需行得更快。如何確定哪些語句可以并發(fā)執(zhí)行是非常重要的，這需要分析清楚程序中語句之間的優(yōu)先關(guān)系。這種優(yōu)先關(guān)系

24、可以用有要分析清楚程序中語句之間的優(yōu)先關(guān)系。這種優(yōu)先關(guān)系可以用有向圖來表示。如用結(jié)點表示語句，若在執(zhí)行完第一個結(jié)點表示的向圖來表示。如用結(jié)點表示語句，若在執(zhí)行完第一個結(jié)點表示的語句之前不能執(zhí)行第二個結(jié)點表示的語句所表示的語句，則在第語句之前不能執(zhí)行第二個結(jié)點表示的語句所表示的語句，則在第一個結(jié)點到第二個結(jié)點之間添加一條邊。最后得到的圖稱為優(yōu)先一個結(jié)點到第二個結(jié)點之間添加一條邊。最后得到的圖稱為優(yōu)先圖。圖。下下圖就是一個優(yōu)先圖的例子。該圖表明在執(zhí)行語句圖就是一個優(yōu)先圖的例子。該圖表明在執(zhí)行語句s s 、s s 與與s s 之前不能執(zhí)行語句之前不能執(zhí)行語句s s 。 10.2 10.2 圖與圖模型

25、圖與圖模型 練習(xí)練習(xí)3 3 在晚會上有在晚會上有n n個人，他們各自與自己相識的人個人，他們各自與自己相識的人握一次手。已知每人與別人握手的次數(shù)都是奇數(shù)，握一次手。已知每人與別人握手的次數(shù)都是奇數(shù)，問問n n是奇數(shù)還是偶數(shù)。為什么？是奇數(shù)還是偶數(shù)。為什么？ 解解 n n是偶數(shù)。用是偶數(shù)。用n n個頂點表示個頂點表示n n個人，頂點間的一條個人，頂點間的一條邊表示一次握手，可構(gòu)成邊表示一次握手，可構(gòu)成 一個無向圖。若一個無向圖。若n n是奇數(shù)，是奇數(shù)，那么該圖的頂點度數(shù)之和為奇數(shù)個奇數(shù)的和那么該圖的頂點度數(shù)之和為奇數(shù)個奇數(shù)的和, ,即為奇即為奇數(shù)，與圖性質(zhì)矛盾，因此，數(shù)，與圖性質(zhì)矛盾，因此，n

26、n是偶數(shù)。是偶數(shù)。10.2 10.2 圖與圖模型圖與圖模型 與集合論中研究子集，抽象代數(shù)中研究與集合論中研究子集，抽象代數(shù)中研究子代數(shù)類似，圖論中也研究一個圖的子圖。子代數(shù)類似，圖論中也研究一個圖的子圖。一個圖一個圖g g的子圖的子圖gg可以通過選取可以通過選取g g中的部分中的部分結(jié)點與邊構(gòu)成，但要求如果選擇了結(jié)點與邊構(gòu)成，但要求如果選擇了g g中的邊，中的邊，則必須選擇與該邊向關(guān)聯(lián)的結(jié)點。這樣就保則必須選擇與該邊向關(guān)聯(lián)的結(jié)點。這樣就保證了證了gg能夠構(gòu)成一個圖。能夠構(gòu)成一個圖。 10.2 10.2 圖與圖模型圖與圖模型 定義定義10.410.4 令圖令圖g=g=（v v，e e），稱），稱

27、(v,e)(v,e)為為g g的子圖的子圖（subgraphsubgraph），當(dāng)），當(dāng) (1)v(1)vv v且且e ee e； (2)(2)對任意對任意e ee e ，則與，則與e e 相關(guān)聯(lián)的結(jié)點相關(guān)聯(lián)的結(jié)點u u ,v,vv v 。 若若g g 是是 g g的子圖的子圖, ,則稱則稱g g是是g g 的的超圖超圖，記作，記作g gg g。若若g gg g且且g g g(g(即即v vv v或或e ee)e)，則稱，則稱g g 是是g g的的真子圖真子圖。若若g gg g且且v v v v，則稱，則稱g g 是是g g的的生成子圖生成子圖（spanning spanning subgra

28、phsubgraph）。設(shè)）。設(shè)v v1 1 v,v,且且v v1 1，以，以v v 為結(jié)點集，以兩為結(jié)點集，以兩端點均在端點均在v v1 1中的全體邊為邊集的中的全體邊為邊集的g g的子圖，稱為的子圖，稱為結(jié)點結(jié)點集集v v1 1導(dǎo)出的導(dǎo)出子圖導(dǎo)出的導(dǎo)出子圖（derived subgraphderived subgraph）。設(shè)）。設(shè)e e1 1 e,e,且且e e1 1，以，以e e 為邊集，以為邊集，以e e1 1中邊關(guān)聯(lián)的結(jié)點的全體中邊關(guān)聯(lián)的結(jié)點的全體為結(jié)點集為結(jié)點集g g的子圖，稱為的子圖，稱為邊集邊集e e1 1導(dǎo)出的導(dǎo)出子圖導(dǎo)出的導(dǎo)出子圖。 10.2 10.2 圖與圖模型圖與圖模

29、型 顯然，子圖或?qū)С鲎訄D可以通過刪除一顯然，子圖或?qū)С鲎訄D可以通過刪除一些結(jié)點或一些邊得到。些結(jié)點或一些邊得到。 例例10.910.9 下下圖所示的圖中，圖所示的圖中，g g 是是g g的由結(jié)點導(dǎo)的由結(jié)點導(dǎo)出的導(dǎo)出子圖，出的導(dǎo)出子圖，g g 為為g g的由邊集導(dǎo)出的導(dǎo)出子的由邊集導(dǎo)出的導(dǎo)出子圖。圖。10.2 10.2 圖與圖模型圖與圖模型 定義定義10.510.5 設(shè)設(shè)g =g =是是n n階圖階圖, ,若若g g中任何結(jié)中任何結(jié)點都與其余的點都與其余的n n 1 1個結(jié)點相鄰，則稱個結(jié)點相鄰，則稱g g為為n n階完階完全圖全圖(complete graph)(complete graph)

30、。記作。記作k kn n。設(shè)。設(shè)d=d=為為n n階有向圖階有向圖, ,若對于任意的結(jié)點若對于任意的結(jié)點,u,v,u,v v v (uv(uv) ,) ,既有有向邊既有有向邊u,v,又有又有v,u ，則稱，則稱d d為為有向完全圖有向完全圖。 容易得到如下重要結(jié)論：容易得到如下重要結(jié)論： k kn n的邊數(shù)的邊數(shù)|e(k|e(kn n)|=n(n-1)/2)|=n(n-1)/2，且對于一般，且對于一般的的n n個結(jié)點的圖個結(jié)點的圖g g其邊數(shù)其邊數(shù)|e(g)|e(g)|n(n-1)/2n(n-1)/2。10.2 10.2 圖與圖模型圖與圖模型 下下圖中圖圖中圖(a)(a)為四個結(jié)點的完全圖，為

31、四個結(jié)點的完全圖，(b)(b)不是完全圖，不是完全圖，(c)(c)是有向完全圖。是有向完全圖。(a)(b)(c)10.2 10.2 圖與圖模型圖與圖模型 定義定義10.610.6 若圖若圖g g的結(jié)點可以分為兩個非空集合的結(jié)點可以分為兩個非空集合v v1 1，v v2 2，g g中的邊的端點分別屬于中的邊的端點分別屬于v v1 1，v v2 2，則稱，則稱g g為為二分圖二分圖（bipartite graphbipartite graph），可簡記為），可簡記為g(vg(v1 1，v v2 2) )。若。若v v1 1中中結(jié)點與結(jié)點與v v2 2中結(jié)點均鄰接且中結(jié)點均鄰接且v v2 2中結(jié)點與

32、中結(jié)點與v v1 1中結(jié)點也均鄰中結(jié)點也均鄰接，則稱接，則稱g g為為完全二分圖完全二分圖（complete bipartite complete bipartite graphgraph），記為），記為k km,nm,n，m,nm,n分別是分別是v v1 1，v v2 2的基數(shù)。的基數(shù)。 二分圖常常被應(yīng)用于工作分配問題中，通過對二分圖常常被應(yīng)用于工作分配問題中，通過對二分圖的分析，找出滿足最多條件的工作分配方案。二分圖的分析，找出滿足最多條件的工作分配方案。完全二分圖完全二分圖k k1 1，n n常常被用來對計算機網(wǎng)絡(luò)建模，度常常被用來對計算機網(wǎng)絡(luò)建模，度為為n n的結(jié)點代表網(wǎng)絡(luò)服務(wù)器，其余

33、結(jié)點代表網(wǎng)絡(luò)中的的結(jié)點代表網(wǎng)絡(luò)服務(wù)器，其余結(jié)點代表網(wǎng)絡(luò)中的n n個計算機。個計算機。10.2 10.2 圖與圖模型圖與圖模型 例例10.1010.10 下圖所示的圖下圖所示的圖(a)(a)是二分圖是二分圖, ,圖（圖（b b）是其的另一種表示。是其的另一種表示。v vv v10.3 10.3 路徑與圖連通性路徑與圖連通性 圖論中的許多概念和應(yīng)用都與對圖的遍圖論中的許多概念和應(yīng)用都與對圖的遍歷有關(guān)，即是從一個結(jié)點歷有關(guān)，即是從一個結(jié)點u u出發(fā)，到達(dá)與之出發(fā)，到達(dá)與之相鄰接的結(jié)點，在從該鄰接結(jié)點出發(fā)到達(dá)其相鄰接的結(jié)點，在從該鄰接結(jié)點出發(fā)到達(dá)其鄰接的結(jié)點，依次類推，最后可以到達(dá)圖中鄰接的結(jié)點，依次

34、類推，最后可以到達(dá)圖中的某結(jié)點的某結(jié)點v v，從而就得到一條從，從而就得到一條從u u到到v v的通路。的通路。從從u u到到v v的通路的通路w w可用如下的結(jié)點的序列來表可用如下的結(jié)點的序列來表示：示： w: u=v w: u=v0 0,v,v1 1,v,v2 2, ,v,vk k=v=v，k k 0 0。 通路通路w w常表示為常表示為u-vu-v通路。這些結(jié)點序列通路。這些結(jié)點序列中任意相鄰的結(jié)點在圖中是鄰接的關(guān)系，稱中任意相鄰的結(jié)點在圖中是鄰接的關(guān)系，稱結(jié)點結(jié)點v vi i（i=0i=0，1,1,k,k）以及邊）以及邊(v(vi i,v,vi+1i+1) ) (i=0,1,(i=0,

35、1,k-1),k-1)為通路為通路w w上的上的結(jié)點結(jié)點與與邊邊。10.3 10.3 路徑與圖連通性路徑與圖連通性 如果通路上首尾結(jié)點相同，則稱該通路如果通路上首尾結(jié)點相同，則稱該通路是是閉的閉的(closed)(closed)，否則稱該通路是，否則稱該通路是開的開的(opened)(opened)。如果通路上沒有相同的邊，則稱。如果通路上沒有相同的邊，則稱該通路為該通路為跡跡(trail)(trail)，如果跡上的開始結(jié)點與，如果跡上的開始結(jié)點與結(jié)束結(jié)點相同，則稱之為結(jié)束結(jié)點相同，則稱之為回路回路(circuit)(circuit)，如，如果回路上除了開始結(jié)點與結(jié)束結(jié)點沒有相同果回路上除了開

36、始結(jié)點與結(jié)束結(jié)點沒有相同的結(jié)點，則稱之為的結(jié)點，則稱之為環(huán)環(huán)(cycle)(cycle)。如果通路上沒。如果通路上沒有相同的結(jié)點，則稱該通路為有相同的結(jié)點，則稱該通路為路路或或路徑路徑(path)(path)，有，有n n個結(jié)點的路常記作個結(jié)點的路常記作p pn n。 10.3 10.3 路徑與圖連通性路徑與圖連通性 通路遍歷過的邊的數(shù)目為通路的長度，如果通通路遍歷過的邊的數(shù)目為通路的長度，如果通路長度為路長度為0 0，則稱之為，則稱之為平凡通路平凡通路（trivial walktrivial walk）。）。兩結(jié)點兩結(jié)點u u，v v間的路可能不只一條，將其中的最短的間的路可能不只一條，將其

37、中的最短的路稱為路稱為u u，v v間的間的距離距離。 如果一條通路如果一條通路w w上有上有k+1k+1個結(jié)點，即個結(jié)點，即w: w: u=vu=v0 0,v,v1 1,v,v2 2, ,v,vk k=v=v，kk0 0。則由于。則由于w w上的邊是由上的邊是由w w上上相鄰結(jié)點相鄰結(jié)點(v(vi i,v,vi+1i+1) (i=0,1,) (i=0,1,k-1),k-1)構(gòu)成，因此構(gòu)成，因此w w上上有有k k條邊，即條邊，即w w的長度為的長度為k k。如果一條環(huán)。如果一條環(huán)c c上有上有k+1k+1個結(jié)個結(jié)點，即點，即c: vc: v0 0,v,v1 1,v,v2 2, ,v,vk k

38、v v0 0，kk0.0.則由于則由于c c上的邊是上的邊是由由c c上相鄰結(jié)點上相鄰結(jié)點(v(vi i,v,vi+1i+1)(i=0,1,)(i=0,1,k-1),k-1)以及（以及（v vk k,v,v0 0）構(gòu)成，因此構(gòu)成，因此c c上有上有k+1k+1條邊，即條邊，即c c的長度為的長度為k+1k+1。10.3 10.3 路徑與圖連通性路徑與圖連通性 定理定理10.210.2 如果圖如果圖g g上存在一條上存在一條u-vu-v通路，則通路，則必然存在一條必然存在一條u-vu-v路；如果路；如果g g上存在一條閉通上存在一條閉通路，則必然存在一條回路路，則必然存在一條回路( (環(huán)環(huán)) )

39、。 這是因為，如果通路上存在相同的結(jié)點這是因為，如果通路上存在相同的結(jié)點v vi i,v,vj j，則可將則可將v vi i,v,vj j之間的一段通路刪除，并合并之間的一段通路刪除，并合并v vi i，v vj j為為一個結(jié)點，從而得到一條更短的一個結(jié)點，從而得到一條更短的u-vu-v通路。如果所得通路。如果所得到的到的u-vu-v通路上還存在相同的結(jié)點，則可以依此繼續(xù)通路上還存在相同的結(jié)點，則可以依此繼續(xù)執(zhí)行刪除操作，最終一定可以得到一條沒有相同結(jié)執(zhí)行刪除操作，最終一定可以得到一條沒有相同結(jié)點的點的u-vu-v通路，也就是一條通路，也就是一條u-vu-v路。類似地，如果路。類似地，如果g

40、g上上存在一條閉通路，則必然存在一條回路（環(huán)）。存在一條閉通路，則必然存在一條回路（環(huán)）。 10.3 10.3 路徑與圖連通性路徑與圖連通性例例10.1110.11 在右圖中，在右圖中，1) 1) 找出一條包含圖所有結(jié)點的通道；找出一條包含圖所有結(jié)點的通道；2) 2) 找出一條包含圖所有結(jié)點的跡；找出一條包含圖所有結(jié)點的跡； 3) 3) 找出所有找出所有a-da-d路，并求出其長度；路，并求出其長度；4) 4) 找出圖中所有的環(huán)。找出圖中所有的環(huán)。解解 1) 1) 包含圖所有結(jié)點的不是跡的通道：包含圖所有結(jié)點的不是跡的通道：aebcaebdaebcaebd。2) 2) 包含所有結(jié)點的跡：包含所

41、有結(jié)點的跡：beacbdbeacbd。3) a-d3) a-d路：路：aebd,acbdaebd,acbd, ,長度均為長度均為3 3。4) 4) 環(huán)：環(huán)：acbeaacbea，長度為，長度為4 4。10.3 10.3 路徑與圖連通性路徑與圖連通性 例例10.1210.12 每個結(jié)點的度數(shù)至少為每個結(jié)點的度數(shù)至少為2 2的圖必包含一個回的圖必包含一個回路。路。 證明證明 設(shè)設(shè)p p是圖是圖g g中最長路經(jīng)中的一條，并設(shè)其長度為中最長路經(jīng)中的一條，并設(shè)其長度為m, pm, p的一個端點為的一個端點為u u。考察?？疾靏 g中與中與u u關(guān)聯(lián)的邊，由于關(guān)聯(lián)的邊，由于g g中每個結(jié)點的度至少為中每個

42、結(jié)點的度至少為2 2，故，故u u必關(guān)聯(lián)一條不在必關(guān)聯(lián)一條不在p p上的上的邊邊e e，從而，從而e e的另一個端點的另一個端點v v必然在必然在p p上，否則，將這上，否則，將這個結(jié)點加入個結(jié)點加入p p上，則可以得到更長的路。于是，上，則可以得到更長的路。于是，p p上上u u到到v v的的路與邊的的路與邊e e構(gòu)成回路。構(gòu)成回路。 10.3 10.3 路徑與圖連通性路徑與圖連通性dijkstradijkstra最短路徑算法最短路徑算法輸入：一個帶權(quán)圖輸入：一個帶權(quán)圖g g，g g的任意兩個結(jié)點間有路徑存在，的任意兩個結(jié)點間有路徑存在，g g中任意邊中任意邊(v,x(v,x) )的權(quán)值的權(quán)

43、值w(v,xw(v,x)0)0；結(jié)點；結(jié)點a a與與z z輸出：輸出：l(zl(z) )，從結(jié)點，從結(jié)點a a到到z z的最短路徑長度的最短路徑長度1 procedure dijkstra(g1 procedure dijkstra(g) )2 2 for for 所有結(jié)點所有結(jié)點xaxa 3 3 l(x)=; l(xl(x)=; l(x) )表示表示a a到到x x的最短路徑長度的最短路徑長度4 4 end for;end for;5 5 l(al(a)=0;)=0;6 t=v(g);6 t=v(g);7 7 s=s=; ; 10.3 10.3 路徑與圖連通性路徑與圖連通性8 while(z

44、t8 while(zt) )9 9 從從t t中找出具有最小中找出具有最小l(vl(v) )的結(jié)點的結(jié)點v;v;10 10 for for 所有與所有與v v相鄰的結(jié)點相鄰的結(jié)點xtxt11 11 l(x)=minl(x),l(v)+w(v,xl(x)=minl(x),l(v)+w(v,x)1212end forend for13 13 t=t-v;t=t-v;1414s=svs=sv;15 15 end whileend while16 end procedure16 end procedure 10.3 10.3 路徑與圖連通性路徑與圖連通性 例例10.1310.13 下圖所示的帶權(quán)圖中，

45、根據(jù)上述算下圖所示的帶權(quán)圖中，根據(jù)上述算法可以得到結(jié)點法可以得到結(jié)點a a到到z z的最短路徑為圖中加粗的最短路徑為圖中加粗的邊所示，長度為的邊所示，長度為1313。 4 5 64 5 6 1 8 2 1 8 2 a z a z 2 10 3 2 10 310.3 10.3 路徑與圖連通性路徑與圖連通性 定義定義10.510.5 如果圖如果圖g g中結(jié)點中結(jié)點u u到到v v有一條路徑，則稱結(jié)有一條路徑，則稱結(jié)點點 u u 到到 v v 是是 可 達(dá) 的可 達(dá) 的 （ a c c e s i b l ea c c e s i b l e ） 或） 或 連 通 的連 通 的（connectedc

46、onnected）。結(jié)點）。結(jié)點u u到其自身也定義為連通的。到其自身也定義為連通的。 定義定義10.610.6 如果圖如果圖g g的任何兩個結(jié)點都是相互可達(dá)的，的任何兩個結(jié)點都是相互可達(dá)的，稱稱g g是是連通的連通的（connectedconnected）, ,并稱并稱g g為為連通圖連通圖(connected graph)(connected graph)。對于有向圖。對于有向圖g g，如果，如果g g的任何兩的任何兩個結(jié)點都是相互可達(dá)的，則稱有向圖個結(jié)點都是相互可達(dá)的，則稱有向圖g g是是強連通強連通的；的；如果如果g g的任何兩個結(jié)點中，至少從一個結(jié)點到另一個的任何兩個結(jié)點中，至少從一

47、個結(jié)點到另一個結(jié)點是可達(dá)的，稱有向圖結(jié)點是可達(dá)的，稱有向圖g g是是單向連通單向連通的；如果的；如果g g的的有向邊被看作無向邊時是連通的，稱有向圖有向邊被看作無向邊時是連通的，稱有向圖g g是是弱連弱連通通的。的。 10.3 10.3 路徑與圖連通性路徑與圖連通性 容易判斷，強連通圖必定是單向連通圖，容易判斷，強連通圖必定是單向連通圖，單向連通圖必定是弱連通圖。單向連通圖必定是弱連通圖。 例例10.1410.14 下圖中，下圖中，(a)(a)為連通圖，為連通圖，(b)(b)為由兩為由兩個連通分支的非連通圖，個連通分支的非連通圖，c c為強連通圖，為強連通圖，d d為為單向連通圖，單向連通圖，

48、e e為弱連通圖。為弱連通圖。 a b c d ea b c d e10.3 10.3 路徑與圖連通性路徑與圖連通性 練習(xí)練習(xí)4 4 已知關(guān)于已知關(guān)于a,b,c,d,e,f,ga,b,c,d,e,f,g的下述事實：的下述事實： a a說英語；說英語； b b說英語和西班牙語；說英語和西班牙語； c c說英語、意大利語和俄語；說英語、意大利語和俄語； d d說日語和西班牙語；說日語和西班牙語； e e說德語和意大利語；說德語和意大利語； f f說法語、日語和俄語；說法語、日語和俄語； g g說法語和德語；說法語和德語； 試問：上述試問：上述7 7人中是否任意兩人都能交談（如果必要，人中是否任意兩

49、人都能交談（如果必要，可由其余可由其余5 5人中所組成的譯員鏈幫忙？）人中所組成的譯員鏈幫忙？）10.3 10.3 路徑與圖連通性路徑與圖連通性 若將圖中兩個結(jié)點間的連通性看作圖的若將圖中兩個結(jié)點間的連通性看作圖的結(jié)點間的一種關(guān)系，容易判定圖中兩個結(jié)點結(jié)點間的一種關(guān)系，容易判定圖中兩個結(jié)點間的連通性是一個間的連通性是一個等價關(guān)系等價關(guān)系，因為結(jié)點，因為結(jié)點u u到到u u是連通的滿足自反性；若是連通的滿足自反性；若u u到到v v是連通的，則是連通的，則v v到到u u也是連通的，滿足對稱性；若也是連通的，滿足對稱性；若u u到到v v連通，連通，v v到到w w連通，則連通，則u u到到w

50、w存在一條通路，從而存在存在一條通路，從而存在一條一條u u到到w w的路徑，故的路徑，故u u到到w w是連通的，滿足傳是連通的，滿足傳遞性。但對于有向圖，結(jié)點間的連通性不滿遞性。但對于有向圖，結(jié)點間的連通性不滿足對稱性，是足對稱性，是偏序關(guān)系偏序關(guān)系。 10.3 10.3 路徑與圖連通性路徑與圖連通性 現(xiàn)在可以利用結(jié)點的連通性對圖現(xiàn)在可以利用結(jié)點的連通性對圖g g的結(jié)點集進(jìn)行的結(jié)點集進(jìn)行劃分，于是利用這個劃分可以得到劃分，于是利用這個劃分可以得到g g的多個連通子圖，的多個連通子圖，如如 gv=(vv,evgv=(vv,ev),), 是結(jié)點是結(jié)點v v所在的一個連通子圖，其中，所在的一個連

51、通子圖，其中，vv=x|xvv=x|x到到v v可達(dá)可達(dá) ，evev 為為vvvv 中結(jié)點在中結(jié)點在g g中相應(yīng)的邊之集合。中相應(yīng)的邊之集合。 gvgv 具有一個特點，即不存在一個具有一個特點，即不存在一個g g的真子圖的真子圖g, gvg, gv 為為gg的真子圖的真子圖, ,且且gg也是也是g g的連通子圖。的連通子圖。稱稱gvgv 為為g g的的連通分支連通分支或或連通分圖連通分圖（connected connected componentcomponent）, ,也稱為也稱為極大連通子圖極大連通子圖。 10.3 10.3 路徑與圖連通性路徑與圖連通性 例例10.1510.15 如果圖如

52、果圖g g恰有兩個不同的奇數(shù)度的恰有兩個不同的奇數(shù)度的結(jié)點結(jié)點u u，v v，那么，那么u u到到v v必定是可達(dá)的。必定是可達(dá)的。 證明證明 如果如果u u到到v v不可達(dá)，那么不可達(dá)，那么g g不是連通的，不是連通的，u u與與v v必分屬于兩個連通分支必分屬于兩個連通分支g g1 1，g g2 2，而，而g g1 1，g g2 2是是g g的子圖，且都恰有一個奇數(shù)度結(jié)點。與的子圖，且都恰有一個奇數(shù)度結(jié)點。與推論推論10.110.1矛盾。因而矛盾。因而u u到到v v是可達(dá)的。是可達(dá)的。 10.3 10.3 路徑與圖連通性路徑與圖連通性 定理定理10.310.3 設(shè)設(shè)g是一是一(n，m)圖

53、，圖，g有有個分圖，個分圖，則則 n-m(n-)(n-+1)/210.3 10.3 路徑與圖連通性路徑與圖連通性 練習(xí)練習(xí)5 5 在任何在任何n (n2)n (n2)個頂點的簡單圖個頂點的簡單圖g g中，至少有中，至少有兩個頂點具有相同的度。兩個頂點具有相同的度。 證明證明 如果如果g g有兩個或更多孤立頂點，那么它們便是有兩個或更多孤立頂點，那么它們便是具有相同的度的兩個頂點。具有相同的度的兩個頂點。 如果如果g g恰有一個孤立頂點，那么我們可對有恰有一個孤立頂點，那么我們可對有n1 n1 個頂點但沒有孤立頂點的個頂點但沒有孤立頂點的gg（它由（它由g g刪除孤立頂點刪除孤立頂點后得到）作討

54、論；如果后得到）作討論；如果g g有分圖，則也可以直接對分有分圖，則也可以直接對分圖進(jìn)行討論。因此，不妨設(shè)圖進(jìn)行討論。因此，不妨設(shè)g g沒有孤立頂點，那么沒有孤立頂點，那么g g 的的n n個頂點的度數(shù)應(yīng)是：個頂點的度數(shù)應(yīng)是：1 1，2 2，3 3，n1 n1 這這n1n1種可能之一，顯然，必定有兩個頂點具有相同的度。種可能之一，顯然，必定有兩個頂點具有相同的度。10.3 10.3 路徑與圖連通性路徑與圖連通性 練習(xí)練習(xí)6 6 給定簡單圖給定簡單圖g=g=，且，且|v|=n|v|=n，|e|e|(n-1)(n-2)/2(n-1)(n-2)/2，試證，試證g g是連通圖。試給出是連通圖。試給出|

55、v|=n|v|=n，|e|=(n-1)(n-2)/2|e|=(n-1)(n-2)/2的簡單無向圖的簡單無向圖g=g=是不連通的例子。是不連通的例子。 10.3 10.3 路徑與圖連通性路徑與圖連通性 定義定義10.910.9 設(shè)設(shè)s s為圖為圖g g的結(jié)點集的結(jié)點集v v的子集，稱的子集，稱s s為為g g的的點點割集割集（cut set of vertexcut set of vertex）, ,如果從如果從g g中刪除中刪除s s中的中的所有結(jié)點后所有結(jié)點后g g的連通分支數(shù)增加，但的連通分支數(shù)增加，但s s的任何真子集的任何真子集均無這一特性。當(dāng)點割集為單元素集合均無這一特性。當(dāng)點割集為

56、單元素集合vv時，時，v v稱稱為為割點割點（cut vertexcut vertex）。）。 設(shè)設(shè)s s為連通圖為連通圖g g邊集邊集e e的子集，稱的子集，稱s s為為g g的的邊割集邊割集（cut set of edgecut set of edge），如果從），如果從g g中刪除中刪除s s的所有邊后的所有邊后g g的連通分支數(shù)增加，但的連通分支數(shù)增加，但s s的任何真子集均無這一特的任何真子集均無這一特性。當(dāng)割集為單元素集性。當(dāng)割集為單元素集ee時，稱時，稱e e為為橋橋(bridge)(bridge)或或割邊割邊（cut edgecut edge）。）。 10.3 10.3 路徑與

57、圖連通性路徑與圖連通性 例例10.1710.17 下下圖中的圖有點割集圖中的圖有點割集11，55，2 2，3 3是割點，而是割點，而44，77不是點割集。不是點割集。ee1 1,e,e3 3,e,e4 4,e,e5 5,e,e6 6,e,e8 8 等均是邊割集，等均是邊割集，e e9 9是是割邊。割邊。10.3 10.3 路徑與圖連通性路徑與圖連通性 例例10.1810.18 試證明：圖試證明：圖g g的任一邊，若其不是的任一邊，若其不是割邊，則必出現(xiàn)于割邊，則必出現(xiàn)于g g的某一環(huán)里。的某一環(huán)里。 證明證明 設(shè)圖設(shè)圖g g的邊的邊e=(ve=(vi i，v vj j) )不是分割邊，去掉不是

58、分割邊，去掉e e后，與后，與v vi i相連接的接點集為相連接的接點集為v v1 1，與，與v vj j相連接相連接的結(jié)點集為的結(jié)點集為v v2 2，由割邊定義知，由割邊定義知，v v1 1vv2 2。因而存在一結(jié)點因而存在一結(jié)點vvvv1 1vv2 2，使得在去掉，使得在去掉e e后，后，v vi i與與v v有路相連，有路相連，v v與與v vj j有路相連。于是有路相連。于是v vi i與與v vj j有路相連接，因而必存在一條連接有路相連接，因而必存在一條連接v vi i與與v vj j的路的路p=vp=vi i，v v1 1，v v2 2，v v，v vj j，從而，從而p p與邊

59、與邊(v(vi i，v vj j) )組成一個環(huán)。組成一個環(huán)。 10.3 10.3 路徑與圖連通性路徑與圖連通性 定義定義10.1010.10 圖圖g g的的點連通度點連通度（vertex vertex connectivityconnectivity）是指把）是指把g g變成非連通圖或平變成非連通圖或平凡圖至少要刪除的結(jié)點數(shù)，記作凡圖至少要刪除的結(jié)點數(shù)，記作 (g) (g) ( 讀讀作卡帕作卡帕) )。定義中的平凡圖主要針對。定義中的平凡圖主要針對g g為完全為完全圖時而言的，因為完全圖無論刪除多少結(jié)點圖時而言的，因為完全圖無論刪除多少結(jié)點都不會變得不連通。根據(jù)定義，都不會變得不連通。根據(jù)定

60、義， (g)(g)可以具可以具體定義如下：體定義如下： (g)=(g)= n0g1gkmin|:gnss1為非連通圖或k為完全圖為點割集為連通圖，但非完全圖10.3 10.3 路徑與圖連通性路徑與圖連通性 類似地，有邊連通度的定義。類似地，有邊連通度的定義。g g的的邊連邊連通度通度（edge connectivityedge connectivity）是指把）是指把g g變成非變成非連通圖或平凡圖至少要刪除的邊數(shù)，記作連通圖或平凡圖至少要刪除的邊數(shù)，記作(g(g) )。根據(jù)定義，當(dāng)。根據(jù)定義，當(dāng)g g為非連通圖或為為非連通圖或為k k1時時(g(g)=0)=0。 例例10.1710.17中圖