圖論課件---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)用了圖論及其算法。首先我們通過圖的發(fā)展過程來了解一下圖論所 研究的內(nèi)容。圖論起源于1736年的一個(gè)游戲-哥尼斯城堡 七橋問題。七橋問題C包含兩個(gè)要素：對象（陸 地）及對象間的二元關(guān)系（是否有橋連接）C轉(zhuǎn)化ADEuler 1736年BADB圖論中討論的圖問題：是否能從四塊 陸地中的任一塊開 始，通過每座橋恰好 一次再回到起點(diǎn)？轉(zhuǎn)化 是否能從任意一個(gè) 頂點(diǎn)開始，通過每 條邊恰好一次再回到起點(diǎn)？問題

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

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

4、是判 斷 一 個(gè) 給定的圖 是否存在一條含所有頂點(diǎn)的回路。圖論是組合數(shù)學(xué)的一個(gè)分支，與其它數(shù)學(xué)分支如群論、矩陣論、集合論、概率論、拓 撲學(xué)、數(shù)值分析等有著密切的聯(lián)系。又由于圖論給含有二元關(guān)系的系統(tǒng)提供了 數(shù)學(xué)模型，因而在許多領(lǐng)域里都具有越來越 重要的地位，并且在物理、化學(xué)、信息學(xué)、 運(yùn)籌學(xué)等各方面都取得了豐碩的成果。從二十世際50年代以來，由于計(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、本概念 一 、基本概念圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖,而是以一種抽象的形式來表達(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), 簡稱點(diǎn); E稱為G的邊集, 其元素稱為邊, 它聯(lián)結(jié)V 中的兩個(gè)點(diǎn), 如果這兩個(gè)點(diǎn)是無序的, 則稱該邊為無向邊, 否則, 稱為有向邊.例子8.1.1四個(gè)城市：v1、v2、v3、v4, 其中v1與v2間，v1與 v3間，v2與v4間有直達(dá)高速公路相連，寫出其集 合并畫出此圖。解：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 按邊的方向分類有向圖：邊有方向的圖無向圖：邊無方向的圖圖1 圖2稱點(diǎn)vi , vj為無向邊（vi ,vj )的端點(diǎn). 在有向圖中, 稱 點(diǎn)vivj分別為邊（vi ,vj )的起點(diǎn)和終點(diǎn)。b.按邊的種類分類：

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

9、，則稱G為n階無向完 全圖，簡稱n階完全圖，記做Kn(n1)。設(shè)D為n階有向簡單圖，若D中每個(gè)頂點(diǎn)都鄰接到其余的n-1個(gè)頂點(diǎn)，又鄰接于其余的n-1個(gè)頂點(diǎn)，則稱D是n階有向完全(完備)圖。設(shè)D為n階有向簡單圖，若D的基圖為n階無向完全圖Kn，則稱D是n階競賽圖。(1)為K5，(2)為3階有向完全圖，(3)為4階競 賽圖這幾種圖形的邊數(shù)： n階無向完全圖的邊數(shù)為n(n-1)/2 n階有向完全圖的邊數(shù)為n(n-1) n階競賽圖的邊數(shù)為n(n-1)/2二、子圖定義8.1.3 設(shè)G=<V，E>，G =<V，E>為兩個(gè)圖(同為無向圖或同為有向圖)，若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階無向簡單圖，以V為結(jié)點(diǎn)集，以使G成為完全圖Kn所添加邊構(gòu)成的集合為邊集的圖，稱為G的補(bǔ)圖，記做GG相對于Kn的補(bǔ)圖是下圖中的G時(shí)于補(bǔ)圖，顯然再以下結(jié)論:1、G 與 百 互為補(bǔ)圖 ， n G =G c2 、E(G )U E( G )=E(完全國 )且

11、E(G )nE( E ) =申 。3、完全國與 n階零固互為補(bǔ)圖 c4、G 與 G 均是完全國的生成子固 。互為補(bǔ)圖互為補(bǔ)圖不是補(bǔ)圖三、結(jié)點(diǎn)的次數(shù)定義8.1.5：在有向圖中,對于任何結(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在無向圖中,結(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>為任意無向圖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已知無向圖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,問G中 有多少個(gè)結(jié)點(diǎn)?練習(xí)2:2+2+3=72+2+6=10已知無向圖G中有10條邊，3度與4度結(jié)點(diǎn)各2個(gè),其余結(jié)點(diǎn)的度數(shù)均小于3,問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)圖易見n階零圖是0-正則圖n階無向完全圖是(n-1)-正則圖彼得松圖是3-正則圖。四、圖的同構(gòu)試觀察下面各圖有何異同？定義8.1.7 G1=<V1,E1>和G2=<V2,E2>是兩個(gè)圖，若存在函數(shù)f:V1® V2 ,f是雙射，且若定義函數(shù) g : E1® E2 ,對于任意的 (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) 一 一 對 應(yīng) 于(g(vi),g(vj)。圖4u3u1u2u4可以看到此兩圖在結(jié)點(diǎn)間存在著一一對應(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）一一對應(yīng)。同構(gòu)分析本例還可以知道，此兩圖的結(jié)點(diǎn)度數(shù)也分別對應(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)和邊分別存在著一一對應(yīng)，且保持關(guān)聯(lián)關(guān)系。G1 G2 .G3 G4在 G1 G G5 G6點(diǎn)間的對應(yīng)關(guān)系為：G7與G8不同構(gòu)2 . 中，結(jié)av1, bv2, cv3, dv4, ev5G5稱為彼得松圖圖中(a)(b)均滿足前面3個(gè)條件，但因?yàn)閷τ趫D(a)中的任一頂點(diǎn)，與該點(diǎn)關(guān)聯(lián)的3個(gè)頂點(diǎn)間彼此不 鄰接；而對于圖(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、討論有向圖的通路、回路，然后推廣到無向圖 一、通路定義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 稱為的長 度。ü若v0=vi ，則稱此通路為回路。ü若中所有邊各異，則稱為簡單通路ü若中所有點(diǎn)各異，則稱為基本通路。P4, P6則即非基本下圖：起點(diǎn)為1，終點(diǎn)為通3路的亦通非路簡有單：通路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簡單通路：各邊都不相同的通路。基本通路：各點(diǎn)都不相同的通路。一條基本通路一定是簡單通路, 反之不然。如P5:是簡單 通路但不是基本通路。 P1, P2, P3是基本通路.二、回路回路:起始結(jié)點(diǎn)與終止結(jié)點(diǎn)相同的通路?？梢娀芈肥且环N特殊的通路。12簡單回路:各邊都不同基本回路:各點(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)然也是簡單回路), C5是簡單回路但非基本回路, 而C6既非基本回路亦非簡單回路。例如：v0v1v2v3v41圖(1) 為v0 到v4的長為4的 基本通路v0v1v22v7v8v3v4v6v5 v4圖(2)為v0 到v8的長為8的 簡單通路v0= v5v1v2v3v4圖(3) 為v0 到v5(= v0)的3長為5的基本回路vvv0= v815圖(4) 為v0 到v8(= v0)的vv27v6v34長為8的簡單回路有向圖中, 環(huán)和兩條方向相反邊構(gòu)成的回路分別為長度為1和2的基本回路(圈)。定理8.

20、2.1在有向(n,m)圖中，任何基本通路長度小于或等于n-1。定理8.2.2在有向(n,m)圖中，任何基本回路長度小 于或等于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)都沒有回路。定義8.2.2在一個(gè)有向圖G中，若從頂點(diǎn)vi到vj 存在通路，則稱vi與vj是可達(dá)的的。短程線:有向圖G中，從結(jié)點(diǎn)vi到vj長度最短的通 路。距離：短程線的長度稱為vi與vj之間的距離,記 作 d<vi ,vj>,當(dāng)vi不可達(dá)vj時(shí),規(guī)定 d<vi,vj>=注：相應(yīng)概念可以推廣到無向圖，將無向圖中 方向相反的兩條邊轉(zhuǎn)換成一條無向邊。例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(