1、圖論的介紹,哥尼斯堡七橋問(wèn)題(Bridges of Koenigsberg),能不能走過(guò)每一個(gè)橋剛好一次并且回到原來(lái)的地方？,歐拉路徑解決哥尼斯保七橋問(wèn)題,原來(lái)是一筆畫(huà)問(wèn)題啊！,數(shù)學(xué)家歐拉(Euler, 1707-1783) 于1736年嚴(yán)格的證明了上述哥尼斯堡七橋問(wèn)題無(wú)解，并且由此開(kāi)創(chuàng)了圖論的典型思維方式及論證方式,實(shí)際生活中的圖論Graph Model,電路模擬,例：Pspice、Cadence、ADS.,Pspice,Cadence,交通網(wǎng)絡(luò),航空網(wǎng)絡(luò)!,捷運(yùn)路線(xiàn)圖！,網(wǎng)絡(luò)架構(gòu)圖,計(jì)算機(jī)網(wǎng)絡(luò),有向圖,有單行道的街道！,行程表！,Social Network,High School Dat

2、ing,corporate e-mail,Reference: Bearman, Moody and Stovel, 2004 image by Mark Newman,Reference: Adamic and Adar, 2004,Protein interaction network,Reference: Jeong et al, Nature Review | Genetics,Power transmission grid of Western US,The Internet,The Internet as mapped by The Opte Project http:/www.o

3、,More Applications,Hypertexts 網(wǎng)頁(yè)包含到其他網(wǎng)頁(yè)的超鏈接。整個(gè)Web是一個(gè)圖. 搜索引擎需要圖處理算法。 Matching 職位招聘，如何有效將職位與應(yīng)聘者匹配？ Schedules 工程項(xiàng)目的任務(wù)安排，如何滿(mǎn)足限制條件，并在最短時(shí)間內(nèi)完成？ Program structure 大型軟件系統(tǒng)，函數(shù)（模塊）之間調(diào)用關(guān)系。編譯器分析調(diào)用關(guān)系圖確定如何最好分配資源才能使程序更有效率。,Graph Applications,Graph Problems and Algorithms,哈密頓（Hamilton）周遊世界問(wèn)題,哈密頓路徑至今尚無(wú)有效方法來(lái)解決！,

4、正十二面體有二十個(gè)頂點(diǎn) 表示世界上20個(gè)城市 各經(jīng)每個(gè)城市一次 最后返回原地,投影至平面,最短路徑問(wèn)題 (Shortest Path Problem),最快航線(xiàn),最快的routing,最短路徑算法Dijkstra算法,可以求出從某一點(diǎn)到圖上其他任一點(diǎn)的最短路徑,走迷宮與深度優(yōu)先搜索(Depth-First Search),老鼠走迷宮深度優(yōu)先搜索,一直往前走 碰壁就回頭換條路找 沿途要記錄下走過(guò)的路線(xiàn),Some graph-processing problems,Path. Is there a path between s to t? Shortest path. What is the sh

5、ortest path between s and t? Longest path. What is the longest simple path between s and t? Cycle. Is there a cycle in the graph? Euler tour. Is there a cycle that uses each edge exactly once? Hamilton tour. Is there a cycle that uses each vertex exactly once? Connectivity. Is there a way to connect

6、 all of the vertices? MST. What is the best way to connect all of the vertices? Biconnectivity. Is there a vertex whose removal disconnects the graph? Planarity. Can you draw the graph in the plane with no crossing edges? First challenge: Which of these problems is easy? difficult? intractable?,圖論的術(shù)

7、語(yǔ),什么是圖？,一堆頂點(diǎn)和邊的組合！ Set of vertices connected pairwise by edges.,例一 例二,圖論的術(shù)語(yǔ),頂點(diǎn) (Vertex) 邊 (Edge) 一個(gè)圖G = (V,E) V: 頂點(diǎn)的集合 E: 邊的集合 例：如右圖 V= a,b,c,d,e E= (a,b),(a,c),(a,d), (b,e),(c,d),(c,e), (d,e),再來(lái)一些術(shù)語(yǔ),連通圖 (connected graph) 子圖(subgraph) 樹(shù)(tree)沒(méi)有回路的連通圖 森林 (forest) 一堆樹(shù)的集合,樹(shù)的實(shí)例 行政組織圖,有向圖(Digraph),有向圖 (D

8、igraph),有向且無(wú)簡(jiǎn)單回路的圖 (directed acyclic graph),加權(quán)圖(Weighted Graph),生成樹(shù)(Spanning Tree),生成樹(shù),包括圖中所有的頂點(diǎn)，并且是一棵樹(shù),可運(yùn)用生成樹(shù)的實(shí)例,Graph Terminology,一些特殊的圖,完全圖 Complete graphs,任意兩點(diǎn)之間都有一條邊與其相連的圖稱(chēng)為完全圖，以Kn 來(lái)表示，n為頂點(diǎn)數(shù),二分圖（偶圖） Bipartite graphs,A graph that can be decomposed into two partite sets but not fewer is bipartite

9、 It is a complete bipartite if its vertices can be divided into two non-empty groups, A and B. Each vertex in A is connected to B, and vice-versa,Complete bipartite graph K2,3,The graph is bipartite,平面圖 Planar graphs,A planar graph is a graph that can be embedded in a plane so that no edges intersec

10、t,Planar:,=,NOT Planar:,平面圖實(shí)例,8個(gè)頂點(diǎn)(V=8) 12條邊 (E=12) 6個(gè)面 (F=6) 8-12+6=2,更多平面圖實(shí)例,樹(shù) Trees,樹(shù)(tree):連通無(wú)簡(jiǎn)單回路無(wú)向圖 若有n個(gè)頂點(diǎn)，則有n-1條邊 任兩點(diǎn)之間僅有一條路徑 生成樹(shù) (spanning tree):包括圖中所有的頂點(diǎn)，并且是一棵樹(shù),A connected graph G,Spanning trees of G,tree,圖術(shù)語(yǔ)回顧,點(diǎn)：研究對(duì)象（陸地、路口、國(guó)家、球隊(duì)）；,點(diǎn)間連線(xiàn)：對(duì)象之間的特定關(guān)系（陸地間有橋、路口 之間道路、兩國(guó)邊界、兩球隊(duì)比賽及結(jié)果)。,對(duì)稱(chēng)關(guān)系：橋、道路、邊界；

11、,用不帶箭頭的連線(xiàn)表示，稱(chēng)為邊。,非對(duì)稱(chēng)關(guān)系：甲隊(duì)勝乙隊(duì)，用帶箭頭的連線(xiàn)表示， 稱(chēng)為弧。,圖：點(diǎn)及邊（或弧）組成。,例：有甲、乙、丙、丁、戊五個(gè)球隊(duì)，各隊(duì)之間比賽 情況如表：,點(diǎn)：球隊(duì)； 連線(xiàn)：兩個(gè)球隊(duì)之間比賽過(guò)，如甲勝乙，用 v1 v2表示。,圖的定義,定義1：一個(gè)圖，是由非空集合V(G)=vi 和V(G)中 元素的有序?qū)Γɑ驘o(wú)序?qū)Γ┑募螮(G)=ek 所組成的二元組（V(G)，E(G)）所構(gòu)成。 記為 G= （ V(G)， E(G) ）,簡(jiǎn)記 G= （V，E）,其中 V= vi 稱(chēng)為點(diǎn)集，vi為點(diǎn) 。 E=ek稱(chēng)為邊集， ek為邊（或?。?。,當(dāng)V，E為有限集時(shí)，稱(chēng)G為有限圖。 否則，稱(chēng)G

12、為無(wú)限圖。,無(wú)向圖：由點(diǎn)及邊構(gòu)成 ，邊vi，vj,有向圖：由點(diǎn)及弧構(gòu)成，弧（ vi，vj）,圖G中點(diǎn)集V的頂點(diǎn)個(gè)數(shù)，記為p (G) ； 邊數(shù)記為q(G), 簡(jiǎn)記 p，q。,1. 簡(jiǎn)單圖與多重圖,某條邊兩個(gè)端點(diǎn)相同，稱(chēng)這條邊為環(huán)。 若兩點(diǎn)之間有多于一條的邊，稱(chēng)這些邊為多重邊。,無(wú)環(huán)、無(wú)多重邊的圖稱(chēng)為簡(jiǎn)單圖。,多重圖：無(wú)環(huán)、但允許有多重邊。,二、圖論中常用術(shù)語(yǔ),2. 相鄰與關(guān)聯(lián),若邊e=u，vE，稱(chēng)u，v是e的端點(diǎn)，也稱(chēng)u，v是相鄰的。稱(chēng)e是點(diǎn)u（及點(diǎn)v）的關(guān)聯(lián)邊。,若兩條邊有一個(gè)公共的端點(diǎn)，則稱(chēng)這兩條邊相鄰接。,點(diǎn)與邊關(guān)聯(lián),點(diǎn)與點(diǎn)相鄰,邊與邊相鄰接,定理1 圖G=（V，E）中，所有點(diǎn)的次之和為邊

13、數(shù) 的兩倍， 即,3. 奇點(diǎn)與偶點(diǎn),次為奇數(shù)的點(diǎn)稱(chēng)為奇點(diǎn)，否則稱(chēng)為偶點(diǎn)。,定理2 任一圖中奇點(diǎn)的個(gè)數(shù)為偶數(shù)。,證明：設(shè)v0和v e分別是G中的奇點(diǎn)和偶點(diǎn)的集合，由定理1，有,因 是偶數(shù)， 也是偶數(shù)，故 必為偶數(shù)。即在一個(gè)圖中奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。,4. 節(jié)點(diǎn)度與懸掛點(diǎn)、孤立點(diǎn),圖G中以點(diǎn)v為端點(diǎn)的邊的數(shù)目，稱(chēng)為v在G中的度， 記為d（v）。,d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1,度為1 的點(diǎn)為懸掛點(diǎn)，懸掛點(diǎn)的關(guān)聯(lián)邊稱(chēng)為懸掛邊，度為零的點(diǎn)稱(chēng)為孤立點(diǎn)。,5. 鏈與圈,給定一個(gè)圖G=（V，E），G中的一個(gè)點(diǎn)、邊交錯(cuò)序列（vi1，ei1，vi2，ei2，vik-1，eik-1，

14、vik），如果滿(mǎn)足eit=vit，vit+1（t=1，2，k-1），則稱(chēng)為一條聯(lián)接vi1和vik的鏈，記為=（vi1，vi2，vik）。,鏈（vi1，vi2，vik）中，若vi1=vik ，稱(chēng)之為一個(gè)圈，記為C= （vi1，vi2，vik-1， vi1 ） 。,初等鏈：鏈中點(diǎn)都不同。 簡(jiǎn)單鏈：鏈中邊都不同。,（邊能否相同？）,（點(diǎn)能否相同？）,簡(jiǎn)單鏈：1=（v2，v1，v3，v6，v4，v3，v5）,初等鏈：2=（v2，v1，v3，v5）,簡(jiǎn)單圈：C1=（v1，v2，v4，v3，v5，v6，v3 ，v1 ）,初等圈：C2=（v1，v2，v4，v6，v5，v3 ，v1 ）,有向圖中，不考慮弧的方

15、向，有類(lèi)似鏈（圈）的定義。當(dāng)鏈（圈）上弧的方向一致時(shí)，稱(chēng)為路（回路）。,3. 連通圖,給定圖G=（V，E），任何兩點(diǎn)間至少有一條鏈，則稱(chēng)G是連通圖，否則為不連通圖。,若G是不連通的，它的每個(gè)連通部分稱(chēng)為G的連通分圖。,一些特殊圖類(lèi),1. 平凡圖 節(jié)點(diǎn)數(shù)n=1,邊數(shù)m=0的圖。,2. 零圖 邊數(shù)m=0的圖。,5. 完備圖,無(wú)向圖的完備圖：任何兩點(diǎn)之間有一條邊；,有向圖的完備圖：任何兩點(diǎn)u與v之間有兩條有向邊（u，v）及（v，u）。,基本圖：把有向圖的每條邊除去方向得到的無(wú)向圖。,若V(G)=X Y,X Y= ，X 、Y中的任兩頂點(diǎn)不相鄰，則G稱(chēng)為二分圖，記為（S,X,Y）。,4.樹(shù) 無(wú)圈連通圖。

16、,6.二分圖,9.網(wǎng)絡(luò),若對(duì)圖G=（V，E）中每條邊vi，vj賦予一個(gè)數(shù)wij，則稱(chēng)wij為邊vi，vj的權(quán)，并稱(chēng)圖G為網(wǎng)絡(luò)（或賦權(quán)圖）。,網(wǎng)絡(luò)：無(wú)向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)。,7.完全二分圖 若V(G)=(S,X,Y),如果任意X、Y，都有，E，則稱(chēng)G是完全的二分圖。,8.正則圖 如果G中每個(gè)點(diǎn)的次數(shù)都相同，則G叫做正則圖。,1. 子圖與支撐子圖,定義2 給定圖G=（V，E），若圖G1=（V1，E1），其 中V1V，E1=uv|uvE，u，v v1，則稱(chēng)G1是G的子圖。,定義3 給定圖G=（V，E），若圖G1=（V，E1），其 中E1E，則稱(chēng)G1是G的一個(gè)支撐子圖。,點(diǎn)全部保留,支撐子圖,四 、圖的運(yùn)

17、算,2.圖的收縮運(yùn)算,設(shè)圖G=(V,E)，V1 V,在G中收縮V1是指在圖G中，在V1中的點(diǎn)重為一個(gè)點(diǎn)，G與V1中的點(diǎn)相關(guān)聯(lián)的邊變?yōu)榕c這個(gè)新點(diǎn)相關(guān)聯(lián)的邊，稱(chēng)這樣的圖為關(guān)于V1收縮。,3. 割集,給定圖G=（V，E），點(diǎn)的子集S V，T V，定義G中邊的集合S，TG=uv|u s，v T為一個(gè)割集。,若X=v1,若X=v1，v2，,4.圖的同構(gòu),定義4 設(shè)圖G=（V，E）與G1=（V1，E1），若它們的點(diǎn)之間存在一一對(duì)應(yīng)，并且保持同樣的相鄰關(guān)系，則稱(chēng)G與G1同構(gòu)。記為GG1。,(a),(b),圖(a)和(b)就為同構(gòu),五、圖的矩陣表示,圖的矩陣表示方法有：鄰接矩陣、關(guān)聯(lián)矩陣、可達(dá)矩陣、權(quán)矩陣等。

18、,1.鄰接矩陣,鄰接矩陣用于描述兩個(gè)頂點(diǎn)之間是否有邊（?。┫噙B。,對(duì)于有n個(gè)頂點(diǎn)的無(wú)向圖G=(V,E) ，定義鄰接矩陣(B=bij)nn 。其中，,對(duì)于有幾個(gè)頂點(diǎn)的有向圖G=(V,A) ，定義鄰接矩陣(B=bij)nn 。其中，,例題1 已知無(wú)向圖所示，求其鄰接矩陣。,則,顯然，無(wú)向圖的鄰接矩陣是關(guān)于對(duì)角線(xiàn)的對(duì)稱(chēng)矩陣。,例 2 已知：圖所示，求其鄰接矩陣。,則：,v1 v2 v3 v4 v5 v6 v1 0 1 1 0 0 0 v2 0 0 1 1 1 0 v3 0 0 0 1 0 0 v4 0 0 0 0 1 1 v5 0 0 1 0 0 1 v6 0 0 0 0 0 0,其鄰接矩陣為：,當(dāng)

19、G為無(wú)向圖時(shí)，鄰接矩陣為對(duì)稱(chēng)矩陣。,在有向圖中可達(dá)矩陣用于描述兩點(diǎn)之間是否有路相連,即R=(rij)nn , 其中，,2.可達(dá)矩陣,例題3 求例題2的可達(dá)矩陣,則,v1 v2 v3 v4 v5 v6 v1 1 1 1 1 1 1 v2 0 1 1 1 1 1 v3 0 0 1 1 1 1 v4 0 0 0 1 1 1 v5 0 0 0 0 1 1 v6 0 0 0 0 0 1,3. 關(guān)聯(lián)矩陣,有向圖的關(guān)聯(lián)矩陣也稱(chēng)頂點(diǎn)邊關(guān)聯(lián)矩陣。,設(shè)有向圖 G=(V,A)，其中rij=V=v1,v2,v3vn，則關(guān)聯(lián)矩陣可定義為 M=(mij)nm其中：,例題4 求下圖的關(guān)聯(lián)矩陣,則其關(guān)聯(lián)矩陣為：,a1 a2

20、a3 a4 a5 a6 v1 0 1 -1 0 0 -1 v2 1 0 1 1 0 0 v3 -1 -1 0 0 1 0 v4 0 0 0 -1 -1 1,權(quán)矩陣是最流行的一種網(wǎng)絡(luò)矩陣表示法。對(duì)于有n個(gè)頂點(diǎn)的無(wú)向網(wǎng)絡(luò)G=(V,E,W) ,邊 vi,vj的權(quán)為wij ，則權(quán)矩陣D=(dij)nn ，其中：,4. 權(quán)矩陣,對(duì)于有n個(gè)頂點(diǎn)的有向網(wǎng)絡(luò)G=(V,A,W) ,邊 vi,vj的權(quán)為wij ，則權(quán)矩陣D=(dij)nn ，其中：,例題5. 如圖所示，弧上的數(shù)字代表數(shù)， D=(dij)5 5。,0 35 43 19 0 85 18 43 0 11 0 16 77 0,其權(quán)矩陣為：,基 本 概 念

21、,最 短 路 問(wèn) 題 及 其 算 法,固 定 起 點(diǎn) 的 最 短 路,最短路是一條路徑，且最短路的任一段也是最短路,假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹(shù),因此, 可采用樹(shù)生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路,算法步驟：,u1,u2,u3,u4,u5,u6,u7,u8,一、 可化為最短路問(wèn)題的多階段決策問(wèn)題,二、 選 址 問(wèn) 題,1、 中心問(wèn)題,2、 重心問(wèn)題,可化為最短路問(wèn)題的多階段決策問(wèn)題,選址問(wèn)題-中心問(wèn)題,S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.

22、5,S(v3)=6,故應(yīng)將消防站設(shè)在v3處。,選址問(wèn)題-重心問(wèn)題,還有哪些選址問(wèn)題？,消防隊(duì) 汽車(chē)急救中心 警車(chē)配置和巡邏問(wèn)題 （2009研究生數(shù)學(xué)建模競(jìng)賽試題）,警車(chē)配置和巡邏問(wèn)題,110警車(chē)在街道上巡弋，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的安全感，同時(shí)也加快了接處警（接受報(bào)警并趕往現(xiàn)場(chǎng)處理事件）時(shí)間，提高了反應(yīng)時(shí)效，為社會(huì)和諧提供了有力的保障。 該問(wèn)題考慮到某城市內(nèi)一區(qū)域，并假定所有事發(fā)現(xiàn)場(chǎng)均在下圖的道路上。下圖紅點(diǎn)部位為重點(diǎn)部位，該區(qū)域內(nèi)三個(gè)重點(diǎn)部位的坐標(biāo)分別為：（5112，4806），（9126，4266），（7434，1332），藍(lán)色部分為水域，相鄰兩個(gè)交叉

23、路口之間的道路近似認(rèn)為是直線(xiàn)。,警車(chē)配置和巡邏問(wèn)題,警車(chē)配置和巡邏問(wèn)題,現(xiàn)在該城市擬增加一批配備有GPS衛(wèi)星定位系統(tǒng)及先進(jìn)通訊設(shè)備的110警車(chē)。假設(shè)110警車(chē)的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h。警車(chē)配置及巡邏方案則需要盡量滿(mǎn)足以下要求： D1. 警車(chē)在接警后三分鐘內(nèi)趕到現(xiàn)場(chǎng)的比例不低于90；而趕到重點(diǎn)部位的時(shí)間必須在兩分鐘之內(nèi)。 D2. 使巡邏效果更顯著。 D3. 警車(chē)巡邏規(guī)律應(yīng)有一定的隱蔽性。,警車(chē)配置和巡邏問(wèn)題,具體問(wèn)題如下： 一. 若要求滿(mǎn)足D1,該區(qū)最少需要配置多少輛警車(chē)巡邏？ 二. 請(qǐng)給出評(píng)價(jià)巡邏效果顯著程度的有關(guān)指標(biāo)。 三.請(qǐng)給出滿(mǎn)足D1且盡量滿(mǎn)足D2

24、條件的警車(chē)巡邏方案及其評(píng)價(jià)指標(biāo)值。 四. 在第三問(wèn)的基礎(chǔ)上，再考慮D3條件，給出你們的警車(chē)巡邏方案及其評(píng)價(jià)指 標(biāo)值。 五.如果該區(qū)域僅配置10輛警車(chē)，應(yīng)如何制定巡邏方案，使D1、D2盡量得到 滿(mǎn)足？ 六. 若警車(chē)接警后的平均行駛速度提高到50km/h，回答問(wèn)題三。 七. 你們認(rèn)為還有哪些因素、哪些情況需要考慮？給出你們相應(yīng)的解決方案。,警車(chē)配置和巡邏問(wèn)題,新問(wèn)題,單約束選路問(wèn)題？ 多約束選路問(wèn)題？ 多目標(biāo)選路問(wèn)題？ 多路徑選路問(wèn)題？ 區(qū)間最優(yōu)路徑？ ,匹配與最大匹配,定義:(二部)圖 G=X,E,Y 的邊集E的子集M稱(chēng)為G的一個(gè)匹配,如果M的任二邊都沒(méi)有公共端點(diǎn); G中邊數(shù)最多的匹配稱(chēng)為最大匹

25、配(不唯一);含有G的每一點(diǎn)的匹配稱(chēng)為完美匹配(必為最大匹配仍不唯一). 下面是最大,完美匹配的例子(用粗線(xiàn)表示):,工作分配問(wèn)題,問(wèn)題 某教研室有4位教師:A,B,C,D.A能教課程5;B能教1,2;C能教1,4;D能教課程3.能否適當(dāng)分配他們的任務(wù),使4位教師擔(dān)任4門(mén)不同課并且不發(fā)生安排教師教他不能教的課的情況? 此問(wèn)題可歸結(jié)為二部圖的數(shù)學(xué)模型: G=A,B,C,D,E,1,2,3,4,5,(X,y)E,如果X能教y.一個(gè)滿(mǎn)足要求的工作分配正是一個(gè)含有4條邊的一個(gè)最大匹配.,A,B,C,D,1,2,3,4,5,求圖G最大匹配的方法,首先 任取一個(gè)匹配(含一邊也可)M作為起點(diǎn).接著按下列方法

26、逐步調(diào)整當(dāng)前匹配(每一步使它調(diào)整為邊數(shù)多1的匹配)最后達(dá)到一個(gè)最大匹配: 步驟 在X中選定一個(gè)不屬于M的點(diǎn)xi標(biāo)記(*). 步驟 在X的新標(biāo)記的點(diǎn)中選一點(diǎn),如xi,用(xi) 標(biāo)記通過(guò)不屬于M的邊與xi鄰接并且尚未標(biāo)記的 點(diǎn)(如yi);在Y的新標(biāo)記的點(diǎn)中選一點(diǎn)(如yi),用 (yi)標(biāo)記通過(guò)M的邊與yi鄰接并且尚未標(biāo)記的點(diǎn); 照此繼續(xù),直到發(fā)現(xiàn)標(biāo)記到Y(jié)的一個(gè)點(diǎn),該點(diǎn)不與 X中任一邊相關(guān)聯(lián)或標(biāo)記不到任何這樣的點(diǎn)為止. 出現(xiàn)前一情況,便找到一條關(guān)于M的交替鏈(定義 8.4-4);利用它可調(diào)整M到一個(gè)比M多一邊的匹配; 出現(xiàn)后一情況便表示M已為最大匹配.,求最大匹配舉例,解: 取一個(gè)初始匹配M=Bb

27、,Cc,Dd. 用標(biāo)記 法從點(diǎn)A開(kāi)始求得一條交替鏈:=(AcCe)(左圖). 用調(diào)整匹配M:將中屬于M的邊刪去并將其中不屬于M的其它邊添加到M中得到比M多一邊的新匹配M(如右圖示). 因?qū)用標(biāo)記法只能從E或F開(kāi)始,但都不能求出M的任何交替鏈,故判定M是一個(gè)最大匹配.,A(c),B,C,D(d),a,b,c(D),d (E),e,E(*),F (*),f,A(*),B,C(c),D,a,b,c(A),d,e(C),E,F,f,M,樹(shù)的概念,樹(shù)是應(yīng)用中特別重要的特殊圖,分無(wú)向樹(shù)和有向樹(shù)兩種. 定義 無(wú)回路的無(wú)向連通圖稱(chēng)為無(wú)向樹(shù).也可以說(shuō),無(wú)基本回路的無(wú)向連通圖稱(chēng)為無(wú)向樹(shù),因?yàn)?無(wú)回路等價(jià)于無(wú)基本

28、回路. 連通分支全為無(wú)向樹(shù)的圖,即無(wú)回路的無(wú)向圖,稱(chēng)為森林. 樹(shù)的1度點(diǎn)稱(chēng)為樹(shù)葉,不是樹(shù)葉的點(diǎn)稱(chēng)為分枝點(diǎn). 例 圖8.6-1.,(n,m)無(wú)向線(xiàn)圖G是樹(shù)的5個(gè)等價(jià)條件,G是樹(shù)連通無(wú)回路.G無(wú)回路且m=n-1. G連通且m=n-1. G無(wú)回路且加一邊得唯 一回路. G連通且少一邊不連通. G任二點(diǎn)間有唯一(基本)路徑. 證 :2結(jié)點(diǎn)樹(shù)的邊數(shù)為1=2-1.假設(shè)k結(jié)點(diǎn)樹(shù)的邊數(shù)為k-1.要證k+1結(jié)點(diǎn)樹(shù)的邊數(shù)為k.事實(shí)上,樹(shù)G必有一樹(shù)葉w(否則G任一點(diǎn)的度都大于1,從任一點(diǎn)出發(fā)沿一邊進(jìn)入另一點(diǎn)恒可沿另一邊離開(kāi).因G的結(jié)點(diǎn)有限,故有限步以后一定要回到前面的點(diǎn),便與G無(wú)回路相矛盾). 子圖G-w顯然是樹(shù),

29、其點(diǎn)數(shù)是k,按歸納假設(shè)其邊數(shù)是k-1,從而G的邊數(shù)是k=(k+1)-1,歸納證明完成.,證 :要證若G無(wú)回路且m=n-1,則G連通.不然的話(huà),G有k(2)個(gè)無(wú)回路的連通分支(樹(shù)): T1,Tk,設(shè)Ti為(ni,mi)圖,則 m=m1+mk=(n1-1)+(nk-1)=(n1+nk)-kn-1矛盾. :要證若G連通且m=n-1,則G無(wú)回路且加一邊得唯一回路. 先對(duì)n用歸納法證明G無(wú)回路.n=2時(shí)顯然成立.設(shè)n=k時(shí)結(jié)論已成立并考慮n=k+1的情形.此時(shí)若G無(wú)1度點(diǎn),則2m2n 與m=n-1矛盾.故G必有1度點(diǎn)w.易見(jiàn)G-w連通且滿(mǎn)足條件(邊數(shù)比點(diǎn)數(shù)少1),由歸納假設(shè)G-w無(wú)回路.因w為1度點(diǎn),故

30、G也無(wú)回路. 再證G加任一邊e=(vi,vj)得唯一回路.G連通性保證有vi-vj路,從而G+e有回路.因刪去兩條回路中的任一邊仍有回路留下,故G+e不會(huì)有兩條回路(否則G有回路).,證 :要證若G無(wú)回路且加一邊得唯一回路,則G連通且刪去一邊不連通.用反證法,因G是森林,若G不連通,則在G的二連通分支的點(diǎn)間加邊不會(huì)得新回路,故G連通.若連通的G刪去一邊e還連通,便得出G=(G-e)e有回路的矛盾. :要證若G連通且刪去一邊不連通,則G任二點(diǎn)間有唯一路徑.事實(shí)上,G連通性保證任2點(diǎn)u,w間有路徑.若有兩條這樣的u-w路徑便與G刪去一邊不連通的假設(shè)矛盾. :要證若G任二點(diǎn)間有唯一路徑則G是樹(shù).任2

31、點(diǎn)都可達(dá)表示G連通.若G有回路,則G必有兩點(diǎn)其間有兩條路徑,與條件矛盾.,推論,由條件,樹(shù)是結(jié)點(diǎn)數(shù)固定下邊數(shù)最少的連通圖,并且 minm|(n,m)圖連通=n-1. 由條件,樹(shù)是結(jié)點(diǎn)數(shù)固定下邊數(shù)最多的無(wú)回路圖,并且 maxm|(n,m)圖無(wú)回路=n-1. 每棵樹(shù)至少有兩片樹(shù)葉(n2). 證:若不是這樣便有 d(v1)+d(vn)2(n-1)+12(n-1)=2m, 與d(v1)+d(vn)=2m的已知規(guī)律矛盾.,生成樹(shù)的概念,定義 無(wú)向圖G=V,E的生成子圖T是樹(shù),則稱(chēng)T是G的一棵生成樹(shù)(不唯一,圖8.6-2). 任何連通無(wú)向圖G至少有一棵生成樹(shù). 證(破圈法) 若G無(wú)簡(jiǎn)單回路,則G自己是一棵

32、生成樹(shù).否則,G有簡(jiǎn)單回路C1,刪去C1的一邊所得G的生成子圖記為G1.若G1無(wú)回路,則G1為生成樹(shù);否則G1有簡(jiǎn)單回路C2,刪去C2的一邊所得G1的生成子圖記為G2.若G2無(wú)回路,則G2為生成樹(shù);否則, 照此繼續(xù).易見(jiàn)經(jīng)m+1-n步必可找到G的一棵生成樹(shù). 推論 無(wú)向圖G連通當(dāng)且僅當(dāng)G有生成樹(shù).,最小生成樹(shù)的概念,定義 賦權(quán)簡(jiǎn)單連通無(wú)向圖G=V,E,W的子圖 H的權(quán)定義為 H 的所有邊的權(quán)和.G中權(quán)最小的生成樹(shù)稱(chēng)為最小生成樹(shù)(對(duì)普通簡(jiǎn)單連通圖不考慮最小生成樹(shù)). 最小生成樹(shù)有很強(qiáng)的應(yīng)用背景,例如:設(shè)計(jì)聯(lián)系若干城市的最短線(xiàn)路通信網(wǎng);設(shè)計(jì)供應(yīng)若干居民點(diǎn)的最短自來(lái)水管線(xiàn)路等.,求最小生成樹(shù)的Kruskal算法(避圈法),算法 將賦權(quán)簡(jiǎn)單連通無(wú)向圖G的邊排序:e1e2em.開(kāi)始時(shí) k:=1,A:=. 步驟 若Aek導(dǎo)出的子圖無(wú)回路,則 A:= Aek. 步驟 若|A|=n-1,算法結(jié)束;否則轉(zhuǎn)步驟. 例 對(duì)左邊無(wú)向圖用Kruskal算法求得右邊的最小生成樹(shù). 1 2 3 4 5 6 7 8 9 10 11