圖論課件---01-2015

1、圖論任課教師：王磊基礎(chǔ)教學(xué)部數(shù)學(xué)教研室圖論發(fā)展史圖論在現(xiàn)代科學(xué)技術(shù)中有著廣泛的應(yīng)用,如： 網(wǎng)絡(luò)設(shè)計(jì)、計(jì)算機(jī)科學(xué)、信息科學(xué)、密碼學(xué)、DNA 的基因譜的確定和計(jì)數(shù)、工業(yè)生產(chǎn)和企業(yè)管理中 的優(yōu)化方法等都廣泛的應(yīng)用了圖論及其算法。首先我們通過(guò)圖的發(fā)展過(guò)程來(lái)了解一下圖論所 研究的內(nèi)容。圖論起源于1736年的一個(gè)游戲-哥尼斯城堡 七橋問(wèn)題。七橋問(wèn)題C包含兩個(gè)要素：對(duì)象（陸 地）及對(duì)象間的二元關(guān)系（是否有橋連接）C轉(zhuǎn)化ADEuler 1736年BADB圖論中討論的圖問(wèn)題：是否能從四塊 陸地中的任一塊開(kāi) 始，通過(guò)每座橋恰好 一次再回到起點(diǎn)？轉(zhuǎn)化 是否能從任意一個(gè) 頂點(diǎn)開(kāi)始，通過(guò)每 條邊恰好一次再回到起點(diǎn)？問(wèn)題

2、一：四色問(wèn)題四色問(wèn)題是世界近代三大 數(shù)學(xué)難題之一。四色問(wèn)題的內(nèi)容是：任何一張地圖只用四種顏色就能使具有共同邊界的國(guó)家著上不同的顏色。它 的 提 出 來(lái) 自 英 國(guó) 。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯 ·格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái)，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家 都被著上不同的顏色?！边M(jìn)入20世紀(jì)以來(lái)，科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行。后來(lái)美國(guó)數(shù) 學(xué)家富蘭克林于1939年證明了22國(guó)以下的地圖都 可以用四色著色。1950年，有人從22國(guó)推進(jìn)到35 國(guó)。1960年，有人又證明了39國(guó)以下的地圖可以 只用四種顏色著色；隨后又推進(jìn)到了50國(guó)

3、。1976年6月，美國(guó)伊利諾大學(xué)哈肯與阿佩爾在 兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作 了100億判斷，終于完成了四色定理的證明，轟動(dòng) 了世界。然而，真正數(shù)學(xué)上的嚴(yán)格證明仍然沒(méi)有得到！數(shù)學(xué)家仍為此努力，并由此產(chǎn)生了多個(gè)不同的圖論分支。問(wèn)題二：Hamilton問(wèn)題Hamilton問(wèn) 題 源 于 1856年 ，英 國(guó) 數(shù) 學(xué) 家 Hamilton 設(shè) 計(jì) 了一 個(gè) 名 為 周游世界 的游戲：他 用 一 個(gè) 正十二面 體的二十個(gè) 端 點(diǎn) 表 示世界上 的二十座大 城 市 （ 見(jiàn)圖）， 要求游戲者 找 一 條 沿著十二 面體的棱通 過(guò) 每 個(gè) 端點(diǎn)恰好 一次的行走 路 線 。 反映到圖 論上就

4、是判 斷 一 個(gè) 給定的圖 是否存在一條含所有頂點(diǎn)的回路。圖論是組合數(shù)學(xué)的一個(gè)分支，與其它數(shù)學(xué)分支如群論、矩陣論、集合論、概率論、拓 撲學(xué)、數(shù)值分析等有著密切的聯(lián)系。又由于圖論給含有二元關(guān)系的系統(tǒng)提供了 數(shù)學(xué)模型，因而在許多領(lǐng)域里都具有越來(lái)越 重要的地位，并且在物理、化學(xué)、信息學(xué)、 運(yùn)籌學(xué)等各方面都取得了豐碩的成果。從二十世際50年代以來(lái)，由于計(jì)算機(jī)的 迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)展，使得 圖論成為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。 因此,學(xué)好圖論十分重要。第八章圖論原理第1節(jié)圖的基本概念第2節(jié)通路、回路與連通性 第3節(jié)歐拉圖第4節(jié)哈密頓圖第5節(jié)圖的矩陣表示第8章圖論原理§8.1圖的基

5、本概念 一 、基本概念圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖,而是以一種抽象的形式來(lái)表達(dá)一些確定的事物之間的聯(lián)系的一個(gè)數(shù)學(xué)系統(tǒng).定義8.1.1 一個(gè)有序二元組(V, E ) 稱為一個(gè)圖,記為G = <V, E >, 其中 V稱為G的頂點(diǎn)集, Vf, 其元素稱為頂點(diǎn)或結(jié)點(diǎn), 簡(jiǎn)稱點(diǎn); E稱為G的邊集, 其元素稱為邊, 它聯(lián)結(jié)V 中的兩個(gè)點(diǎn), 如果這兩個(gè)點(diǎn)是無(wú)序的, 則稱該邊為無(wú)向邊, 否則, 稱為有向邊.例子8.1.1四個(gè)城市：v1、v2、v3、v4, 其中v1與v2間，v1與 v3間，v2與v4間有直達(dá)高速公路相連，寫(xiě)出其集 合并畫(huà)出此圖。解：G =V，E，V =

6、(v1，v2，v3，v4) ，E = (l1，l2，l3)，其中：l1= (v1, v2)l2= (v1, v3)l3 = (v2, v4)l1v1v2ll2 3v4v3(一)結(jié)點(diǎn)與邊的關(guān)系: 結(jié)點(diǎn)與邊(不)相 關(guān)聯(lián)：若一條邊 lk = (v ,v )，則稱結(jié)點(diǎn)vi、vj與邊lk相ij與邊l1、l2關(guān)聯(lián)。例如：前邊例題中結(jié)點(diǎn) v1相關(guān)聯(lián)，而與邊l3不相關(guān)聯(lián)。l1v1v2l結(jié)點(diǎn)與結(jié)點(diǎn),邊與邊(不)相鄰接A結(jié)點(diǎn)與結(jié)點(diǎn)：如果兩個(gè)結(jié)點(diǎn)與 同一條邊相關(guān)聯(lián), 則稱這兩個(gè)結(jié)點(diǎn)v4 相鄰接,否則不相鄰接如：例題中 v1 與 v2、v3 相鄰接，而與v4 不相 鄰接。2l3v3B邊與邊：如果若干條邊與同一個(gè)結(jié)點(diǎn)

7、相關(guān)聯(lián)，則稱這些邊是相鄰接的，否則不相 鄰接。如: 例題中 l2 與 l1 相鄰接，而與 l3 不相鄰接。l1v1v2l3l2v4v3(二)特殊點(diǎn):孤立點(diǎn):不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)懸掛點(diǎn):只與一條邊相鄰接的結(jié)點(diǎn)v1v1是孤立點(diǎn)v3 、v4是懸掛點(diǎn)v2v3v4(三)特殊的邊:環(huán):一條與兩個(gè)相同的結(jié)點(diǎn)相關(guān)聯(lián)的邊多重邊:與兩個(gè)結(jié)點(diǎn)相關(guān)聯(lián)的邊若多于一條，這些邊為多重邊。如圖：(四) 圖的分類: a 按邊的方向分類有向圖：邊有方向的圖無(wú)向圖：邊無(wú)方向的圖圖1 圖2稱點(diǎn)vi , vj為無(wú)向邊（vi ,vj )的端點(diǎn). 在有向圖中, 稱 點(diǎn)vivj分別為邊（vi ,vj )的起點(diǎn)和終點(diǎn)。b.按邊的種類分類：

8、多重圖:含多重邊的圖叫多重圖。簡(jiǎn)單圖:不含環(huán)與多重邊的圖叫簡(jiǎn)單圖。有權(quán)圖:有時(shí)在一個(gè)圖中邊的旁邊可以附 加數(shù)字以刻劃此邊的某些數(shù)量特征，叫做 邊的權(quán)，此邊叫做有權(quán)邊，具有有權(quán)邊的 圖叫有權(quán)圖或帶權(quán)圖。無(wú)權(quán)圖:沒(méi)有權(quán)邊的圖叫無(wú)權(quán)圖。G1、G2是多重圖G4是簡(jiǎn)單圖G3是多重圖A1有權(quán)圖BBBAA BA BBA A2B無(wú)權(quán)圖c.按結(jié)點(diǎn)集與邊集的“階”分類有限圖與無(wú)限圖：V 與 E 為有限集合的圖叫有限圖，否則叫 無(wú)限圖。(n,m)圖：有 n 個(gè)結(jié)點(diǎn)與 m 條邊的圖。零圖:即(n,0)圖;平凡圖:即(1,0)圖。一些特殊的圖定義8.1.2設(shè)G為n階無(wú)向簡(jiǎn)單圖，若G中每個(gè)頂點(diǎn) 均與其余的n-1個(gè)頂點(diǎn)相鄰

9、，則稱G為n階無(wú)向完 全圖，簡(jiǎn)稱n階完全圖，記做Kn(n1)。設(shè)D為n階有向簡(jiǎn)單圖，若D中每個(gè)頂點(diǎn)都鄰接到其余的n-1個(gè)頂點(diǎn)，又鄰接于其余的n-1個(gè)頂點(diǎn)，則稱D是n階有向完全(完備)圖。設(shè)D為n階有向簡(jiǎn)單圖，若D的基圖為n階無(wú)向完全圖Kn，則稱D是n階競(jìng)賽圖。(1)為K5，(2)為3階有向完全圖，(3)為4階競(jìng) 賽圖這幾種圖形的邊數(shù)： n階無(wú)向完全圖的邊數(shù)為n(n-1)/2 n階有向完全圖的邊數(shù)為n(n-1) n階競(jìng)賽圖的邊數(shù)為n(n-1)/2二、子圖定義8.1.3 設(shè)G=<V，E>，G =<V，E>為兩個(gè)圖(同為無(wú)向圖或同為有向圖)，若VÍV且E Í

10、;E，則稱G是G的子圖，G為G的母圖，記作GÍG. 又 若VÍV 且EÌE，則稱G為G的真子圖。若V=V， EÍE 則稱G為G的生成子圖。ababba1a1b11母圖真子圖d1c1dcdcaba1生成子圖b1G'ÍG且d1c1dcV'=V定義8.1.4設(shè)G=<V，E>為n階無(wú)向簡(jiǎn)單圖，以V為結(jié)點(diǎn)集，以使G成為完全圖Kn所添加邊構(gòu)成的集合為邊集的圖，稱為G的補(bǔ)圖，記做GG相對(duì)于Kn的補(bǔ)圖是下圖中的G時(shí)于補(bǔ)圖，顯然再以下結(jié)論:1、G 與 百 互為補(bǔ)圖 ， n G =G c2 、E(G )U E( G )=E(完全國(guó) )且

11、E(G )nE( E ) =申 。3、完全國(guó)與 n階零固互為補(bǔ)圖 c4、G 與 G 均是完全國(guó)的生成子固 ?；檠a(bǔ)圖互為補(bǔ)圖不是補(bǔ)圖三、結(jié)點(diǎn)的次數(shù)定義8.1.5：在有向圖中,對(duì)于任何結(jié)點(diǎn)v.引出次數(shù)(或出度):以v為始點(diǎn)的邊的條數(shù),記為deg+(v);引入次數(shù)(或入度):以v為終點(diǎn)的邊的條數(shù),記為deg-(v);次數(shù)(或度數(shù)):結(jié)點(diǎn)v的引出次數(shù)和引入次數(shù) 之和,記作deg(v)。deg+(v1)=2 deg+(v2)=1 deg+(v3)=2 deg+(v4)=2deg-(v1)=2 deg-(v2)=1 deg-(v3)=2 deg-(v4)=2deg(v1)=4 deg(v2)=2 deg

12、(v3)=4 deg(v4)=4在無(wú)向圖中,結(jié)點(diǎn)v的次數(shù)是與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù),也記為deg(v)。孤立結(jié)點(diǎn)的次數(shù)為零。l1deg(v1)=2v1v2deg(v2)=2l2l3deg(v3)=1v4v3deg(v4)=1握手定理定理8.1.1(握手定理) 設(shè)圖G=<V,E>為任意無(wú)向圖V=v1,v2,vn，|E|=m，則nåi =1d (vi ) = 2m有n個(gè)人握手，每人握手x次，握手總次數(shù)為S，必有S= nx/2證 G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。定理8.1.2(握手定理) 設(shè)D=&l

13、t;V,E>為任意有向 圖，V=v1,v2,vn，|E|=m，則nnnåd (vi ) = 2m且 åd(vi ) = åd(vi ) = m+-i=1i=1i=1練習(xí)1:2+2+1+6=11已知無(wú)向圖G中有10條邊，2個(gè)2度結(jié)點(diǎn),2個(gè)3度結(jié)點(diǎn),1 個(gè)4度結(jié)點(diǎn),其余結(jié)點(diǎn)的度數(shù)都是1,問(wèn)G中 有多少個(gè)結(jié)點(diǎn)?練習(xí)2:2+2+3=72+2+6=10已知無(wú)向圖G中有10條邊，3度與4度結(jié)點(diǎn)各2個(gè),其余結(jié)點(diǎn)的度數(shù)均小于3,問(wèn)G中至少有多少個(gè) 結(jié)點(diǎn)?最多有多少個(gè)結(jié)點(diǎn)?K5圖3彼得松圖定義8.1.6:各結(jié)點(diǎn)的次數(shù)均相同的圖稱為正則圖,各結(jié)點(diǎn)的次數(shù)均為k時(shí)稱為k正則圖。圖3

14、所示的稱為彼得松(Petersen)圖易見(jiàn)n階零圖是0-正則圖n階無(wú)向完全圖是(n-1)-正則圖彼得松圖是3-正則圖。四、圖的同構(gòu)試觀察下面各圖有何異同？定義8.1.7 G1=<V1,E1>和G2=<V2,E2>是兩個(gè)圖，若存在函數(shù)f:V1® V2 ,f是雙射，且若定義函數(shù) g : E1® E2 ,對(duì)于任意的 (v1 ,v1¢) Î E1 , g(v1, v1¢) = (f (v1 ),f (v1¢).g也是一個(gè)雙射則稱圖G1和圖G2是同構(gòu)的兩個(gè)圖，并稱 f 為圖的同構(gòu)映射，記為G G .12v1u1v4v2v

15、3u 4(a)(b)兩個(gè)同構(gòu)的u2圖，在我們討論的范圍內(nèi)認(rèn)為是一u樣的圖4圖 4所 示 的 兩圖是 同構(gòu)的。 因?yàn)樽?映射g(vi)=vi(i=1,2,6), 可 使 (vi,vj) 一 一 對(duì) 應(yīng) 于(g(vi),g(vj)。圖4u3u1u2u4可以看到此兩圖在結(jié)點(diǎn)間存在著一一對(duì)應(yīng)映射g：g(a)u3， g(b)u1，g(c)u4，g(d)u2，且有（a,c），（a,b），（b,d），（c,d）分別與（u3,u4）,（u3,u1），（u1,u2），（u4,u2）一一對(duì)應(yīng)。同構(gòu)分析本例還可以知道，此兩圖的結(jié)點(diǎn)度數(shù)也分別對(duì)應(yīng)相等，如表所示。同構(gòu)的性質(zhì)(必要條件)：1結(jié)點(diǎn)數(shù)目相同；2邊數(shù)相等；3度

16、數(shù)相同的結(jié)點(diǎn)數(shù)目相等。不是充分條件，下圖(a)和(b)滿足上述三個(gè)條 件，但并不同構(gòu)。若 G與 G同構(gòu)，它的充要條件是：兩個(gè)圖的結(jié)點(diǎn)和邊分別存在著一一對(duì)應(yīng)，且保持關(guān)聯(lián)關(guān)系。G1 G2 .G3 G4在 G1 G G5 G6點(diǎn)間的對(duì)應(yīng)關(guān)系為：G7與G8不同構(gòu)2 . 中，結(jié)av1, bv2, cv3, dv4, ev5G5稱為彼得松圖圖中(a)(b)均滿足前面3個(gè)條件，但因?yàn)閷?duì)于圖(a)中的任一頂點(diǎn)，與該點(diǎn)關(guān)聯(lián)的3個(gè)頂點(diǎn)間彼此不 鄰接；而對(duì)于圖(b)中的任一頂點(diǎn)，與該點(diǎn)關(guān)聯(lián) 的3個(gè)頂點(diǎn)中有2個(gè)是鄰接點(diǎn)，所以它們不同同構(gòu)樣?？梢钥闯鰣D(c)(d)也是不同構(gòu)的。§8.2通路、回路、圖的連通性先

17、討論有向圖的通路、回路，然后推廣到無(wú)向圖 一、通路定義8.2.1 給定有向圖 G=<V,E>,設(shè)G中頂點(diǎn)與邊 的交替序列 =v0e1v1e2 elvl，若滿足如下 條件：vi-1 是ei的始點(diǎn),vi 是ei的終點(diǎn),i=0,1,l , 則 稱為頂點(diǎn)v0到vl的通路。v0和vl分別稱為此通 路的起點(diǎn)和終點(diǎn),中邊的數(shù)目l 稱為的長(zhǎng) 度。ü若v0=vi ，則稱此通路為回路。ü若中所有邊各異，則稱為簡(jiǎn)單通路ü若中所有點(diǎn)各異，則稱為基本通路。P4, P6則即非基本下圖：起點(diǎn)為1，終點(diǎn)為通3路的亦通非路簡(jiǎn)有單：通路P1: (1, 2, 3),P2: (1, 4, 3

18、)12P3: (1, 2, 4, 3)P4: (1, 2, 4, 1, 2, 3)P5: (1, 2, 4, 1, 4, 3)P6: (1, 1,1, 2, 3)43簡(jiǎn)單通路：各邊都不相同的通路?；就罚焊鼽c(diǎn)都不相同的通路。一條基本通路一定是簡(jiǎn)單通路, 反之不然。如P5:是簡(jiǎn)單 通路但不是基本通路。 P1, P2, P3是基本通路.二、回路回路:起始結(jié)點(diǎn)與終止結(jié)點(diǎn)相同的通路?？梢?jiàn)回路是一種特殊的通路。12簡(jiǎn)單回路:各邊都不同基本回路:各點(diǎn)都不同C1: (1, 1),C2: (1, 2, 1)C3: (1, 2, 3, 1)C4: (1, 4, 3, 1)C5: (1, 2, 3, 2, 1)

19、43C6: (1, 2, 3, 2, 3, 1), C1, C2, C3 , C4是基本回路, (當(dāng)然也是簡(jiǎn)單回路), C5是簡(jiǎn)單回路但非基本回路, 而C6既非基本回路亦非簡(jiǎn)單回路。例如：v0v1v2v3v41圖(1) 為v0 到v4的長(zhǎng)為4的 基本通路v0v1v22v7v8v3v4v6v5 v4圖(2)為v0 到v8的長(zhǎng)為8的 簡(jiǎn)單通路v0= v5v1v2v3v4圖(3) 為v0 到v5(= v0)的3長(zhǎng)為5的基本回路vvv0= v815圖(4) 為v0 到v8(= v0)的vv27v6v34長(zhǎng)為8的簡(jiǎn)單回路有向圖中, 環(huán)和兩條方向相反邊構(gòu)成的回路分別為長(zhǎng)度為1和2的基本回路(圈)。定理8.

20、2.1在有向(n,m)圖中，任何基本通路長(zhǎng)度小于或等于n-1。定理8.2.2在有向(n,m)圖中，任何基本回路長(zhǎng)度小 于或等于n。例8.2.1：求下圖回路數(shù)和C到B的通路A要求各找出4個(gè)以上e8(e2),(e3, e4, e2),(e3, e5, e6, e10, e2),e7e9Fe1Be10(e3, e5, e6, e7, e1)是從Ce6e2到B的4個(gè)通路。這4條Ee4C通路中第一條、第四條是基本通路；e5e3D(e3, e4),(e3, e5, e6, e10),(e8),(e9)是4條有向回路;上圖中,從B到其它任意點(diǎn)都沒(méi)有回路。定義8.2.2在一個(gè)有向圖G中，若從頂點(diǎn)vi到vj 存在通路，則稱vi與vj是可達(dá)的的。短程線:有向圖G中，從結(jié)點(diǎn)vi到vj長(zhǎng)度最短的通 路。距離：短程線的長(zhǎng)度稱為vi與vj之間的距離,記 作 d<vi ,vj>,當(dāng)vi不可達(dá)vj時(shí),規(guī)定 d<vi,vj>=注：相應(yīng)概念可以推廣到無(wú)向圖，將無(wú)向圖中 方向相反的兩條邊轉(zhuǎn)換成一條無(wú)向邊。例8.2.2在(a)中有：d(v2，v1)1，d(v1，v2)2，d(v3，v1)2，d(v1，v3)4；在(b)中有：d(v1，v3)2，d(v3，v7)3，d(