第七章 網(wǎng)絡(luò)優(yōu)化模型

第七章網(wǎng)絡(luò)優(yōu)化模型

圖與網(wǎng)絡(luò)的基本概念最短路徑問題最大流問題最小費(fèi)用最大流問題

哥尼斯堡七橋問題ABDC簡(jiǎn)捷表示事物之間的本質(zhì)聯(lián)系，歸納事物之間的一般規(guī)律ACDB在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e57.1圖與網(wǎng)絡(luò)的基本概念7.1圖與網(wǎng)絡(luò)的基本概念7.1.1圖與網(wǎng)絡(luò)的概念及分類1、圖：圖由點(diǎn)和邊組成G=(V,E)點(diǎn)集V={vi}邊集E={ei}vjvie每一條邊和兩個(gè)端點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)端點(diǎn)表示（vi，vj）邊數(shù)：m(G)=|E|點(diǎn)數(shù)：n(G)=|V|

7.1圖與網(wǎng)絡(luò)的基本概念無向邊：有向邊：無向圖：由無向邊構(gòu)成的圖有向圖：由有向邊構(gòu)成的圖2、無向圖和有向圖7.1圖與網(wǎng)絡(luò)的基本概念3、簡(jiǎn)單圖和多重圖環(huán)：e9多重邊：e6和e7簡(jiǎn)單圖：不含環(huán)和多重邊多重圖：含多重邊判斷下列哪些圖是簡(jiǎn)單圖，哪些圖是多重圖？7.1圖與網(wǎng)絡(luò)的基本概念7.1圖與網(wǎng)絡(luò)的基本概念4、次：以點(diǎn)v為端點(diǎn)的邊數(shù)叫做點(diǎn)v的次，d(v)

奇點(diǎn)：次為奇數(shù) 偶點(diǎn)：次為偶數(shù)懸掛點(diǎn)：d(v)=1 孤立點(diǎn)：d(v)=0定理7.1：任何圖，Σd(vi)=2m定理7.2：任何圖，奇點(diǎn)有偶數(shù)個(gè)7.1圖與網(wǎng)絡(luò)的基本概念出次d+(vi)

：有向圖中，以vi為始點(diǎn)的邊數(shù)入次d-(vi)

：有向圖中，以vi為終點(diǎn)的邊數(shù)Σd+(v)=Σd-(v)=m7.1圖與網(wǎng)絡(luò)的基本概念5、連通圖：鏈：無向圖G=（V,E）前后相繼的點(diǎn)邊序列稱為鏈初等鏈：點(diǎn)邊序列中沒有重復(fù)的點(diǎn)和重復(fù)邊的鏈稱為初等鏈(v1,e1,v2,e6,v4,e3,v3,e8,v5

)7.1圖與網(wǎng)絡(luò)的基本概念5、連通圖：圈：無向圖G=（V,E）中起點(diǎn)和終點(diǎn)重合的鏈稱為圈初等圈：沒有重復(fù)點(diǎn)和重復(fù)邊的鏈圈稱為初等圈(v1,e1,v2,e6,v4,e3,v3,e5,v1

)7.1圖與網(wǎng)絡(luò)的基本概念5、連通圖：對(duì)于有向圖來說，如果鏈和圈中邊的方向與有向圖中所標(biāo)方向相同，那么鏈就稱為道路，圈就稱為回路。連通圖：任意兩個(gè)點(diǎn)之間至少有一條鏈相連的圖稱為連通圖7.1圖與網(wǎng)絡(luò)的基本概念6、子圖與生成子圖：子圖：圖G=(V,E)，E’是E的子集，V’是V的子集，且E’的邊與V’的頂點(diǎn)想關(guān)聯(lián)，G’=(V’,E’)是圖G的一個(gè)子圖。生成子圖：若V’=V，則G’是G的生成子圖7.1圖與網(wǎng)絡(luò)的基本概念6、網(wǎng)絡(luò)：網(wǎng)絡(luò)（賦權(quán)圖）：由點(diǎn)、邊以及與點(diǎn)邊相關(guān)聯(lián)的權(quán)數(shù)所構(gòu)成的圖稱為網(wǎng)絡(luò)，記作N={V,E,W}v4v2v3v16215846v4v2v3v16215846無向網(wǎng)絡(luò) 有向網(wǎng)絡(luò)7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)1、樹（T）：無圈的連通圖稱為樹

樹葉

分枝點(diǎn)7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)2、樹的性質(zhì)性質(zhì)7.1樹中任意兩點(diǎn)之間有且只有一條鏈。性質(zhì)7.2如圖G中任意兩點(diǎn)之間，有且只有一條鏈，則該圖G是一個(gè)樹。性質(zhì)7.3一個(gè)樹，則m=n-1。性質(zhì)7.4樹中任意兩個(gè)不相鄰的點(diǎn)之間增加一條邊，則形成唯一的圈。性質(zhì)7.5一個(gè)樹如果去掉任何一條邊，該圖就不再連通。7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)3、圖的生成樹生成樹（支撐樹）：圖G的生成子圖是一棵樹，則稱該樹為G的生成樹圖G中屬于生成樹的邊稱為樹枝，不屬于生成樹的邊稱為弦定理7.3：圖G=（V,E）,有生成樹的充分必要條件為G是連通圖4、最小生成樹：圖G=(V，E)的生成樹所有樹枝上的權(quán)數(shù)的總和,稱為生成樹的權(quán)。權(quán)數(shù)最小的生成樹稱為最小生成樹。尋找最小生成樹的方法：避圈法、破圈法最小生成樹權(quán)=115、根樹有向樹：若一個(gè)有向圖在不考慮邊的方向時(shí)是一棵樹，則稱這個(gè)有向圖為有向樹。根樹：有向樹T，恰有一個(gè)結(jié)點(diǎn)入次d-(vi)=0，其余各點(diǎn)入次d-(vi)=1，則稱T為根樹根樹中入次d-(vi)=0的點(diǎn)稱為根出次d+(vi)=0稱為葉其他點(diǎn)稱為分枝點(diǎn)7.1圖與網(wǎng)絡(luò)的基本概念在根樹中，若每個(gè)頂點(diǎn)的出次d-(vi)≤m，稱這棵樹為m叉樹。若每個(gè)頂點(diǎn)的出次d-(vi)=m或0，則稱這棵樹為完全m叉樹7.1圖與網(wǎng)絡(luò)的基本概念v2v3v7v1v8v4v5v66134105275934682求從v1到v8的最短路徑標(biāo)號(hào)：T標(biāo)號(hào)（試探性標(biāo)號(hào)）P標(biāo)號(hào)（永久性標(biāo)號(hào)）1、狄克斯托算法（Dijkstra）:標(biāo)號(hào)法7.2最短路問題V2V3V7V1V8V4V5V66134105275934682S={v1}P(v1)=0,T(vi)=∞T(v2)=2,T(v4)=1,T(v6)=3min{T(v2),T(v4),T(v6)}=min{2，1，3}=1P(v4)

=1S={v1,v4}P(v1)=0L12=2L14=1L16=3P(v4)=1v2v3v7v1v8v4v5v66134105275934682S={v1,v4}P(v2)

=2P(v1)=0P(v4)=1T(v2)=2T(v6)=3T(v7)=3min{T(v2),T(v6),T(v7)}=min{2，3，3}=2P(v2)

=2S={v1,v4,v2}L12=2L16=3L42=11L47=3v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2}P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L16=3L47=3L23=8L25=7T(v6)=3T(v7)=3T(v3)=8T(v5)=7min{T(v6),T(v7),T(v3),T(v5)}=min{3,3,8,7}=3P(v6)

=3S={v1,v4,v2,v6}v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6}P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L47=3L23=8L25=7L67=7T(v7)=3T(v3)=8T(v5)=7min{T(v7),T(v3),T(v5)}=min{3,8,7}=3P(v7)

=3S={v1,v4,v2,v6,v7}v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7}P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L23=8L25=7L75=6L78=11T(v3)=8T(v5)=6T(v8)=11min{T(v3),T(v5),T(v8)}=min{8,6,11}=6P(v5)

=6S={v1,v4,v2,v6,v7,v5}v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,v5}P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L23=8L53=15L58=10L78=11T(v3)=8T(v8)=10min{T(v3),T(v8)}=min{8,10}=8P(v3)

=8S={v1,v4,v2,v6,v7,

v5,

v3}v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,

v5,

v3}P(v8)

=10P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L38=14L58=10L78=11T(v8)=10P(v8)

=10S={v1,v4,v2,v6,v7,

v5,

v3,v8}v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,

v5,

v3,v8}v1到v8的最短路徑為{v1,v4,v7,

v5,

v8}，長(zhǎng)度為10P(v8)

=10P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2狄克斯托算法（Dijkstra）的適用條件：1、用于賦權(quán)有向圖。對(duì)于賦權(quán)無向圖的處理2、權(quán)數(shù)wij

≥02、逐次逼近算法可用于網(wǎng)絡(luò)中有權(quán)數(shù)為負(fù)數(shù)的邊7.2最短路問題7.2最短路問題v1v3v4v2v5vtvsww6243743179887.3最大流問題1、流量和容量有向連通圖G=(V，E),G的每條邊（vi，vj）上有非負(fù)數(shù)cij稱為邊的容量，僅有一個(gè)入次=0的點(diǎn)vs稱為發(fā)點(diǎn)，一個(gè)出次=0的點(diǎn)vt稱為收點(diǎn)，其余點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，記為G（V,E,C）。7.3.1基本概念7.3最大流問題2、可行流和最大流可行流必須滿足的兩個(gè)條件 （1）容量限定條件：0≤fij≤cij

（2）流量守恒條件：每一個(gè)節(jié)點(diǎn)流量平衡7.3最大流問題vjvifij=5cij=5飽和邊、不飽和邊、流量的間隙（