《圖論的介紹》PPT課件.ppt

1、圖論的介紹,哥尼斯堡七橋問題(Bridges of Koenigsberg),能不能走過每一個橋剛好一次并且回到原來的地方？,歐拉路徑解決哥尼斯保七橋問題,原來是一筆畫問題?。?數(shù)學(xué)家歐拉(Euler, 1707-1783) 于1736年嚴(yán)格的證明了上述哥尼斯堡七橋問題無解，并且由此開創(chuàng)了圖論的典型思維方式及論證方式,實(shí)際生活中的圖論Graph Model,電路模擬,例：Pspice、Cadence、ADS.,Pspice,Cadence,交通網(wǎng)絡(luò),航空網(wǎng)絡(luò)!,捷運(yùn)路線圖！,網(wǎng)絡(luò)架構(gòu)圖,計算機(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)頁包含到其他網(wǎng)頁的超鏈接。整個Web是一個圖. 搜索引擎需要圖處理算法。 Matching 職位招聘，如何有效將職位與應(yīng)聘者匹配？ Schedules 工程項目的任務(wù)安排，如何滿足限制條件，并在最短時間內(nèi)完成？ Program structure 大型軟件系統(tǒng)，函數(shù)（模塊）之間調(diào)用關(guān)系。編譯器分析調(diào)用關(guān)系圖確定如何最好分配資源才能使程序更有效率。,Graph Applications,Graph Problems and Algorithms,哈密頓（Hamilton）周遊世界問題,哈密頓路徑至今尚無有效方法來解決！,

4、正十二面體有二十個頂點(diǎn) 表示世界上20個城市 各經(jīng)每個城市一次 最后返回原地,投影至平面,最短路徑問題 (Shortest Path Problem),最快航線,最快的routing,最短路徑算法Dijkstra算法,可以求出從某一點(diǎn)到圖上其他任一點(diǎn)的最短路徑,走迷宮與深度優(yōu)先搜索(Depth-First Search),老鼠走迷宮深度優(yōu)先搜索,一直往前走 碰壁就回頭換條路找 沿途要記錄下走過的路線,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、語,什么是圖？,一堆頂點(diǎn)和邊的組合！ Set of vertices connected pairwise by edges.,例一 例二,圖論的術(shù)語,頂點(diǎn) (Vertex) 邊 (Edge) 一個圖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),再來一些術(shù)語,連通圖 (connected graph) 子圖(subgraph) 樹(tree)沒有回路的連通圖 森林 (forest) 一堆樹的集合,樹的實(shí)例 行政組織圖,有向圖(Digraph),有向圖 (D

8、igraph),有向且無簡單回路的圖 (directed acyclic graph),加權(quán)圖(Weighted Graph),生成樹(Spanning Tree),生成樹,包括圖中所有的頂點(diǎn)，并且是一棵樹,可運(yùn)用生成樹的實(shí)例,Graph Terminology,一些特殊的圖,完全圖 Complete graphs,任意兩點(diǎn)之間都有一條邊與其相連的圖稱為完全圖，以Kn 來表示，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個頂點(diǎn)(V=8) 12條邊 (E=12) 6個面 (F=6) 8-12+6=2,更多平面圖實(shí)例,樹 Trees,樹(tree):連通無簡單回路無向圖 若有n個頂點(diǎn)，則有n-1條邊 任兩點(diǎn)之間僅有一條路徑 生成樹 (spanning tree):包括圖中所有的頂點(diǎn)，并且是一棵樹,A connected graph G,Spanning trees of G,tree,圖術(shù)語回顧,點(diǎn)：研究對象（陸地、路口、國家、球隊）；,點(diǎn)間連線：對象之間的特定關(guān)系（陸地間有橋、路口 之間道路、兩國邊界、兩球隊比賽及結(jié)果)。,對稱關(guān)系：橋、道路、邊界；

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

12、為無限圖。,無向圖：由點(diǎn)及邊構(gòu)成 ，邊vi，vj,有向圖：由點(diǎn)及弧構(gòu)成，弧（ vi，vj）,圖G中點(diǎn)集V的頂點(diǎn)個數(shù)，記為p (G) ； 邊數(shù)記為q(G), 簡記 p，q。,1. 簡單圖與多重圖,某條邊兩個端點(diǎn)相同，稱這條邊為環(huán)。 若兩點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。,無環(huán)、無多重邊的圖稱為簡單圖。,多重圖：無環(huán)、但允許有多重邊。,二、圖論中常用術(shù)語,2. 相鄰與關(guān)聯(lián),若邊e=u，vE，稱u，v是e的端點(diǎn)，也稱u，v是相鄰的。稱e是點(diǎn)u（及點(diǎn)v）的關(guān)聯(lián)邊。,若兩條邊有一個公共的端點(diǎn)，則稱這兩條邊相鄰接。,點(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)稱為奇點(diǎn)，否則稱為偶點(diǎn)。,定理2 任一圖中奇點(diǎn)的個數(shù)為偶數(shù)。,證明：設(shè)v0和v e分別是G中的奇點(diǎn)和偶點(diǎn)的集合，由定理1，有,因 是偶數(shù)， 也是偶數(shù)，故 必為偶數(shù)。即在一個圖中奇點(diǎn)的個數(shù)必為偶數(shù)。,4. 節(jié)點(diǎn)度與懸掛點(diǎn)、孤立點(diǎn),圖G中以點(diǎn)v為端點(diǎn)的邊的數(shù)目，稱為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)邊稱為懸掛邊，度為零的點(diǎn)稱為孤立點(diǎn)。,5. 鏈與圈,給定一個圖G=（V，E），G中的一個點(diǎn)、邊交錯序列（vi1，ei1，vi2，ei2，vik-1，eik-1，

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

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

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

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

18、,1.鄰接矩陣,鄰接矩陣用于描述兩個頂點(diǎn)之間是否有邊（?。┫噙B。,對于有n個頂點(diǎn)的無向圖G=(V,E) ，定義鄰接矩陣(B=bij)nn 。其中，,對于有幾個頂點(diǎn)的有向圖G=(V,A) ，定義鄰接矩陣(B=bij)nn 。其中，,例題1 已知無向圖所示，求其鄰接矩陣。,則,顯然，無向圖的鄰接矩陣是關(guān)于對角線的對稱矩陣。,例 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為無向圖時，鄰接矩陣為對稱矩陣。,在有向圖中可達(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)矩陣也稱頂點(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ò)矩陣表示法。對于有n個頂點(diǎn)的無向網(wǎng)絡(luò)G=(V,E,W) ,邊 vi,vj的權(quán)為wij ，則權(quán)矩陣D=(dij)nn ，其中：,4. 權(quán)矩陣,對于有n個頂點(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、,最 短 路 問 題 及 其 算 法,固 定 起 點(diǎn) 的 最 短 路,最短路是一條路徑，且最短路的任一段也是最短路,假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹,因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路,算法步驟：,u1,u2,u3,u4,u5,u6,u7,u8,一、 可化為最短路問題的多階段決策問題,二、 選 址 問 題,1、 中心問題,2、 重心問題,可化為最短路問題的多階段決策問題,選址問題-中心問題,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處。,選址問題-重心問題,還有哪些選址問題？,消防隊 汽車急救中心 警車配置和巡邏問題 （2009研究生數(shù)學(xué)建模競賽試題）,警車配置和巡邏問題,110警車在街道上巡弋，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的安全感，同時也加快了接處警（接受報警并趕往現(xiàn)場處理事件）時間，提高了反應(yīng)時效，為社會和諧提供了有力的保障。 該問題考慮到某城市內(nèi)一區(qū)域，并假定所有事發(fā)現(xiàn)場均在下圖的道路上。下圖紅點(diǎn)部位為重點(diǎn)部位，該區(qū)域內(nèi)三個重點(diǎn)部位的坐標(biāo)分別為：（5112，4806），（9126，4266），（7434，1332），藍(lán)色部分為水域，相鄰兩個交叉

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

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

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

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

27、,Cc,Dd. 用標(biāo)記 法從點(diǎn)A開始求得一條交替鏈:=(AcCe)(左圖). 用調(diào)整匹配M:將中屬于M的邊刪去并將其中不屬于M的其它邊添加到M中得到比M多一邊的新匹配M(如右圖示). 因?qū)用標(biāo)記法只能從E或F開始,但都不能求出M的任何交替鏈,故判定M是一個最大匹配.,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,樹的概念,樹是應(yīng)用中特別重要的特殊圖,分無向樹和有向樹兩種. 定義 無回路的無向連通圖稱為無向樹.也可以說,無基本回路的無向連通圖稱為無向樹,因?yàn)?無回路等價于無基本

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

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

30、G也無回路. 再證G加任一邊e=(vi,vj)得唯一回路.G連通性保證有vi-vj路,從而G+e有回路.因刪去兩條回路中的任一邊仍有回路留下,故G+e不會有兩條回路(否則G有回路).,證 :要證若G無回路且加一邊得唯一回路,則G連通且刪去一邊不連通.用反證法,因G是森林,若G不連通,則在G的二連通分支的點(diǎn)間加邊不會得新回路,故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是樹.任2

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

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