第08講 圖的基本概念及最小支撐樹(shù)問(wèn)題

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

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

2、不相鄰；7.二部分圖(二分圖)8.支撐子圖9.導(dǎo)出子圖10. 點(diǎn)度、通路、回路GG有向圖定義 有向圖D=, 只需注意E是VV 的多重子集圖2表示的是一個(gè)有向圖，試寫(xiě)出它的V 和 E 注意：圖的數(shù)學(xué)定義與圖形表示，在同構(gòu)的意義下是一一對(duì)應(yīng)的網(wǎng)絡(luò)(帶權(quán)圖)對(duì)于圖G的每條邊e都賦予一個(gè)值w(e),稱為邊的權(quán)，則G連同邊上的權(quán)稱為一個(gè)網(wǎng)絡(luò)，記為G=(V,E,w)無(wú)向圖的關(guān)聯(lián)矩陣無(wú)向圖的關(guān)聯(lián)矩陣（對(duì)圖無(wú)限制）定義 無(wú)向圖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( 的的終終點(diǎn)點(diǎn)為為，不不關(guān)關(guān)聯(lián)聯(lián)與與，的的始始點(diǎn)點(diǎn)為為jijijiijevevevm10,1 定義定義 有向圖有向圖D=，則稱則稱 (mij)n m為為D的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記為，記為M(D). (4) 平行邊對(duì)應(yīng)的列相同平行邊對(duì)應(yīng)的列相同性質(zhì)性質(zhì)有向圖的關(guān)聯(lián)矩陣鄰接矩陣定義 設(shè)無(wú)向圖D=, V=v1, v2, , vn, E=e1, e2, , em

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

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

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

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

8、支撐樹(shù)，則下面幾個(gè)命題等價(jià)：（1）：是 的最小支撐樹(shù)；（2）： 對(duì)任意上的邊 有（3）： 對(duì)任意 上的邊 有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é)束，這時(shí)即為所求；否則轉(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, 直到得到生成樹(shù)為止. 例子所求最小生成樹(shù)如所求最小生成樹(shù)如圖所示，圖所示，W(T)=38. 求圖的一棵最小生成樹(shù)求圖的一棵最小生成樹(shù).Dijkstra算法 12311., , ,.,2.min , , , ;3.,min ,2.tniikiikkvSkkikjjjkjTRvSv vvuwuuwuRRvSSvTTeSTvSuu w令選取若則停止，G中不存在支撐樹(shù)；否則令若，則停止， 為最小支撐樹(shù)；否則對(duì)于一切令轉(zhuǎn)時(shí)間復(fù)雜性Kruskal算法:Dijkstra算法：2(log )O nn2()O n作業(yè)140:1,2P