




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、圖的定義和基本術(shù)語(yǔ)數(shù) 據(jù) 結(jié) 構(gòu)圖圖的定義和基本術(shù)語(yǔ)圖:圖G由V(G)和E(G)這兩個(gè)集合所組成,記為G=(V,E),其中V(G)是頂點(diǎn)(Vertex)的非空集,每個(gè)頂點(diǎn)可以標(biāo)以不同的字符或數(shù)字;E(G)是邊(Edge)的集合,特殊情況下E(G)可以是空集。每個(gè)邊由其所連接的兩個(gè)頂點(diǎn)表示。無向圖:對(duì)于一個(gè)圖G,若邊集合E(G)為無向邊的集合,則稱該圖為無向圖。有向圖:對(duì)于一個(gè)圖G,若邊集合E(G)為有向邊的集合,則稱該圖為有向圖。圖圖6.1 有向圖與無向圖無向圖G1有向圖G2圖完全圖:在一個(gè)有n個(gè)頂點(diǎn)的無向圖中,若每個(gè)頂點(diǎn)到其它(n-1)個(gè)頂點(diǎn)都連有一條邊,則圖中共有n(n-1)/2條邊,這種
2、圖稱為完全圖(Complete graph,也稱完備圖)。左圖所示就是n=4的完全圖,它一共有六條邊。 圖權(quán)和網(wǎng)絡(luò):有些圖, 對(duì)應(yīng)每條邊有一相應(yīng)的數(shù)值,這個(gè)數(shù)值叫做該邊的權(quán)(Weight)。邊上帶權(quán)的圖稱為帶權(quán)圖,也稱為網(wǎng)絡(luò)(Network)。子圖:設(shè)有兩個(gè)圖G =(V,E)和G=(V,E),若V(G)是V(G)的子集,且E(G)是E(G)的子集,則稱G是G的子圖(Subgraph)。例如圖6.3所示的圖是圖6.1中G1的一些子圖。 圖圖6.3 子圖圖頂點(diǎn)的度:圖中與每個(gè)頂點(diǎn)相連的邊數(shù),叫該頂點(diǎn)的度(Degree)。例如圖6.1的圖G1中,頂點(diǎn)的度數(shù)為2,頂點(diǎn)的度數(shù)為3,。 入度、出度:對(duì)于有
3、向圖,頂點(diǎn)的度分為入度和出度,入度是以該頂點(diǎn)為終點(diǎn)的入邊數(shù)目;出度是以該頂點(diǎn)為起點(diǎn)的出邊數(shù)目,該頂點(diǎn)的度等于其入度和出度之和。例如在圖6.1的圖G2中,頂點(diǎn)的入度為1,出度為2,而頂點(diǎn)的入度為1,出度為0,因?yàn)橛幸粭l邊指向它,而沒有邊從它指出去。 圖路徑:在一個(gè)圖中,若從某頂點(diǎn)Vp出發(fā),沿一些邊經(jīng)過頂點(diǎn)V1,V2,Vm到達(dá),Vq,則稱頂點(diǎn)序列(Vp, V1,V2,Vm, Vq)為從Vp到Vq的路徑(Path)。路徑長(zhǎng)度:對(duì)于無權(quán)的圖,路徑長(zhǎng)度指的是沿此路徑上邊的數(shù)目;對(duì)于有權(quán)圖,一般是取沿路徑各邊的權(quán)之和作為此路徑的長(zhǎng)度。若一條路徑上各頂點(diǎn)均不重復(fù),即路徑經(jīng)過每一頂點(diǎn)不超過一次,則此路徑叫做簡(jiǎn)
4、單路徑。如果從一個(gè)頂點(diǎn)出發(fā)又回到該頂點(diǎn),即Vp與Vq相同,則此路徑叫做環(huán)路(Cycle)。圖連通、連通圖:在無向圖中,如果從頂點(diǎn)Vi到頂點(diǎn)Vj之間有路徑,則稱這兩個(gè)頂點(diǎn)是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱此圖是連通圖(Connected graph)。連通分量:例如圖6.1中的圖G1是連通圖。圖6.4中的圖就是非連通圖,非連通圖的每一個(gè)極大連通子圖叫連通分量(Connected Component),此圖包括二個(gè)連通分量。 圖圖6.4 非連通圖G圖強(qiáng)連通圖和強(qiáng)連通分量:在有向圖G中,如果從頂點(diǎn)Vi到頂點(diǎn)Vj和從頂點(diǎn)Vj到頂點(diǎn)Vi之間都有路徑,則稱這兩個(gè)頂點(diǎn)是強(qiáng)連通的。如果圖中任何一對(duì)頂點(diǎn)都是強(qiáng)連通的,則此圖叫做強(qiáng)連通圖。非強(qiáng)連通圖的每一個(gè)極大強(qiáng)連通子圖叫做強(qiáng)連通分
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝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ù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 甲狀旁腺癌5例病例報(bào)告及文獻(xiàn)復(fù)習(xí)
- 小學(xué)語(yǔ)文教學(xué)提高學(xué)生閱讀理解能力的路徑研討
- 企業(yè)支付貨款合同范例
- 減水劑運(yùn)輸合同范例
- oem藥品合同范例
- 共同制作招牌合同范例
- 分期抵押車合同范例
- 中醫(yī)門診加盟合同范例
- 房屋壓頂施工方案范本
- 倉(cāng)儲(chǔ)信息咨詢合同范例
- 地鐵出入口雨棚施工工藝
- 掘金之旅:金融不良資產(chǎn)處置十八般武藝
- 雙機(jī)抬吊法吊運(yùn)箱梁安全控制要點(diǎn)課件
- 房建工程樣板節(jié)點(diǎn)參考照片圖文并茂
- 2023年高考語(yǔ)文全國(guó)乙卷《長(zhǎng)出一地的好蕎麥》解析
- ICC國(guó)際冠軍杯傳播及招商方案
- 豐田車系卡羅拉(雙擎)轎車用戶使用手冊(cè)【含書簽】
- 商品價(jià)格表(全)
- 管理系統(tǒng)中計(jì)算機(jī)應(yīng)用詳細(xì)課件
- 危險(xiǎn)廢棄物管理培訓(xùn)資料
- 三月三主題班會(huì)課件
評(píng)論
0/150
提交評(píng)論