第08講 圖的基本概念及最小支撐樹問題

《第08講 圖的基本概念及最小支撐樹問題》由會員分享，可在線閱讀，更多相關(guān)《第08講 圖的基本概念及最小支撐樹問題（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、圖的基本概念及最小支撐樹問題 無向圖定義 無向圖G = , 其中(1) V 為頂點集，元素稱為頂點(2) E為VV 的多重集，其元素稱為無向邊，簡稱邊實例 設(shè) V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則 G = 為一無向圖相關(guān)定義1.鄰接：兩個點有公共邊，兩條邊有公共頂點；2.關(guān)聯(lián)：邊與其頂點；3.環(huán)：一條邊的兩個頂點重合；4.重邊：兩個點之間有多于一條邊；5.簡單圖：既無環(huán)也無重邊的圖；6.補圖：圖G的補圖定義為 ：與G有相同的頂點集， 中兩個點相鄰當且僅當它們在G中

2、不相鄰；7.二部分圖(二分圖)8.支撐子圖9.導出子圖10. 點度、通路、回路GG有向圖定義 有向圖D=, 只需注意E是VV 的多重子集圖2表示的是一個有向圖，試寫出它的V 和 E 注意：圖的數(shù)學定義與圖形表示，在同構(gòu)的意義下是一一對應(yīng)的網(wǎng)絡(luò)(帶權(quán)圖)對于圖G的每條邊e都賦予一個值w(e),稱為邊的權(quán)，則G連同邊上的權(quán)稱為一個網(wǎng)絡(luò)，記為G=(V,E,w)無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣（對圖無限制）定義 無向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej的關(guān)聯(lián)次數(shù)，稱(mij)nm為G 的關(guān)聯(lián)矩陣，記為M(G). 性質(zhì)：平行邊的列相同平行邊的列相同)4(2)3(),.,2 , 1

3、()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij jiijmjmjiijiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),()1(),()1()2(),.,2 , 1(0)1( 的的終終點點為為，不不關(guān)關(guān)聯(lián)聯(lián)與與，的的始始點點為為jijijiijevevevm10,1 定義定義 有向圖有向圖D=，則稱則稱 (mij)n m為為D的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記為，記為M(D). (4) 平行邊對應(yīng)的列相同平行邊對應(yīng)的列相同性質(zhì)性質(zhì)有向圖的關(guān)聯(lián)矩陣鄰接矩陣定義 設(shè)無向圖D=, V=v1, v2, , vn, E=e1, e2, , em

4、, 令cij為頂點 vi 和 vj 之間邊的條數(shù)，稱(cij)為D的鄰接矩陣，記作A(D)，或簡記為A. 定義 設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令cij為頂點 vi 鄰接到頂點 vj 邊的條數(shù)，稱(cij)為D (cij)的鄰接矩陣，記作A(D)，或簡記為A. 圖的連通性無向圖的連通性(1) 頂點之間的連通關(guān)系：G=為無向圖 若 vi 與 vj 之間有通路，則 vivj 是V上的等價關(guān)系 R=| u,v V且uv (2) G的連通性與連通分支 若u,vV，uv，則稱G連通 V/R=V1,V2,Vk，稱GV1, GV2, ,GVk為連通分 支，其個

5、數(shù) p(G)=k (k1)； k=1，G連通割集1. 刪除頂點及刪除邊 Gv 從G中將v及關(guān)聯(lián)的邊去掉 GV從G中刪除V中所有的頂點 Ge 將e從G中去掉 GE刪除E中所有邊 2. 點割集與邊割集 點割集與割點定義 G=, VV V為點割集p(GV)p(G)且有極小性 v為割點v為點割集定義 G=, EE E是邊割集p(GE)p(G)且有極小性 e是割邊（橋）e為邊割集無向樹定義(1) 無向樹連通無回路的無向圖(2) 平凡樹平凡圖(3) 森林至少由兩個連通分支（每個都是樹）組成(4) 樹葉1度頂點(5) 分支點度數(shù)2的頂點 樹的充要條件定理16.1 設(shè)G=是n階m條邊的無向圖，則下面各命題是等

6、價的：(1) G 是樹(2) G 中任意兩個頂點之間存在惟一的路徑.(3) G 中無回路且 m=n1. (4) G 是連通的且 m=n1.(5) G 是連通的且 G 中任何邊均為橋.(6) G 中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到惟一的一個含新邊的圈. 支撐樹定義：T為G的支撐子圖，且T為樹，稱T為G的支撐樹。定理：G有支撐樹當且僅當G為連通圖；12121212121200121212(,):,( ),(,)(,)( ).,( ):,(,)( )S SS SV GSSS SSSS SE GTGTGTTTeTTeT TS SS SGe且表示 與之間的邊的集合，且反樹：

7、設(shè) 為圖 的支撐樹，令稱為 的反樹。對于 的任意一條邊，不連通，設(shè)其兩個連通分支分別為它們所對應(yīng)的點集分別為，則構(gòu)成 的一個割集，記為。支撐樹 000,1( ):,TGTGTeTeTeGnGC eTe Te定理：設(shè) 是圖 的支撐樹，則不包含 的任何割集，但對中任一條邊存在唯一的割集，它包含在中?；靖罴簩τ?每條邊 都存在 的唯一割集，這樣的割集一共個，稱為 的基本割集。對于中每一條邊都包含唯一的回路.最小值支撐（生成）樹定義：網(wǎng)絡(luò)中權(quán)值最小的支撐樹，稱為該網(wǎng)絡(luò)的最小支撐樹。0( )( )( )max( )( )min( )eC eeeTGTGTew ew eTew ew e定理：設(shè) 是 的

8、支撐樹，則下面幾個命題等價：（1）：是 的最小支撐樹；（2）： 對任意上的邊 有（3）： 對任意 上的邊 有Kruskal算法 121.( )().(),0,1;2. 343.1,24. ,1;5.1 mjjw ew ew eSijG SejjjmSSeiiinG S 設(shè)若包含圈，轉(zhuǎn) ，否則轉(zhuǎn) ；令若轉(zhuǎn) ，否則停止；令并設(shè)若，則結(jié)束，這時即為所求；否則轉(zhuǎn)2.Kruskal算法設(shè)G=，將G中非環(huán)邊按權(quán)從小到大排序：e1, e2, , em.(1) 取e1在T中(2) 查e2，若e2與e1不構(gòu)成回路，取e2也在T 中，否則棄e2.(3) 再查e3, 直到得到生成樹為止. 例子所求最小生成樹如所求最小生成樹如圖所示，圖所示，W(T)=38. 求圖的一棵最小生成樹求圖的一棵最小生成樹.Dijkstra算法 12311., , ,.,2.min , , , ;3.,min ,2.tniikiikkvSkkikjjjkjTRvSv vvuwuuwuRRvSSvTTeSTvSuu w令選取若則停止，G中不存在支撐樹；否則令若，則停止， 為最小支撐樹；否則對于一切令轉(zhuǎn)時間復(fù)雜性Kruskal算法:Dijkstra算法：2(log )O nn2()O n作業(yè)140:1,2P