第6章圖論課件

轉(zhuǎn)化

Euler1736年

圖論中討論的圖

問題：是否能從四塊陸地中的任一塊開始，通過每座橋恰好一次再回到起點(diǎn)？是否能從任意一個頂點(diǎn)開始，通過每條邊恰好一次再回到起點(diǎn)？包含兩個要素：對象（陸地）及對象間的二元關(guān)系（是否有橋連接）問題一:哥尼斯堡七橋問題轉(zhuǎn)化Euler圖論中討論的圖問題：是否能從四塊陸地中的任LeonhardEuler(公元1707-1783年)1707年出生在瑞士的巴塞爾城，13歲就進(jìn)巴塞爾大學(xué)讀書，師從著名的數(shù)學(xué)家約翰.伯努利。他從19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。1733年，年僅26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長，直到1766年，重回彼得堡，沒有多久，完全失明．歐拉在數(shù)學(xué)上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。LeonhardEuler1707年出生在瑞士的巴塞爾城，問題二：四色問題四色問題是世界近代三大數(shù)學(xué)難題之一。

四色問題的內(nèi)容是：任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。它的提出來自英國。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯·格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色?！边@個現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？問題二：四色問題四色問題是世界近代三大數(shù)學(xué)難題之一

進(jìn)入20世紀(jì)以來，科學(xué)家們對四色猜想的證明基本上是按照肯普的想法在進(jìn)行。后來美國數(shù)學(xué)家富蘭克林于1939年證明了22國以下的地圖都可以用四色著色。1950年，有人從22國推進(jìn)到35國。1960年，有人又證明了39國以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了50國。1976年6月，美國伊利諾大學(xué)哈肯與阿佩爾在兩臺不同的電子計算機(jī)上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明，轟動了世界。然而，真正數(shù)學(xué)上的嚴(yán)格證明仍然沒有得到！數(shù)學(xué)家仍為此努力，并由此產(chǎn)生了多個不同的圖論分支。問題二：四色問題進(jìn)入20世紀(jì)以來，科學(xué)家們對四色猜想的證明基問題三：Hamilton問題

Hamilton問題源于1856年，英國數(shù)學(xué)家Hamilton設(shè)計了一個名為周游世界的游戲：他用一個正十二面體的二十個端點(diǎn)表示世界上的二十座大城市（見圖），提出的問題是要求游戲者找一條沿著十二面體的棱通過每個端點(diǎn)恰好一次的行走路線。反映到圖論上就是判斷一個給定的圖是否存在一條含所有頂點(diǎn)的回路。Hamilton至今尚無有效方法來解決！問題三：Hamilton問題Hamilton問題四:校園網(wǎng)絡(luò)問題四:校園網(wǎng)絡(luò)一直往前走碰壁就回頭換條路找沿途要記錄下走過的路線問題五:游戲一直往前走問題五:游戲程序調(diào)用的圖論模型程序調(diào)用的圖論模型設(shè)備更新問題。某工廠的某臺機(jī)器可連續(xù)工作4年，決策者每年年初都要決定機(jī)器是否需要更新。若購置新的，就要支付一定的購置費(fèi)用；若繼續(xù)使用，則要支付一定的維修與運(yùn)行費(fèi)用，而且隨著機(jī)器使用年限的增加費(fèi)用逐年增多。計劃期（4年）中每年年初的購置價格及各個年限內(nèi)維修與運(yùn)行費(fèi)用由下表給出，試制訂今后4年的機(jī)器更新計劃，使總的支付費(fèi)用最少。設(shè)備更新問題。某工廠的某臺機(jī)器可連續(xù)工作4年，決策者每年年初解：把該問題看成一個最短路問題。設(shè)v1和v5分別表示計劃期的始點(diǎn)和終點(diǎn)（x5可理解為第4年年末）。圖中各邊(vi

,vj)表示在第i年初購進(jìn)的機(jī)器使用到第j年初（即第j

1年底），邊旁的數(shù)字由表中的數(shù)據(jù)得到。解：把該問題看成一個最短路問題。設(shè)v1和v5分別表示又如果已知不同役齡機(jī)器年末的處理價格如下表所示，那末在這計劃期內(nèi)機(jī)器的最優(yōu)更新計劃又會怎樣？又如果已知不同役齡機(jī)器年末的處理價格如下表所

關(guān)于第二問，類似于第一問，可轉(zhuǎn)化為求下圖中從v1到v5的最短路問題。按照最短路算法可得最短路{v1,v2,v3,v5}，即計劃期內(nèi)機(jī)器更新最優(yōu)計劃為第1年、第3年初各購進(jìn)一臺新機(jī)器，4年總的支付費(fèi)用為6.8萬元。關(guān)于第二問，類似于第一問，可轉(zhuǎn)化為求下圖中從1.圖的定義圖G(graph)主要由2部分組成:(1)節(jié)點(diǎn)集合V,其中的元素稱為節(jié)點(diǎn).(2)邊集合E,其中的元素稱為邊.通常將圖G記為G=(V,E).1.圖的定義圖G(graph)主要由2部分組成:(a)節(jié)點(diǎn)又可以稱為點(diǎn)、頂點(diǎn)或結(jié)點(diǎn),常用一個實(shí)心點(diǎn)或空心點(diǎn)表示,但在實(shí)際應(yīng)用中還可以用諸如方形、圓形、菱形等符號.(b)邊及其的表示.無向邊?b3=AB=BA={A,B}(可重).有向邊(弧)?幾點(diǎn)說明:所有邊都是無向邊的圖稱為無向圖；所有邊都是有向邊的圖稱為有向圖.(a)節(jié)點(diǎn)又可以稱為點(diǎn)、頂點(diǎn)或結(jié)點(diǎn),常用一個實(shí)心點(diǎn)或空心點(diǎn)表(c)圖的拓?fù)洳蛔冃再|(zhì).需要注意的是,我們討論的圖不但與節(jié)點(diǎn)位置無關(guān),而且與邊的形狀和長短也無關(guān).有n個節(jié)點(diǎn)的圖稱為n階圖,有n個節(jié)點(diǎn)m條邊的圖稱為(n,m)圖.在圖G=(V,E)中,稱V=

的圖為空圖,記為

.幾點(diǎn)說明:(c)圖的拓?fù)洳蛔冃再|(zhì).需要注意的是,我們討論的圖不但與節(jié)若V

但E=

的圖稱為零圖,n階零圖可記為Nn.僅一個節(jié)點(diǎn)的零圖稱為平凡圖.若V但E=的圖稱為零圖,n階零圖可記為Nn定義：設(shè)G=(V,E)是圖,對于任意u,v

V,若從節(jié)點(diǎn)u到節(jié)點(diǎn)v有邊,則稱u鄰接到v或稱u和v是鄰接的.2.鄰接無向圖?有向圖?定義：設(shè)G=(V,E)是圖,對于任意u,vV(無向圖的兩條邊鄰接是指它們有公共端點(diǎn).)(平面圖的面相鄰?)(無向圖的兩條邊鄰接是指它們有公共端點(diǎn).)(平面圖的面相鄰?3.關(guān)聯(lián)定義：設(shè)G=(V,E)是圖,e

E,e的兩個端點(diǎn)分別為u和v,則稱邊e與節(jié)點(diǎn)u以及邊e與節(jié)點(diǎn)v是關(guān)聯(lián)的.圖的任意一條邊都關(guān)聯(lián)兩個節(jié)點(diǎn).關(guān)聯(lián)相同兩個節(jié)點(diǎn)的邊稱為吊環(huán),可簡稱環(huán).關(guān)聯(lián)的起點(diǎn)相同與終點(diǎn)也相同的邊稱為多重邊或平行邊,其邊數(shù)稱為邊的重數(shù).3.關(guān)聯(lián)定義：設(shè)G=(V,E)是圖,eE,4.簡單圖(1)簡單圖定義：設(shè)G=(V,E)是圖,若G中既無吊環(huán)又無多重邊,則稱G是簡單圖.彼得森(Petersen,1831~1910)圖,是一種妖怪圖.4.簡單圖(1)簡單圖彼得森(Petersen,1831~第6章圖論課件妖怪圖?Petersen圖稱為單星妖怪.下面的圖稱為雙星妖怪.妖怪圖?(2)完全無向圖Def設(shè)G=(V,E)是n階簡單無向圖,若G中任意節(jié)點(diǎn)都與其余n-1個節(jié)點(diǎn)鄰接,則稱G為n階完全無向圖，記為Kn.K5:

(2)完全無向圖將n階完全無向圖Kn的邊任意加一個方向所得到的有向圖稱為n階競賽圖.設(shè)G=(V,E)是n階簡單有向圖,若G中任意節(jié)點(diǎn)都與其余n-1個節(jié)點(diǎn)鄰接,則稱G為n階完全有向圖。將n階完全無向圖Kn的邊任意加一個方向所得到的有向圖稱為n階(3)補(bǔ)圖Def設(shè)G=(V,E)是n階簡單無向圖,由G的所有節(jié)點(diǎn)以及由能使G成為Kn需要添加的邊構(gòu)成的圖稱為G的補(bǔ)圖,記為(u和v在G中不鄰接

u和v在中鄰接)(3)補(bǔ)圖6.2節(jié)點(diǎn)的度數(shù)“七橋”中從一個地方出發(fā)的橋的數(shù)目就是對應(yīng)節(jié)點(diǎn)的度數(shù).邊與節(jié)點(diǎn)的關(guān)聯(lián)次數(shù)?6.2節(jié)點(diǎn)的度數(shù)“七橋”中從一個地方出發(fā)的橋的數(shù)目就是對應(yīng)Def設(shè)G=(V,E)是無向圖,v

V,稱與節(jié)點(diǎn)v關(guān)聯(lián)的所有邊的關(guān)聯(lián)次數(shù)之和為節(jié)點(diǎn)v的度數(shù)(degree),記為deg(v).一個環(huán)算2度?Def設(shè)G=(V,E)是無向圖,vV,稱Def設(shè)G=(V,E)是有向圖,v

V,稱以v為起點(diǎn)的邊的數(shù)目為節(jié)點(diǎn)的出度(out-degree),記為deg+(v),以v為終點(diǎn)的邊的數(shù)目為節(jié)點(diǎn)的入度(in-degree),記為deg-(v),稱deg+(v)+deg-(v)為節(jié)點(diǎn)v的度數(shù),記為deg

(v).一個環(huán)算2度?Def設(shè)G=(V,E)是有向圖,vV,稱以圖論第一定理,常稱為“握手(?)定理”.Theorem6-1在任何(n,m)圖G=(V,E)中,其所有節(jié)點(diǎn)度數(shù)之和等于邊數(shù)m的2倍,即Corollary

在任意圖G=(V,E)中,度數(shù)為奇數(shù)的節(jié)點(diǎn)個數(shù)必為偶數(shù).Proof圖論第一定理,常稱為“握手(?)定理”.由定理及其推論很容易知道,在任何一次聚會上,所有人握手次數(shù)之和必為偶數(shù)并且握了奇數(shù)次手的人數(shù)必為偶數(shù).(環(huán)的解釋?)Theorem6-2在任意有向圖中,所有節(jié)點(diǎn)的出度之和等于入度之和.在任意圖中,度數(shù)為0的節(jié)點(diǎn)稱為孤立點(diǎn)。度數(shù)為1的節(jié)點(diǎn)稱為懸掛點(diǎn)。由定理及其推論很容易知道,在任何一次聚會上,所有人握手次數(shù)之例6-1證明:對于任意n(n

2)個人的組里,必有兩個人有相同個數(shù)的朋友.Proof將組里的每個人看作節(jié)點(diǎn),兩個人是朋友當(dāng)且僅當(dāng)對應(yīng)的節(jié)點(diǎn)鄰接,于是得到一個n階簡單無向圖G,進(jìn)而G中每節(jié)點(diǎn)的度數(shù)可能為0,1,2,…,n-1中一個.例6-1證明:對于任意n(n2)個人的組里,必有兩當(dāng)G中無孤立點(diǎn)時,于是每節(jié)點(diǎn)的度數(shù)可能為1,2,…,n-1.由于共有n個節(jié)點(diǎn),于是必有兩節(jié)點(diǎn)度數(shù)相同.當(dāng)G中有孤立點(diǎn)時,這時每節(jié)點(diǎn)的度數(shù)只可能為0,1,2,…,n-2.同樣由于共n有個節(jié)點(diǎn),因此必有兩節(jié)點(diǎn)度數(shù)相同.當(dāng)G中無孤立點(diǎn)時,于是每節(jié)點(diǎn)的度數(shù)可能為1,2,…,n若一個Simple無向圖G的每節(jié)點(diǎn)度數(shù)均為k,則稱G為k-正則圖(k-regulargraph).例6-2設(shè)無向圖G是一個3-正則(n,m)圖,且2n–3=m,求n和m各是多少?

Hint根據(jù)握手定理有:若一個Simple無向圖G的每節(jié)點(diǎn)度數(shù)均為k,則稱G為k-Def最大度、最小度；最小出度、最小入度任意圖G=(V,E):有向圖G=(V,E):Def最大度、最小度；最小出度、最小入度對于無向圖G=(V,E),V={v1,v2,…,vn},稱deg(v1),deg(v2),…,deg(vn)為的度數(shù)序列.對于有向圖,還可以定義其出度序列和入度序列.例6-3是否存在一個無向圖G,其度數(shù)序列分別為(1)7,5,4,2,2,1.(2)4,4,3,3,2,2.(1)由于序列7,5,4,2,2,1中,奇數(shù)個數(shù)為奇數(shù),根據(jù)握手定理的推論知,不可能存在一個圖其度數(shù)序列為7,5,4,2,2,1.(2)因?yàn)樾蛄?,4,3,3,2,2中,奇數(shù)個數(shù)為偶數(shù),可以得到一個無向圖,其度數(shù)序列為4,4,3,3,2,2.對于無向圖G=(V,E),V={v1,v2,6.3子圖、圖的運(yùn)算和圖同構(gòu)1.子圖可以通過一個圖的子圖去考察原圖的有關(guān)性質(zhì)以及原圖的局部結(jié)構(gòu).Def設(shè)G=(V,E)和H=(W,F)是圖,若W

V且F

E,則稱H=(W,F)是G=(V,E)的子圖.若H=(W,F)是G=(V,E)的子圖且W

=V,則稱H=(W,F)是G=(V,E)的生成子圖.6.3子圖、圖的運(yùn)算和圖同構(gòu)1.子圖例子圖子圖例子圖子圖第6章圖論課件第6章圖論課件常見的4種產(chǎn)生G=(V,E)的子圖的方式如下:(1)G[W]設(shè)W

V,則以W為節(jié)點(diǎn)集合,以兩端點(diǎn)均屬于W的所有邊為邊集合構(gòu)成的子圖,稱為由W導(dǎo)出的子圖(inducedsubgraphbyW),記為G[W].常見的4種產(chǎn)生G=(V,E)的子圖的方式如下:(2)G–W設(shè)W

V,導(dǎo)出子圖G[V–W]記為G–W,是在G中去掉所有W中的節(jié)點(diǎn),同時也要去掉與W中節(jié)點(diǎn)關(guān)聯(lián)的所有邊.通常將G–{v}記為G-v.(3)G[F]設(shè)F

E,則以F為邊集合,以F中邊的所有端點(diǎn)為節(jié)點(diǎn)集合構(gòu)成的子圖,稱為由F導(dǎo)出的子圖(inducedsubgraphbyF),記為G[F].(2)G–W設(shè)WV,導(dǎo)出子圖G[V–(4)G–F

設(shè)F

E,則從G中去掉F中的所有邊得到的生成子圖記為G–F.第6章圖論課件簡單圖G=(V,E)的補(bǔ)圖G+U:(與子圖無關(guān))簡單圖G=(V,E)的補(bǔ)圖2.*圖的運(yùn)算圖的運(yùn)算就是通過一定的操作,產(chǎn)生“新”的圖.前面的子圖的產(chǎn)生實(shí)際上就是圖的運(yùn)算,但它們都是在一個圖中進(jìn)行討論的.也便于用代數(shù)方法討論圖.Def(1)2.*圖的運(yùn)算(2)(3)(4)思考

圖的每種運(yùn)算的性質(zhì)有哪些?它與集合的并、交、差、(補(bǔ))及環(huán)和(對稱差)運(yùn)算的性質(zhì)有什么不同?(2)3.圖同構(gòu)由于圖的拓?fù)湫再|(zhì),有可能兩個表面上看起來不同的圖本質(zhì)上是同一個圖,這就是圖同構(gòu)的問題.Def設(shè)G1=(V1,E1)和G2=(V2,E2)是無向圖，若存在一個雙射

:V1→V2使得對于任意u,v∈V1，(u,v)∈E1當(dāng)且僅當(dāng)且(u)(v)∈E2且邊的重數(shù)相同，則稱G1與G2同構(gòu)，記為G1

G2.直觀理解:G1

G2是指其中一個圖僅經(jīng)過下列兩種變換可以變?yōu)榱硪粋€圖:(a)挪動節(jié)點(diǎn)的位置；(b)伸縮邊的長短.3.圖同構(gòu)無向圖:無向圖:有向圖:對于兩個有向圖同構(gòu)的判斷,特別要注意邊的方向的一致性.思考給出至少4個兩個圖同構(gòu)的必要條件.有向圖:對于兩個有向圖同構(gòu)的判斷,特別要注意邊的方向的一致Ulam猜想?Simplegraphs:Ulam猜想?6.4路與回路在圖G=(V,E)中,經(jīng)?？紤]從一個節(jié)點(diǎn)出發(fā),沿著一些邊連續(xù)移動到另一個節(jié)點(diǎn)的問題,這就是路的概念.1.路(walk,way)Def對于任意圖G=(V,E)中，稱G中節(jié)點(diǎn)與邊交替出現(xiàn)的序列為一條路。6.4路與回路在圖G=(V,E)中,經(jīng)?？紤]從一路的起點(diǎn);終點(diǎn);路的長度;平凡路.需要注意的是,有向圖中的路須按邊的方向走,有向圖中的路可稱為有向路.路的起點(diǎn);終點(diǎn);路的長度;平凡路.有兩種特殊的路:一種是節(jié)點(diǎn)不重復(fù)的路,稱為路徑.一種是邊不重復(fù)的路,稱為軌跡.顯然,路徑是軌跡,但軌跡不一定是路徑.說明由于圖論應(yīng)用的廣泛性,很多概念存在意義上的差別.之所以選擇“路徑”,它有捷徑之意；“軌跡”強(qiáng)調(diào)邊不重復(fù),它是(可能多次)走過后留下的痕跡.有兩種特殊的路:一種是節(jié)點(diǎn)不重復(fù)的路,稱為路徑.一種在n階圖G=(V,E)中,若存在從節(jié)點(diǎn)v0到vl一條路(v0

vl),則存在一條從v0到vl一條長度

n-1的路徑.Def在圖G=(V,E),稱節(jié)點(diǎn)u到v的邊數(shù)最少的長度為u到v的距離，記為d(u,v)。d(u,v):u到v邊數(shù)最少的路徑長度.稱maxd(u,v)為圖G的直徑，記為diam(G).在n階圖G=(V,E)中,若存在從節(jié)點(diǎn)v0到vl一條2.回路Def起點(diǎn)與終點(diǎn)相同的(長度1)路稱為回路.邊不重復(fù)的回路稱為簡單回路（閉跡).除起點(diǎn)重復(fù)一次外,別的節(jié)點(diǎn)均不重復(fù)的簡單回路稱為圈或環(huán),2.回路顯然,圈

簡單回路,但反過來不成立.有n個節(jié)點(diǎn)的圈稱為n階圈,記為Cn.

在n-1階圈Cn-1的內(nèi)部放置一個節(jié)點(diǎn),并使之與Cn-1的每個節(jié)點(diǎn)鄰接,這樣得到的圖稱為n階輪圖,記為Wn.顯然,圈簡單回路,但反過來不成立.在n階圖G=(V,E)中,若存在從節(jié)點(diǎn)v0到v0一條簡單回路,則存在一條從v0到v0一條長度

n

的圈.在n階圖G=(V,E)中,若存在從節(jié)點(diǎn)v0到v0一條采用“最長路徑法”技巧.Theorem在無向圖G=(V,E)中,若任意v

V有deg(v)2,則G中存在圈.Proof不妨設(shè)G是簡單圖.在G中選取一條最長的路徑L:v0v1…vl.采用“最長路徑法”技巧.6.5圖的連通性圖的基本性質(zhì)之一是其連通性,它與圖中從節(jié)點(diǎn)到節(jié)點(diǎn)的路密切相關(guān).為了討論方便,先給出Def在任何圖G=(V,E)中,若從節(jié)點(diǎn)u到v存在一條路,則稱u可達(dá)v

(accessible).由于節(jié)點(diǎn)v到v總存在一條長度為0的路,因此任意節(jié)點(diǎn)v可達(dá)v自身.6.5圖的連通性圖的基本性質(zhì)之一是其連通性,它與圖中從節(jié)先討論無向圖的連通性.1.無向圖的連通性Def6-17設(shè)G=(V,E)是無向圖,對于G中任意兩個節(jié)點(diǎn)u和v均可達(dá),則稱G是連通圖.先討論無向圖的連通性.Def設(shè)G=(V,E)是無向圖,G中極大的連通子圖稱為G的連通分支(connectedcomponent),圖G的連通分支數(shù)記為w(G).由定義知,圖G的連通分支滿足3個條件:(1)連通分支是G的子圖；(2)該子圖本身是連通圖；(3)在該子圖中再添加原圖的任意邊或節(jié)點(diǎn)都不連通.Def設(shè)G=(V,E)是無向圖,G中極大的連通子Theorem設(shè)G=(V,E)是無向圖,則G是連通圖當(dāng)且僅當(dāng)w(G)=1.G是非連通圖當(dāng)且僅當(dāng)w(G)

2.例6-5

G不連通連通.Hintu,v:(1)u,v在G中不鄰接.(2)u,v在G中鄰接:第一種方法:根據(jù)定義證明!Theorem設(shè)G=(V,E)是無向圖,則G是連通例6-6

設(shè)G=(V,E)是n階簡單無向圖,若對于任意的G中不相鄰的節(jié)點(diǎn)u和v有deg(u)+deg(v)

n-1,則G是連通圖.Hint(反證)Theorem6-7去掉簡單回路上的一條邊或度為1的節(jié)點(diǎn),圖的連通性不變.第二種方法:反證法!例6-6設(shè)G=(V,E)是n階簡單無向圖,若2.無向連通圖的點(diǎn)連通度與邊連通度對于無向連通圖,其連通的程度是不同的,有些很“脆弱”,有的則相反.(1)點(diǎn)割集與點(diǎn)連通度κ(G).Def設(shè)G=(V,E)是連通無向圖,W

V,(i)G–W不連通或是1階圖;(ii)刪除W的任意真子集均連通,則稱W為G的點(diǎn)割集.“割”是分割、分離、分開的意思,恰使得G不連通或是1階圖所要去掉的節(jié)點(diǎn)集合稱為的點(diǎn)割集.若點(diǎn)割集W={v},則稱v為的割點(diǎn)或關(guān)節(jié)點(diǎn).2.無向連通圖的點(diǎn)連通度與邊連通度點(diǎn)割集:{a,b};{c,d}.κ(G)=2.邊割集:{e1,e2,e3}.λ(G)=3.點(diǎn)割集:{a,b};{c,d}.κ(G)=2.割點(diǎn):A;B.κ(G)=1.割邊:e.λ(G)=1.割點(diǎn):A;B.κ(G)=1.Def根據(jù)定義,一個連通無向圖的點(diǎn)連通度是使得G不連通或?yàn)?階圖所要刪去的最少的節(jié)點(diǎn)個數(shù).于是,1階圖的點(diǎn)連通度為0,而完全無向圖Kn的點(diǎn)連通度為n-1.Def點(diǎn)連通度為2的圖G稱為2-連通或重連通圖.確定一個無向圖是否重連通具有重要的意義.假定無向圖的節(jié)點(diǎn)表示電話交換站,邊表示電話線,則在點(diǎn)連通度為2的通訊網(wǎng)絡(luò)系統(tǒng)中,一個站發(fā)生故障系統(tǒng)仍可正常工作.點(diǎn)連通度為2的圖G稱為2-連通或重連通圖.(2)邊割集與邊連通度λ(G).Def設(shè)G=(V,E)是連通無向圖且F

E,若從G中刪除F的所有邊所得到的子圖不連通或是平凡圖,而刪除F的任意真子集都連通,則稱F為G的邊割集.恰使得G不連通或是平凡圖所要去掉的邊的集合稱為G的邊割集.若邊割集F={e},則稱e為的割邊或橋.(2)邊割集與邊連通度λ(G).Def根據(jù)定義,一個連通無向圖G的邊連通度是使得G不連通或?yàn)槠椒矆D所要刪去的最少的邊的數(shù)目.H.Whitney在1932年給出的關(guān)于點(diǎn)連通度、邊連通度及最小度之間的聯(lián)系的一個結(jié)論.Theorem6-8設(shè)G=(V,E)是連通無向圖,則DefProof(1)由于將任意一個節(jié)點(diǎn)所關(guān)聯(lián)的邊全去掉后都不連通,所以有(2)設(shè)F是G的恰具有條邊的邊割集.考慮刪除F中條邊.刪除后不連通,顯然若刪除后連通,則存在橋uv={u,v}.再刪除u或v,即得知結(jié)論成立.Proof(1)由于將任意一個節(jié)點(diǎn)所關(guān)聯(lián)的邊全去掉后都不連3.有向圖的連通性(1)強(qiáng)連通圖Def設(shè)G=(V,E)是有向圖,

u,v

V均相互可達(dá),則稱G為強(qiáng)連通圖.(2)單向連通圖Def設(shè)G=(V,E)是有向圖,對于任意u,v

V,從u可達(dá)v或者從v可達(dá)u,則稱G為單向連通圖.(3)弱連通圖Def設(shè)G=(V,E)是有向圖,若不考慮邊的方向是一個無向連通圖,則稱有向圖G為弱連通圖，簡稱有向圖連通.3.有向圖的連通性(2)單向連通圖(3)弱連通圖強(qiáng)連通圖單向連通圖

弱連通圖.但反過來均不成立!第6章圖論課件Theorem6-9設(shè)G=(V,E)是n階(n≥2)有向圖,則G強(qiáng)連通當(dāng)且僅當(dāng)G中存在一條回路,它通過所有節(jié)點(diǎn).

Def設(shè)G=(V,E)是有向圖,G的極大的強(qiáng)連通子圖稱為G的強(qiáng)連通分支.(i)子圖;(ii)強(qiáng)連通;(iii)極大.Theorem6-9設(shè)G=(V,E)是n階(n≥2)Theorem6-10設(shè)G=(V,E)是有向圖,則G的任意節(jié)點(diǎn)都位于且僅位于的一個強(qiáng)連通分支中.Hint任意節(jié)點(diǎn)v本身強(qiáng)連通.Theorem6-10設(shè)G=(V,E)是有向圖,Def設(shè)G=(V,E)是有向圖,G的極大的單向連通子圖稱為G的單向連通分支.無向連通圖的節(jié)點(diǎn)可以位于不同的單向連通分支中.Def設(shè)G=(V,E)是有向圖,G的極大的弱連通子圖稱為G的弱連通分支.Def設(shè)G=(V,E)是有向圖,G的極大的單向連6.6圖的矩陣表示將一個圖畫出來是最直觀的表示圖的方式.為了便于使用計算機(jī)存儲和處理圖,更為了借助于完善的矩陣?yán)碚?線性代數(shù)知識之一!)研究圖的有關(guān)性質(zhì),有必要學(xué)習(xí)圖的矩陣表示.本節(jié)簡單介紹圖的常見的3種矩陣表示及一些簡單結(jié)論,不涉及更多的有關(guān)圖的矩陣方面的知識.6.6圖的矩陣表示將一個圖畫出來是最直觀的表示圖的方式.1.圖的鄰接(adjacency)矩陣第一種圖的矩陣表示—鄰接矩陣,它表示的是圖中任意兩個節(jié)點(diǎn)間的鄰接關(guān)系.Def6-29

G=(V,E),對節(jié)點(diǎn)編號V={v1,v2,…,vn}.其中aij是vi鄰接到vj的邊數(shù),i,j=1,2,…,n.1.圖的鄰接(adjacency)矩陣第6章圖論課件顯然,無向圖的鄰接矩陣是對稱矩陣.一個圖與其鄰接矩陣是一一對應(yīng)的.從一個圖G的鄰接矩陣A(G)容易得出每個節(jié)點(diǎn)的度數(shù).以有向圖為例,A(