《運籌學(xué)》6圖論教學(xué)課件_第1頁
《運籌學(xué)》6圖論教學(xué)課件_第2頁
《運籌學(xué)》6圖論教學(xué)課件_第3頁
《運籌學(xué)》6圖論教學(xué)課件_第4頁
《運籌學(xué)》6圖論教學(xué)課件_第5頁
已閱讀5頁，還剩115頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

運籌學(xué)課件運帷回回回回回包巴回回回回回回回包回回回回圈與罔輅分析之決勝千里之外NetworkAnalysis第一節(jié)圖的基本概念與模型無向圖的基本概念定義:稱G=(NE是一個圖,如果有(1)N是非空有限集;(2)E是N中元素對所組成的集合。且,稱N的元素為頂點,E的元素為邊記號:圖G=(N,E)簡記為G圖G的頂點集簡記為NG)或NG的點集合:(例如:圖(1)中的N=(1,2,3,4,5)是一個無向圖的點的集合)G的邊集合:E={e}且={n,}為右圖無序二元組e的端點:有e1n1,n1},則稱n1和n為e;的端點,且稱e;連接點n和n環(huán):兩個端點重合為一點的邊(例如右圖中的e1)孤立點:不與任何邊關(guān)聯(lián)的點(例如右圖中的n2)有向圖的基本概念有向圖G:一個有序二員組(NA),記為G=(NA)G的弧集合:A={ai}且aij={ninj}為有序二元組,若lj={ni,nj},則稱i從m連向j,ni稱為的尾,川為di的頭,n稱為j的先輩,n稱為ni的后繼有向圖G的基本圖:對于G的每條弧用一條邊代替后得到的無向圖續(xù)(1)關(guān)聯(lián):一條邊的端點稱為這條邊的關(guān)聯(lián)鄰接:與同一條邊關(guān)聯(lián)的端點稱為是鄰接的,同時如果兩條邊有一個公共端點,則稱這兩條邊是鄰接的有限圖:點和邊都是有限集合的圖空圖:沒有任何邊的圖平凡圖:只有一個點的圖簡單圖:既沒有環(huán)也沒有兩條邊連接同一對點的圖度(次)無向圖G有向圖D各頂點度數(shù)為:d(V1)=4d(V2)=2各頂點度數(shù)為:d(V3)=1d(V4=2d()=d+(v1)+d(1)=3+0=3d(V5)=?d(V2)=d+(V2)+d(V2)=1+1=2第7頁度的有關(guān)定理定理1(握手定理)設(shè)G=<V,E>為任意圖(無向的或者有向的),V={v1,V2,…,,Vn},邊的條數(shù)Ed(v,)=2m=2|E推論任何圖(無向的或者有向的)中,度數(shù)為奇數(shù)的頂點個數(shù)是偶數(shù)。定理2設(shè)D=<VE>為有向圖,V={V1,V2,…,vn},邊的條數(shù)E=m,則∑d()=∑d第8頁續(xù)(2)完全圖:每一對點之間均有一條邊相連的圖偶圖(二分圖):若N(G)能分解為N與N2合于N∪N2=N(G),N1⌒N2=①,且N自身的頂點互不相鄰(i=1,2)則稱G是偶圖;記為G=(N1,N2E)完全偶圖:不在同一頂點子集的任二頂點都相鄰的簡單偶圖;子圖圖G=(NE)的子圖G′=(N,E):NcN和E'gE,對E

溫馨提示

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

評論

0/150

提交評論