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

上傳人:奔*** 文檔編號(hào):29370902 上傳時(shí)間:2021-10-07 格式:PPT 頁(yè)數(shù):21 大小:400.50KB
收藏 版權(quán)申訴 舉報(bào) 下載
第08講 圖的基本概念及最小支撐樹(shù)問(wèn)題_第1頁(yè)
第1頁(yè) / 共21頁(yè)
第08講 圖的基本概念及最小支撐樹(shù)問(wèn)題_第2頁(yè)
第2頁(yè) / 共21頁(yè)
第08講 圖的基本概念及最小支撐樹(shù)問(wèn)題_第3頁(yè)
第3頁(yè) / 共21頁(yè)

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁(yè)未讀,繼續(xù)閱讀

資源描述:

《第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

展開(kāi)閱讀全文
溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!

五月丁香婷婷狠狠色,亚洲日韩欧美精品久久久不卡,欧美日韩国产黄片三级,手机在线观看成人国产亚洲