圖與網(wǎng)絡(luò)分析.ppt

1、1.運(yùn)籌學(xué)，圖與網(wǎng)絡(luò)分析，第10章圖與網(wǎng)絡(luò)，趙偉，3。主要內(nèi)容：10.1基本概念10.2最短路徑問題(1)貝爾曼優(yōu)化原理(2) Dijustra算法(雙括號法)(3)通信線路布局問題(4)設(shè)備更新問題10.3最小生成樹(1)基本概念和理論(2) Kruskal算法(加邊法、破圓法)(3)邊丟失法(破圓法)10.4最大流問題(1)基本概念(2)雙標(biāo)簽算法10.5最小費(fèi)用最大流(1)基本概念(2)求解算法，5.5其中V=V1Vn稱為g的點(diǎn)集，E=(eij)稱為g的邊集，evj是連接VV和vj的邊。6。如果N和E都是有限集合，那么G是一個有限圖，否則它被稱為無限圖。如果既沒有有限環(huán)(圈)也沒有兩條邊

2、連接同一對點(diǎn)，g就叫做簡單圖。正如右圖的(a)所示，右圖的(b)不是一個簡單的數(shù)字。如果G是一個簡單的圖，并且G中的每一對點(diǎn)都由一條邊連接，則G被稱為完全圖。圖(a)是一個簡單的圖表，但不是一個完整的圖表。，圖A，圖b，7，def 2:有向圖G是一個有序的二進(jìn)制集合，表示為G=(V，A)，其中V=(V1V2Vn)稱為G的點(diǎn)集，A=aij稱為G的弧()。|V|=n表示g中的節(jié)點(diǎn)數(shù)為n，也稱為圖g的階。|A|=m表示有向圖g中的弧數(shù)為m，與任一頂點(diǎn)相關(guān)聯(lián)的邊數(shù)稱為頂點(diǎn)的度。8，2連通圖def 3:在有向圖g中，點(diǎn)和邊Vi eij VjVk ekl Vl的交替序列稱為從點(diǎn)Vi到g中的Vl的路徑。如果

3、道路a的起點(diǎn)和終點(diǎn)重合，則a稱為環(huán)路；如果G中的點(diǎn)Vi和Vj之間有路徑，那么點(diǎn)Vi和Vj是連接的。如果圖G中的任意兩點(diǎn)是連通的，那么圖G稱為連通圖，或者說圖G是連通的。無向圖中有相應(yīng)的概念。9、3子圖def 4:有兩個圖：G1=(V1，E1)，G2=(V2，E2)。如果有，那么G1被稱為G2的子圖，寫為：如果V1=V2存在，那么G1=(V1，E1)是G2=(V2，E2)的生成子圖(支持子圖)。10，例：下圖G1是圖G的子圖，圖G2是圖G的生成子圖。V1，V2，V4，(A)圖G，(b)圖G1，(c)圖G2，11，4，加權(quán)圖和網(wǎng)絡(luò)定義5:設(shè)G是圖(或有向圖)，如果G的每條邊(或弧)都給定了一個實(shí)數(shù)

4、ij，則稱G=(V，E，W)(或(V，A，W)是加權(quán)圖， 并且在g的v中規(guī)定了起點(diǎn)(通常稱為Vs)和終點(diǎn)(稱為Vt)，那么以這種方式規(guī)定了起點(diǎn)和終點(diǎn)的加權(quán)圖g被稱為網(wǎng)絡(luò)。12，10.2最短路徑問題，定義6:設(shè)G=(V，A，W)是一個加權(quán)有向圖，Vs是指定的起點(diǎn)，Vt是指定的終點(diǎn)，其余的是中間點(diǎn)。P是G中從Vs到Vt的有向路徑，稱為路徑P的長度，如果有，則稱為G中從Vs到Vt的最短路徑。最短路徑問題在工程設(shè)計(jì)和企業(yè)管理中有重要的應(yīng)用，如選址、場地布置、設(shè)備更新和網(wǎng)絡(luò)線路安裝。14，(1)貝爾曼優(yōu)化原理，1命題1:如果p是網(wǎng)絡(luò)g中從Vs到Vt的最小路徑，Vl是p中除Vs和Vt之外的任何中間點(diǎn)，那么沿著p從Vs到Vl的P1也必須是從Vs到Vl的最小路徑。vs，v1，Vl