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

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

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

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

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

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

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

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

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

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

樹葉

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

=10P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

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

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

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

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