




已閱讀5頁,還剩64頁未讀, 繼續(xù)免費閱讀
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第十一章圖與網(wǎng)絡規(guī)劃11.1圖與網(wǎng)絡的基本概念11.2樹及最小樹問題11.3最短路問題11.4網(wǎng)絡最大流問題11.1圖與網(wǎng)絡的基本概念圖的概念所謂圖,就是頂點和邊的集合,點的集合記為V,邊的集合記為E,則圖可以表示為:G(V,E),點代表被研究的事物,邊代表事物之間的聯(lián)系,因此,邊不能離開點而獨立存在,每條邊都有兩個端點。在畫圖時,頂點的位置、邊和長短形狀都是無關緊要的,只要兩個圖的頂點及邊是對應相同的,則兩個圖相同。圖的表示,211e,212e,413e,314e,315e,426e,437e,448e,549e),(),(987654321654321eeeeeeeeeEe1e2e3e4e5v2v3v1v4v5v6e6e7e8e9點與邊頂點數(shù)集合V中元素的個數(shù),記作p(G)。邊數(shù)集合E中元素的個數(shù),記作q(G)。若e=u,vE,則稱u和v為e的端點,而稱e為u和v的關聯(lián)邊,也稱u,v與邊e相關聯(lián)。例如圖中的圖G,p(G)=6,q(G)=9,v1,v2是e1和e2的端點,e1和e2都是v1和v2的關聯(lián)邊。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9點邊關系若點u和v與同一條邊相關聯(lián),則u和v為相鄰點;若兩條邊ei和ej有同一個端點,則稱ei與ej為相鄰邊。例如在圖中v1和v2為相鄰點,v1和v5不相鄰;e1與e5為相鄰邊,e1和e7不相鄰。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9簡單圖若一條邊的兩個端點是同一個頂點,則稱該邊為環(huán);又若兩上端點之間有多于一條邊,則稱為多重邊或平行邊。例如圖的e8為環(huán),e1,e2為兩重邊,e4,e5也是兩重邊。含有多重邊的圖稱作多重圖。無環(huán)也無多重邊的圖稱作簡單圖。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9圖的次次點v作為邊的端點的次數(shù),記作d(v),如圖中,d(v1)=5,d(v4)=6等端點次為奇數(shù)的點稱作奇點;次為偶數(shù)的點稱作偶點。次為1的點稱為懸掛點,與懸掛點連接的邊稱作懸掛邊;次為0的點稱為孤立點。圖中的點v5即為懸掛點,邊e9即為懸掛邊,而點v6則是弧立點。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9定理若圖G中所有點都是孤立點,則稱圖G為空圖。定理1所有頂點的次的和,等于所有邊數(shù)的2倍。即qdV2)(e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9定理2在任一圖中,奇點的個數(shù)必為偶數(shù)。設V1和V2分別是圖G中次數(shù)為奇數(shù)和偶
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 電影特效工作室行業(yè)深度調研及發(fā)展戰(zhàn)略咨詢報告
- 康復醫(yī)療機器人行業(yè)跨境出海戰(zhàn)略研究報告
- 中國中醫(yī)藥保健品行業(yè)市場集中度、企業(yè)競爭格局分析報告-智研咨詢發(fā)布
- 運動褲批發(fā)企業(yè)縣域市場拓展與下沉戰(zhàn)略研究報告
- 動物類露酒企業(yè)ESG實踐與創(chuàng)新戰(zhàn)略研究報告
- 豬肉及雜碎罐頭企業(yè)縣域市場拓展與下沉戰(zhàn)略研究報告
- 模塊化建筑預制件生產行業(yè)跨境出海戰(zhàn)略研究報告
- 大型貨物道路運輸企業(yè)ESG實踐與創(chuàng)新戰(zhàn)略研究報告
- 機器人磨削與拋光系統(tǒng)行業(yè)深度調研及發(fā)展戰(zhàn)略咨詢報告
- 基于互耦垂直腔面發(fā)射激光器(VCSELs)的多通道光子儲備池計算研究
- 中國氣血健康白皮書
- 食品的營養(yǎng)課件
- 化學品安全技術說明書 MSDS( 石腦油)
- 電位計算精品課件
- DB13T 5542-2022 水利水電工程施工組織設計編制指南
- 中子源介紹課件
- 二期6KV系統(tǒng)1
- 研究生面試復試英語+常問問題
- 安徽省教育科學研究項目課題申請書【模板】
- 參考文獻的標注規(guī)范
- 幼年特發(fā)性關節(jié)炎.
評論
0/150
提交評論