運籌學11-圖與網(wǎng)絡.ppt_第1頁
運籌學11-圖與網(wǎng)絡.ppt_第2頁
運籌學11-圖與網(wǎng)絡.ppt_第3頁
運籌學11-圖與網(wǎng)絡.ppt_第4頁
運籌學11-圖與網(wǎng)絡.ppt_第5頁
已閱讀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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論