圖論及其應(yīng)用教學(xué)課件

1、圖論及其應(yīng)用第1頁(yè)，共101頁(yè)。圖論發(fā)展史 圖論在現(xiàn)代科學(xué)技術(shù)中有著重要的理論價(jià)值和廣泛的應(yīng)用背景，如：線性代數(shù)、密碼學(xué)、物理化學(xué)、網(wǎng)絡(luò)設(shè)計(jì)、計(jì)算機(jī)科學(xué)、信息科學(xué)、DNA的基因譜的確定和計(jì)數(shù)、工業(yè)生產(chǎn)和企業(yè)管理中的優(yōu)化方法等都廣泛的應(yīng)用了圖論及其算法。 首先我們通過(guò)圖的發(fā)展過(guò)程來(lái)了解一下圖論所研究的內(nèi)容。 圖論起源于18世紀(jì)的一個(gè)游戲-俄羅斯的哥尼斯堡七橋問(wèn)題。 （1736年 瑞士數(shù)學(xué)家歐拉圖論之父）第2頁(yè)，共101頁(yè)。A B D C 轉(zhuǎn)化 Euler1736年 B D CA 圖論中討論的圖 問(wèn)題：是否能從A，B，C，D中的任一個(gè)開(kāi)始走，通過(guò)每座橋恰好一次再回到起點(diǎn)？是否能從任意一個(gè)頂點(diǎn)開(kāi)始，

2、通過(guò)每條邊恰好一次再回到起點(diǎn)？轉(zhuǎn)化包含兩個(gè)要素：對(duì)象（陸地）及對(duì)象間的二元關(guān)系（是否有橋連接）七 橋 問(wèn) 題第3頁(yè)，共101頁(yè)。中國(guó)郵遞員問(wèn)題1962年中國(guó)數(shù)學(xué)家管梅谷提出圖論中的“中國(guó)郵遞員問(wèn)題”。問(wèn)題：一個(gè)郵遞員從街區(qū)的某一點(diǎn)出發(fā)，經(jīng)過(guò)街區(qū)每條街道至少一次又回到原出發(fā)點(diǎn)，如何設(shè)計(jì)投遞路線，使總路程最短？第4頁(yè)，共101頁(yè)。 Hamilton問(wèn)題源于1856年，英國(guó)數(shù)學(xué)家Hamilton設(shè)計(jì)了一個(gè)名為周游世界的游戲：他用一個(gè)正十二面體的二十個(gè)端點(diǎn)表示世界上的二十座大城市（見(jiàn)圖），提出的問(wèn)題是要求游戲者找一條沿著十二面體的棱通過(guò)每個(gè)端點(diǎn)恰好一次的行走路線。反映到圖論上就是判斷一個(gè)給定的圖是否存

3、在一條含所有頂點(diǎn)的回路。Hamilton問(wèn)題第5頁(yè)，共101頁(yè)。 四色問(wèn)題是世界近代三大數(shù)學(xué)難題之一。 四色問(wèn)題的內(nèi)容是：任何一張地圖只用四種顏色就能使具有共同邊界的國(guó)家著上不同的顏色。 它的提出來(lái)自英國(guó)。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái)，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都被著上不同的顏色?！边@個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？四色問(wèn)題第6頁(yè)，共101頁(yè)。 1872年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問(wèn)題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問(wèn)題。 18781880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證

4、明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了。 1890年，在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計(jì)算指出了肯普在證明上的漏洞。不久，泰勒的證明也被人們否定了。后來(lái)，人們開(kāi)始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題。第7頁(yè)，共101頁(yè)。 進(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ó)。 1976年6月，美國(guó)伊利諾大學(xué)哈肯與

5、阿佩爾在兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明，轟動(dòng)了世界。 然而，真正數(shù)學(xué)上的嚴(yán)格證明仍然沒(méi)有得到！數(shù)學(xué)家仍為此努力，并由此產(chǎn)生了多個(gè)不同的圖論分支。第8頁(yè)，共101頁(yè)。幾個(gè)事實(shí)：任意的6個(gè)人中，總有3個(gè)人互相認(rèn)識(shí)或有3個(gè)人互不認(rèn) 識(shí)。任意的9個(gè)人中，總有3個(gè)人互相認(rèn)識(shí)或有4個(gè)人互不認(rèn) 識(shí)。問(wèn)題： 對(duì)任意的自然數(shù)k和t，是否存在一個(gè)最小的正整數(shù)r(k,t)，使得每個(gè)至少有r(k,t)個(gè)人的團(tuán)體，總有k個(gè)人互相認(rèn)識(shí)或有t個(gè)人互不認(rèn)識(shí)。 拉姆瑟（F.P. Ramsey）在1930年證明了這個(gè)數(shù) r(k,t)是存在的，人們稱(chēng)之為 Ramsey數(shù)。確定

6、其精確值是個(gè)公開(kāi)的難題。Ramsey 問(wèn)題第9頁(yè)，共101頁(yè)。Ramsey數(shù)R(p,q)第10頁(yè)，共101頁(yè)。Ramsey數(shù)的計(jì)算Ramsey數(shù)的計(jì)算是對(duì)人類(lèi)智力的挑戰(zhàn)！例如R(4,5)=25 (1993年計(jì)算機(jī)11年的計(jì)算量)Erds用如下比喻說(shuō)明其困難程度：一伙外星人入侵地球，要求一年內(nèi)求得R(5,5)，否則將滅絕人類(lèi)！那么也許人類(lèi)能集中所有計(jì)算機(jī)和專(zhuān)家來(lái)求出它以自保；但如果外星人問(wèn)的是R(6,6) ，那么人類(lèi)將別無(wú)選擇，只能拼死一戰(zhàn)了。第11頁(yè)，共101頁(yè)。Ramsey理論的哲理意義完全的無(wú)序是不可能的(Complete disorder is impossible)。任一足夠大的結(jié)構(gòu)中

7、必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)。無(wú)序無(wú)意的行為產(chǎn)生了有規(guī)律的后果，發(fā)人深思耐人尋味。古人在滿天的星斗中發(fā)現(xiàn)野獸和眾神群集于天空的圖形，以為是造物主的杰作。但根據(jù)Ramsey 定理，只要隨機(jī)分布的星星數(shù)目足夠多，就可以描繪出各種圖形的輪廓。1994年Statistical Science的一篇論文利用統(tǒng)計(jì)方法證明：圣經(jīng)隱藏了許多訊息，而這些訊息是有意安排的，絕非文字排列偶然造成的。 1997 年Michael Drosnin的The Bible Code 通過(guò)計(jì)算機(jī)掃讀圣經(jīng)中的304805個(gè)字母，發(fā)現(xiàn)圣經(jīng)密碼當(dāng)中傳達(dá)的訊息除了拉賓被刺殺外，還包括美國(guó)肯尼迪和林肯兩位總統(tǒng)，以及印度總理甘地遇刺的

8、事件，日本神戶、美國(guó)舊金山的大地震、世界末日與廣島原子彈轟炸等，種種過(guò)去與未來(lái)發(fā)生的大事件。Ramsey理論的哲理意義第12頁(yè)，共101頁(yè)。最精美的組合定理Rota：如果要求在組合學(xué)中僅舉出一個(gè)精美的定理，那么大多數(shù)組合學(xué)家會(huì)提名Ramsey定理。1984年Wolf獎(jiǎng)得主Erds1997年Fulkerson獎(jiǎng)得主Kim1998年Fields獎(jiǎng)得主Gowers1999年Wolf獎(jiǎng)得主Lovasz2003年Steele獎(jiǎng)得主Graham2005年Gdel獎(jiǎng)得主Alon2006年Fields獎(jiǎng)得主Tao 均對(duì)Ramsey理論有杰出貢獻(xiàn)第13頁(yè)，共101頁(yè)。第14頁(yè)，共101頁(yè)。Ramsey理論的哲理

9、意義第15頁(yè)，共101頁(yè)。某村里有n 個(gè)男士與n 個(gè)女士，每個(gè)男士恰好認(rèn)識(shí) r 個(gè)女士，每個(gè)女士也恰好認(rèn)識(shí) r 個(gè)男士，問(wèn)：在這個(gè)村中，能否做到：每個(gè)男士與其認(rèn)識(shí)的女士結(jié)婚，每個(gè)女士也恰好與其認(rèn)識(shí)的男士結(jié)婚?；橐銎ヅ涞?6頁(yè)，共101頁(yè)。圖論相關(guān)的交叉研究 代數(shù)圖論 拓?fù)鋱D論 化學(xué)圖論 算法圖論 隨機(jī)圖論 極值圖論 超圖以往數(shù)學(xué)家習(xí)慣將純數(shù)學(xué)應(yīng)用于其它學(xué)科，Gowers將圖論和組合數(shù)學(xué)中的Ramsey理論應(yīng)用于泛函分析的研究，獲得了1998年的Fields獎(jiǎng)。第17頁(yè)，共101頁(yè)。內(nèi)容提要圖的基本概念圖的基本概念；二部圖及其性質(zhì)；圖的同構(gòu)；關(guān)聯(lián)矩陣與鄰接矩陣。路、圈與連通圖；最短路問(wèn)題。樹(shù)及其

10、基本性質(zhì)；最小生成樹(shù)。圖的連通性割點(diǎn)、割邊和塊；邊連通與點(diǎn)連通；連通度；Whitney 定理；可靠通信網(wǎng)絡(luò)的設(shè)計(jì)。匹配問(wèn)題匹配與最大匹配；完美匹配；二部圖的最大匹配。第18頁(yè)，共101頁(yè)。歐拉圖與哈密爾頓圖歐拉圖；中國(guó)郵遞員問(wèn)題；哈密爾頓圖；旅行商問(wèn)題。獨(dú)立集、覆蓋集與團(tuán)點(diǎn)獨(dú)立集、點(diǎn)覆蓋集、邊覆蓋集與團(tuán)的概念。圖的著色問(wèn)題點(diǎn)著色；邊著色；平面圖；四色猜想。網(wǎng)絡(luò)流理論有向圖；網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念；最大流最小割定理；求最大流的標(biāo)號(hào)算法；網(wǎng)絡(luò)流理論的應(yīng)用。第19頁(yè)，共101頁(yè)。主要參考書(shū)1 J.A. Bondy and U.S. Murty, Graph Theory with Applicati

11、ons, 1976 （GTM244, 2008）。2 B. Bollobas, Modern Graph Theory (現(xiàn)代圖論)，科學(xué)出版社，2001。3 王樹(shù)禾，圖論，科學(xué)出版社，2004。4 蔣長(zhǎng)浩，圖論與網(wǎng)絡(luò)流，中國(guó)林業(yè)出版社，2001。5 徐俊明，圖論及其應(yīng)用，中國(guó)科技大學(xué)出版社，1998。第20頁(yè)，共101頁(yè)。第一章 圖和子圖1.1 圖和簡(jiǎn)單圖1.2 子圖1.3 圖的同構(gòu)1.4 頂點(diǎn)的度1.5 路、圈和連通1.6 關(guān)聯(lián)矩陣和鄰接矩陣1.7 應(yīng)用： 最短路問(wèn)題第21頁(yè)，共101頁(yè)。1.1 圖和簡(jiǎn)單圖第22頁(yè)，共101頁(yè)。圖graph， 頂點(diǎn)vertex，邊edge圖的定義其中V(G

12、) 是非空的頂點(diǎn)集， E(G)是不與V(G)相交的邊集，而 是關(guān)聯(lián)函數(shù)，它使G的每條邊對(duì)應(yīng)于G 的無(wú)序頂點(diǎn)對(duì)。若e是一條邊，而u和v是使得 的頂點(diǎn)，則稱(chēng) e連接 u 和 v ；頂點(diǎn) u 和 v 稱(chēng)為 e 的端點(diǎn)。 一個(gè)圖 G 是指一個(gè)有序三元組 ，第23頁(yè)，共101頁(yè)。例 1此時(shí)， 定義為這便定義出一個(gè)圖。第24頁(yè)，共101頁(yè)。圖的圖形表示 通常，圖的頂點(diǎn)可用平面上的一個(gè)點(diǎn)來(lái)表示，邊可用平面上的線段來(lái)表示（直的或曲的），而邊僅在端點(diǎn)處相交， 這樣畫(huà)出的平面圖形稱(chēng)為圖的圖形表示。第25頁(yè)，共101頁(yè)。G = (V, E) ，其中這便定義出一個(gè)圖。例2注：由于表示頂點(diǎn)的平面點(diǎn)的位置的任意性，同一個(gè)

13、圖可以畫(huà)出形狀迥異的很多圖示。例2中圖的另一個(gè)圖示：第26頁(yè)，共101頁(yè)。 圖的圖示直觀易懂，因此以后一般說(shuō)到一個(gè)圖，我們總是畫(huà)出它的一個(gè)圖示來(lái)表示。 閱讀書(shū)P.2-3頁(yè)，理解平面圖和非平面圖，并且完成課后習(xí)題1.1.2。第27頁(yè)，共101頁(yè)。一些概念和術(shù)語(yǔ)：（1） 點(diǎn)與邊的關(guān)聯(lián)(incident)（2） 點(diǎn)與點(diǎn)的相鄰(adjacent)（3） 邊與邊的相鄰（4）（自）環(huán)(loop)、連桿(link)（5）重邊(parallel edge)（6）簡(jiǎn)單圖(simple graph)（7）有限圖(finite graph)（8）平凡圖(trivial graph)和非平凡圖（9）空?qǐng)D(empty

14、graph)和零圖（null graph)（10）圖的頂點(diǎn)數(shù)（圖的階order） 、邊數(shù)(size)第28頁(yè)，共101頁(yè)。1.2 圖的同構(gòu) 由前已知，同一個(gè)圖有不同形狀的圖示。反過(guò)來(lái)，兩個(gè)不同的圖也可以有形狀相同的圖示。比如： 可見(jiàn) G1 和 G2 的頂點(diǎn)及邊之間都一一對(duì)應(yīng)，且連接關(guān)系完全相同，只是頂點(diǎn)和邊的名稱(chēng)不同而已。這樣的兩個(gè)圖稱(chēng)為是同構(gòu)的(isomorphic)。第29頁(yè)，共101頁(yè)。 從數(shù)學(xué)上看，同構(gòu)的兩個(gè)圖，其頂點(diǎn)間可建立一一對(duì)應(yīng)，邊之間也能建立一一對(duì)應(yīng)，且若一圖的兩點(diǎn)間有邊，則在另一圖中對(duì)應(yīng)的兩點(diǎn)間有對(duì)應(yīng)的邊。嚴(yán)格的數(shù)學(xué)定義如下。定義: 兩個(gè)圖G = (V (G), E(G) 與

15、H = (V (H), E(H) ，如果存在兩個(gè)一一映射： :V (G) V (H) ， : E(G) E(H) ，使得對(duì)任意e = (u,v) E(G) ，都有( (u), (v) E(H) 且 (e) = ( (u), (v) ，則稱(chēng)圖G 與H 同構(gòu)。記為G H 。第30頁(yè)，共101頁(yè)。 G1、G2 在對(duì)應(yīng)viui (i=1,2,3,4,5,6)下是同構(gòu)的。例3x1x2y1x3y2y3v1v2v3v4v5v6第31頁(yè)，共101頁(yè)。畫(huà)出所有的階數(shù)不大于4，大小為3的所有非同構(gòu)簡(jiǎn)單圖：第32頁(yè)，共101頁(yè)。畫(huà)出階數(shù)為5大小為3的所有非同構(gòu)簡(jiǎn)單圖G1G2G3G4第33頁(yè)，共101頁(yè)。無(wú)標(biāo)號(hào)的圖注

16、：判斷兩個(gè)圖是否同構(gòu)目前沒(méi)有好算法。第34頁(yè)，共101頁(yè)。一些特殊圖類(lèi)：（1） 完全圖(complete graph)例 4K3K4K5K5第35頁(yè)，共101頁(yè)。（2） 二部圖 (bipartite graph)：若圖G 的頂點(diǎn)集可劃分為兩個(gè)非空子集X 和Y，使得任一條邊有一個(gè)端點(diǎn)在X 中，另一個(gè)端點(diǎn)在Y 中，則稱(chēng)G 為二部圖（或偶圖），記為G (X U Y , E) ，(X ,Y ) 稱(chēng)為G 的一個(gè)劃分（二分類(lèi)）。第36頁(yè)，共101頁(yè)。K3,3 K2,4 （3）完全二部圖(complete bipartite graph)：在簡(jiǎn)單二部圖G = (X U Y , E) 中，若X 的每個(gè)頂點(diǎn)與Y

17、的每個(gè)頂點(diǎn)有邊連接，則稱(chēng)G 為完全二部圖；若| X |= m，|Y |= n ，則記此完全二部圖為K m , n。特別地， K 1 , n 稱(chēng)為星。第37頁(yè)，共101頁(yè)。（4） r部圖、完全r部圖任意一個(gè)Vi 內(nèi)部都沒(méi)有邊。完全 r-部圖K(n1,n2,nr)：如果任意Vi中的所有點(diǎn)與Vj中的所有點(diǎn)都相連。一個(gè)簡(jiǎn)單圖叫作r-部圖, 如果第38頁(yè)，共101頁(yè)。（6） G的補(bǔ)圖(complement)： 設(shè)G 是一個(gè)圖，以V (G) 為頂點(diǎn)集，以(x, y) | (x, y) E(G)為邊集的圖稱(chēng)為G 的補(bǔ)圖，記為GC。第39頁(yè)，共101頁(yè)。1.3 子圖(1) 子圖(subgraph)： 如果V

18、(H) V (G) 且 E(H) E(G) ，則稱(chēng)圖 H 是G 的子圖，記為 H G 。(2) 生成子圖(spanning subgraph): 若H 是G 的子圖且V(H)=V(G)，則稱(chēng)H 是G 的生成子圖。(3) 點(diǎn)導(dǎo)出子圖(induced subgraph)： 設(shè)V V (G) ，以V 為頂點(diǎn)集，以?xún)啥它c(diǎn)均在 V 中的邊的全體為邊集所組成的子圖，稱(chēng)為 G 的由頂點(diǎn)集 V 導(dǎo)出的子圖，簡(jiǎn)稱(chēng)為 G 的點(diǎn)導(dǎo)出子圖，記為GV 。第40頁(yè)，共101頁(yè)。(4) 邊導(dǎo)出子圖(edge-induced subgraph)：設(shè)E E(G) ，以 E 為邊集，以 E 中邊的端點(diǎn)全體為頂點(diǎn)集所組成的子圖，稱(chēng)

19、為G 的由邊集 E 導(dǎo)出的子圖，簡(jiǎn)稱(chēng)為 G 的邊導(dǎo)出子圖，記為 GE。(5) 定義G - V (6) 定義G - E (7) 基礎(chǔ)簡(jiǎn)單圖：壓縮平行邊，去掉環(huán)基礎(chǔ)簡(jiǎn)單圖第41頁(yè)，共101頁(yè)。例6第42頁(yè)，共101頁(yè)。v2v5v3v4v1Ge1e8e7e6e5e4e3e2v2v3v4v1e1e8e6e5e4v2v5v4v1e1e7e3e2v2v5v4e7e6e5e3v2v5v3v4v1e1e7e6e4e3例7第43頁(yè)，共101頁(yè)。子圖的運(yùn)算：第44頁(yè)，共101頁(yè)。G2G1G2G1圖的運(yùn)算：第45頁(yè)，共101頁(yè)。G2G1第46頁(yè)，共101頁(yè)。1.4 頂點(diǎn)的度頂點(diǎn)v 的度(degree)：d(v) =

20、 頂點(diǎn)v 所關(guān)聯(lián)的邊的數(shù)目（環(huán)邊計(jì)兩次）。圖G 的最大度： (G) = maxd G (v) | v V (G)圖G 的最小度： (G) = mind G (v) | v V (G)正則圖(regular graph)：每個(gè)頂點(diǎn)的度都相等的圖。度序列：見(jiàn)習(xí)題1.5.5孤立點(diǎn)： d(v) =0 第47頁(yè)，共101頁(yè)。定理 1.1證明：按每個(gè)頂點(diǎn)的度來(lái)計(jì)數(shù)邊，每條邊恰數(shù)了兩次。推論1.1 任何圖中，奇度頂點(diǎn)的個(gè)數(shù)總是偶數(shù)（包括0）。設(shè)V1 和 V2 分別是G中奇點(diǎn)集和偶點(diǎn)集，由證明：而 是偶數(shù)，所以 是偶數(shù)，故 是偶數(shù)。定理1.1知，是偶數(shù)，第48頁(yè)，共101頁(yè)。例 晚會(huì)上大家握手言歡，試證握過(guò)奇

21、次手的人數(shù)是偶數(shù)。證明：以參加晚會(huì)的人為頂點(diǎn)集構(gòu)造一個(gè)圖G，當(dāng)且僅當(dāng)二人握手時(shí)，在相應(yīng)的兩頂點(diǎn)之間連一條邊。于是每人握手的次數(shù)即為G的相應(yīng)頂點(diǎn)的度數(shù)。由推論1.1，得證。第49頁(yè)，共101頁(yè)。例 空間中不可能有這樣的多面體存在，它的面數(shù)是奇數(shù)，而且每個(gè)面由奇數(shù)條線段圍成證明：如果有這樣的多面體，以此多面體的面集合為頂點(diǎn)集構(gòu)造一個(gè)圖G，當(dāng)且僅當(dāng)兩個(gè)面有公共邊界時(shí)，在相應(yīng)的兩頂點(diǎn)之間連一條邊。于是G有奇數(shù)個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)都為奇點(diǎn)，與定理1.1矛盾。故這種多面體不存在。第50頁(yè)，共101頁(yè)。1.5 路、圈和連通(1) 途徑(walk)：圖G 中一個(gè)頂點(diǎn)和邊交替出現(xiàn)的有限非 空序列注1：起點(diǎn)(v0)

22、；終點(diǎn)(vk) ；內(nèi)部頂點(diǎn)（內(nèi)點(diǎn)）；長(zhǎng)(k)注2：簡(jiǎn)單圖中的途徑可以用頂點(diǎn)來(lái)表示若在非簡(jiǎn)單圖中，則表示通過(guò)這些頂點(diǎn)的任意途徑。注3： W-1； W1W2; 注4： W的(vi,vj)節(jié)路和圈有關(guān)概念第51頁(yè)，共101頁(yè)。(2) 跡(trail)：各邊相異的途徑。(3) 路(path): 各頂點(diǎn)相異的跡（P_k)。第52頁(yè)，共101頁(yè)。(4) 閉途徑(closed walk)：具有正的長(zhǎng)且起點(diǎn)和終點(diǎn)相同的途徑。 閉跡(closed trail) 也稱(chēng)為回路（circuit）。(5) 圈(cycle): 各頂點(diǎn)相異的閉跡。 k圈（C_k)；3圈常稱(chēng)為三角形 圖G 中長(zhǎng)為奇數(shù)和偶數(shù)的圈分別稱(chēng)為奇圈(

23、odd cycle)和偶圈(even cycle)。 圖G 的圍長(zhǎng)(girth) 是指G 中最短圈的長(zhǎng)；若G沒(méi)有圈，則定義為無(wú)窮大。 最長(zhǎng)圈的長(zhǎng)稱(chēng)為圖G 的周長(zhǎng)(circumference)。第53頁(yè)，共101頁(yè)。v2v5v3v4v1Ge1e8e7e6e5e4e3e2途徑長(zhǎng)為 5。長(zhǎng)為 5。跡 長(zhǎng)為 3。試著尋找其它的 (v1, v3)-路?路例8第54頁(yè)，共101頁(yè)。圖 K4, E3, P4, C4 and C5 第55頁(yè)，共101頁(yè)。圖的分支（component）：若圖G 的頂點(diǎn)集V(G)可劃分為若干非空子集V 1,V 2, ,V ，使得兩頂點(diǎn)屬于同一子集當(dāng)且僅當(dāng)它們?cè)贕 中連通，則稱(chēng)每個(gè)

24、子圖GV i 為圖G 的一個(gè)分支（ i = 1,2, ）。連通性的概念圖中兩點(diǎn)的連通：如果在圖G 中存在(u，v) 路，則稱(chēng)頂點(diǎn)u，v 在圖G 中連通。連通圖（connected graph）：圖G 中任二頂點(diǎn)都連通。第56頁(yè)，共101頁(yè)。 非連通圖，三個(gè)分支v1v2v3v4e2e3e4e5e6e7 連通圖注：（1）圖G 的分支是G 的一個(gè)極大連通子圖。 （2）圖G 連通當(dāng)且僅當(dāng)1。第57頁(yè)，共101頁(yè)。有四個(gè)分支的不連通圖例第58頁(yè)，共101頁(yè)。注：（1）若在G中頂點(diǎn) x 和 y 是連通的 ，則 x 和 y 之間 的距離(distance) d G(x, y) 是G 中最短 (x, y) 路

25、的長(zhǎng)；若沒(méi)有路連接 x 和 y，則定義d G(x, y)為無(wú)窮大。（2）圖G 的直徑(diameter): D = maxd G (x, y) | x, y V (G) 。第59頁(yè)，共101頁(yè)。定理1.2 一個(gè)圖是二部圖當(dāng)且僅當(dāng)它不含奇圈。證明： 必要性：設(shè) C = v 0 v 1 v k v 0 是二部圖G = (X U Y , E) 的一個(gè)圈。不妨設(shè)v 0 X ，由二部圖的定義知v 1 Y ，v 2 X ， ，一般地，v 2 i X ，v 2 i +1 Y ，（ i = 0,1,）。又因v 0 X ，故v k Y ，因而k 是奇數(shù)。注意到圈C 上共有k + 1條邊，因此是偶圈。偶圖的判定條

26、件第60頁(yè)，共101頁(yè)。充分性：顯然對(duì)連通圖證明即可。設(shè)G 不含奇圈。任取 u V (G) ，令X = v V (G) | d(u, v)是奇數(shù)，Y = v V (G) | d(u, v)是偶數(shù)?，F(xiàn)證（X,Y）是G的一個(gè)二分類(lèi)。任取一條邊 e = v1v2，欲證, v1 ，v2分屬于X 和Y。 設(shè)P，Q 分別是u 到 v1 ，v2 的最短路。Puv1v2（1）如果 P = Q + v 2 v 1或 Q = P + v 1 v 2 ，則 v 1, v 2到u 的距離奇偶性相反， v 1 , v 2分屬于X和Y。第61頁(yè)，共101頁(yè)。 假如P，Q 的奇偶性相同，則P 的(u , v 1 ) 節(jié)和Q

27、 的(u , v 2 ) 節(jié)奇偶性相同，它們與邊e 構(gòu)成一個(gè)奇圈，與定理?xiàng)l件矛盾?？梢?jiàn)P，Q 的奇偶性不同，從而 v 1, v 2分屬于X 和Y。證畢。（2）否則，設(shè)u是P 與Q 的最后一個(gè)公共頂點(diǎn)，因P 的(u, u) 節(jié)和Q 的(u, u) 節(jié)都是最短的(u,u) 路，故長(zhǎng)相等。Puuv1Qv2Puv1Puv1Puv1Puv1Puv1v1第62頁(yè)，共101頁(yè)。由定理 1.2可知圖 (a) 所示的圖不是二部圖，因?yàn)樗粋€(gè)三角形；圖 (b) 所示的圖是一個(gè)二部圖，它不含長(zhǎng)為奇數(shù)的圈。第63頁(yè)，共101頁(yè)。證明：設(shè)P = v0v1 v k 為G 中的一條最長(zhǎng)路 。因 d (v 0) 2 ，故

28、除 v 1外，存在頂點(diǎn) v 與 v 0相鄰。若v V(P) ，則得到比 P 更長(zhǎng)的路，這與 P 的取法矛盾。因此必有 v V(P) ，從而 G 包含圈。證畢。例9 設(shè)G 是一個(gè)簡(jiǎn)單圖，若 (G) 2 ，則G 包含圈。v0v1v2vk第64頁(yè)，共101頁(yè)。例10 設(shè) G 是簡(jiǎn)單圖，若 (G) 3 ，則 G 包含偶圈。v0v1v2vkvivj第65頁(yè)，共101頁(yè)。證明：設(shè) P =v0v1 v k 是G 的最長(zhǎng)路。因?yàn)?d (v 0) 3 ， 所以存在兩個(gè)與 v 1 相異的頂點(diǎn) v, v 與 v 0 相鄰。v, v 必都在路 P 上，否則會(huì)得到比 P 更長(zhǎng)的路。不妨設(shè) v = v i , v = v

29、 j , (i 0。（w = 0時(shí)，可令兩端點(diǎn)重合；第81頁(yè)，共101頁(yè)。 若路 P = u 0 u 1 u k 1 u k 是從 u 0到 u k的最短路，則 P = u 0 u 1 u k 1必 u 0到u k 1的最短路?；谶@一原理，算法由近及遠(yuǎn)地逐次求出u 0到其它各點(diǎn)的最短路。二、Dijkstra 算法1. 算法思想下面通過(guò)例子說(shuō)明具體做法。第82頁(yè)，共101頁(yè)。（1）令 ， ，求 到 中最近點(diǎn)的最短路，結(jié)果找到 。（2）令: ，求 到 中最近點(diǎn)的最短路。此時(shí)除了考慮 到 的直接連邊外，還要考慮 通過(guò) 向 的連邊，即選取 中第83頁(yè)，共101頁(yè)。一點(diǎn) ，使得結(jié)果找到u 2 。一般地

30、，若 以及相應(yīng)的最短路已找到。則可應(yīng)用(*)式來(lái)選取新的 ，獲得 到 的最短路。第84頁(yè)，共101頁(yè)。例1472122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u0195第85頁(yè)，共101頁(yè)。 1) 置 ，對(duì) ， ， 且 . 2) 對(duì)每個(gè) ，用代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為 ，置 3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).

31、2算法實(shí)現(xiàn)標(biāo)號(hào)法第86頁(yè)，共101頁(yè)。計(jì)算實(shí)例：求連接 vs、vt 的最短路.開(kāi)始，給vs以 P 標(biāo)號(hào)，P(vs)=0,其余各點(diǎn)給 T 標(biāo)號(hào) T(vi)=+.227414731555vsv2v1vtv4v5v3Step 1: 迭代 1 Dijkstra算法基本步驟：例15第87頁(yè)，共101頁(yè)。 若 vi 為剛得到 P 標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn) vj : (vi ,vj)E 且vj 為 T 標(biāo)號(hào)。227414731555vsv2v1vtv4v5v3Step 2: 對(duì)vj的T 標(biāo)號(hào)進(jìn)行如下更改T(vj)=minT(vj),P(vi)+wij245迭代 1 考察vs , T(v2)=minT(v2),

32、P(vs)+ws2= min+,0+5=5T(v1)=minT(v1),P(vs)+ws1= min+,0+2=2第88頁(yè)，共101頁(yè)。 比較所有具有 T 標(biāo)號(hào)的點(diǎn)，把最小者改為P 標(biāo)號(hào)，227414731555vsv2v1vtv4v5v3Step 3: 245即 P(vi)=minT(vi).當(dāng)存在兩個(gè)以上最小者時(shí),可同時(shí)改為P 標(biāo)號(hào)。若全部點(diǎn)為P標(biāo)號(hào),則停止。否則用vi代替vi轉(zhuǎn)step 2.-2迭代 1 全部T標(biāo)號(hào)中,T(v1)最小,令P(v1)=2,記錄路徑(vs ,v1).第89頁(yè)，共101頁(yè)。227414731555vsv2v1vtv4v5v394 若 vi 為剛得到 P 標(biāo)號(hào)的點(diǎn)

33、,考慮這樣的點(diǎn) vj : (vi ,vj)E 且vj 為 T 標(biāo)號(hào)。Step 2: 對(duì)vj的T 標(biāo)號(hào)進(jìn)行如下更改T(vj)=minT(vj),P(vi)+wij迭代 2 考察v1 , T(v4)=minT(v4),P(v1)+w14= min+,2+7=9T(v2)=minT(v2),P(v1)+w12= min5,2+2=4第90頁(yè)，共101頁(yè)。227414731555vsv2v1vtv4v5v344迭代 2 比較所有具有 T 標(biāo)號(hào)的點(diǎn)，把最小者改為P 標(biāo)號(hào)，Step 3: 即 P(vi)=minT(vi).-全部 T 標(biāo)號(hào)中,T(v2),T(v3)最小,令P(v2)=4, P(v3)=4,記錄路徑(v1 ,v2