Chap圖與網(wǎng)絡(luò)分析實(shí)用

會(huì)計(jì)學(xué)1Chap圖與網(wǎng)絡(luò)分析實(shí)用Copyrights?2006-poweredbynerdpal@HIT最短路問題:從給定的網(wǎng)絡(luò)圖中找出某一點(diǎn)到其它點(diǎn)的最短距離公認(rèn)的求最短路徑問題的較好的算法是由E.W.Dijkstra(狄克斯屈拉)于1959年給出的標(biāo)號(hào)法最短路問題第1頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V5V6V2V3V75727241360226V4567710Dijkstra標(biāo)號(hào)法本頁播放時(shí)隱藏,保留第2頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V5V6V2V3V75727241360226V4Dijkstra標(biāo)號(hào)法第3頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V5V6V2V3V75727241360226V45Dijkstra標(biāo)號(hào)法第4頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V5V6V2V3V75727241360226V456Dijkstra標(biāo)號(hào)法第5頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V5V6V2V3V75727241360226V45677Dijkstra標(biāo)號(hào)法第6頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V5V6V2V3V75727241360226V4567710Dijkstra標(biāo)號(hào)法第7頁/共45頁Copyrights?2006-poweredbynerdpal@HIT2V1V5V6V2V3V7577241360226V451112915Dijkstra標(biāo)號(hào)法－有向圖本頁播放時(shí)隱藏,保留第8頁/共45頁Copyrights?2006-poweredbynerdpal@HIT2V1V5V6V2V3V7577241360226V4Dijkstra標(biāo)號(hào)法－有向圖第9頁/共45頁Copyrights?2006-poweredbynerdpal@HIT2V1V5V6V2V3V7577241360226V45Dijkstra標(biāo)號(hào)法－有向圖第10頁/共45頁Copyrights?2006-poweredbynerdpal@HIT2V1V5V6V2V3V7577241360226V459Dijkstra標(biāo)號(hào)法－有向圖第11頁/共45頁Copyrights?2006-poweredbynerdpal@HIT2V1V5V6V2V3V7577241360226V45119Dijkstra標(biāo)號(hào)法－有向圖第12頁/共45頁Copyrights?2006-poweredbynerdpal@HIT2V1V5V6V2V3V7577241360226V4511129Dijkstra標(biāo)號(hào)法－有向圖第13頁/共45頁Copyrights?2006-poweredbynerdpal@HIT2V1V5V6V2V3V7577241360226V451112915Dijkstra標(biāo)號(hào)法－有向圖第14頁/共45頁Copyrights?2006-poweredbynerdpal@HIT最短路問題的數(shù)學(xué)模型第15頁/共45頁

圖的基本概念與模型

樹圖和圖的最小生成樹

最短路問題

中國郵遞員問題

網(wǎng)絡(luò)最大流運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用之圖與網(wǎng)絡(luò)分析第16頁/共45頁Copyrights?2006-poweredbynerdpal@HIT一個(gè)郵遞員從郵局出發(fā)，走遍他負(fù)責(zé)投遞的每一條街道，然后再返回郵局，問應(yīng)選擇什么樣的路線，使走的路程最短？V1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中國郵路問題類似于歐拉回路第17頁/共45頁Copyrights?2006-poweredbynerdpal@HITKonigsberg七橋問題歐拉回路歐拉圖ACBDABCD第18頁/共45頁Copyrights?2006-poweredbynerdpal@HIT是歐拉圖；不是歐拉圖，但存在歐拉回路；即不是歐拉圖，也不存在歐拉回路。例(a)(b)(b)(c)(c)第19頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中國郵路問題每條邊上最多重復(fù)一次在圖G的每個(gè)回路上，有重復(fù)的邊的長度不超過回路總長的一半歐拉圖將奇點(diǎn)兩兩相連，變成偶點(diǎn)第20頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中國郵路問題××××××××在圖G的每個(gè)回路上，有重復(fù)的邊的長度不超過回路總長的一半第21頁/共45頁Copyrights?2006-poweredbynerdpal@HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中國郵路問題××××××××第22頁/共45頁

圖的基本概念與模型

樹圖和圖的最小生成樹

最短路問題

中國郵遞員問題

網(wǎng)絡(luò)最大流運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用之圖與網(wǎng)絡(luò)分析第23頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流一

引言在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。而網(wǎng)絡(luò)系統(tǒng)的最大流問題是圖與網(wǎng)絡(luò)流理論中的最優(yōu)化問題，它對(duì)于解決生產(chǎn)實(shí)際問題起著十分重要的作用。第24頁/共45頁Copyrights?2006-poweredbynerdpal@HIT每條弧旁邊的權(quán)就是對(duì)應(yīng)的容量(最大通過能力)。要求指定一個(gè)產(chǎn)品運(yùn)輸方案，使得從s→t的貨運(yùn)量最大，這是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題，即從發(fā)點(diǎn)s到收點(diǎn)t允許通過的最大流量。tv3v2v1v4s1069879552Cij§5網(wǎng)絡(luò)最大流第25頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流二基本概念

定義設(shè)一個(gè)加權(quán)有向圖D(V,A)，在V中指定一個(gè)發(fā)點(diǎn)s和一個(gè)收點(diǎn)t，其他的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的弧(vi,vj)∈A，都有一個(gè)權(quán)cij叫做弧的容量。這樣的圖D稱做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡稱網(wǎng)絡(luò)，記做D(V,A,C)。網(wǎng)絡(luò)D上的流，是指加在弧集合A上的一組負(fù)載量,記作f(vi,vj),或fij.若網(wǎng)絡(luò)上所有的fij=0，稱為零流。第26頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流

該圖給出了網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）,每一個(gè)弧上的流量

fij

就是運(yùn)輸量，例如fs1=8，fs2=5，f13=4等等tv3v2v1v4s(8)(1)(4)(8)(5)(9)(5)(4)(0)fij第27頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流網(wǎng)絡(luò)系統(tǒng)上流的特點(diǎn)：(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等；(2)每一個(gè)中間點(diǎn)的凈流量=0，即流入量-流出量=0；(3)每一條弧上的流量不能超過它的最大通過能力（即容量）。第28頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流定義網(wǎng)絡(luò)上的一個(gè)流f

稱作可行流，若f滿足以下條件：（1）容量條件：對(duì)于每一個(gè)?。╲i,vj）∈A，有0fij

cij（2）平衡條件：對(duì)于發(fā)點(diǎn)s，有∑fsj-∑fjs=v(f)

對(duì)于收點(diǎn)

t，有∑ftj-∑fjt=-v(f)

對(duì)于中間點(diǎn)，有∑fij-∑fji=0v(f)

表示可行流的流量。第29頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流第30頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流任意一個(gè)網(wǎng)絡(luò)都存在可行流。如零流v(f)=0,就滿足可行流的條件。網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流f,其流量v(f)

達(dá)到最大值。設(shè)流f={fij}是網(wǎng)絡(luò)D上的一個(gè)可行流，fij=cij的弧稱為飽和弧；fij<cij的弧稱為非飽和弧；fij>0的弧為非零流弧，fij=0的弧為零流弧。第31頁/共45頁Copyrights?2006-poweredbynerdpal@HIT割是指將網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開,并使s→t的流中斷的一組弧的集合.K將網(wǎng)絡(luò)上的點(diǎn)分割成V和V，s∈V,t∈V,稱弧集（V,V）={(v1,v3),(v2,v4)}是分離s和t的割.注意:弧(v3,v2)即使不割斷,從s→t的流仍然中斷.Ktv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)第32頁/共45頁Copyrights?2006-poweredbynerdpal@HIT

將割中所有弧的容量之和稱作割的容量，記作

,即Ktv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)第33頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流結(jié)論:

在網(wǎng)絡(luò)D中,任何一個(gè)可行流f的流量v(f)都小于或等于這個(gè)網(wǎng)絡(luò)中任何一個(gè)割(V,V)的容量.設(shè)μ是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)s和收點(diǎn)t的一條鏈。定義鏈的方向是從s→t，于是鏈μ上的弧被分為兩類：一是弧的方向與鏈的方向相同，叫做前向弧，記作μ+;二是弧的方向與鏈的方向相反，叫做后向弧，記作μ-.第34頁/共45頁Copyrights?2006-poweredbynerdpal@HIT飽和弧:(s,v1),(v2,v4),(v3,t);其他的弧都是非飽和弧;(v3,v2)是零流弧.如圖，在鏈（s,v1,v2,v3,v4,t)中，μ+={(s,v1),(v1,v2),(v4,t)},

μ-={(v3,v2),(v4,v3)}.§5網(wǎng)絡(luò)最大流tv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)第35頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流增廣鏈，如果鏈μ滿足以下條件：1．在?。╲i,vj）∈μ+上，有0<=fij<cij

，即μ+中的每一條弧是非飽和弧。2．在弧（vi,vj）∈μ-上，有0<fij<=cij，即μ-中的每一條弧是非零流弧。第36頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流如圖，鏈μ=（s,v2,v1,v3,v4,t）就是一條增廣鏈。tv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)第37頁/共45頁Copyrights?2006-poweredbynerdpal@HIT第38頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流定理1網(wǎng)絡(luò)中的一個(gè)可行流f*

是最大流當(dāng)且僅當(dāng)不存在關(guān)于f*

的增廣鏈。定理2在網(wǎng)絡(luò)中s→t

的最大流量等于最小割的容量。定理1實(shí)際上提供了尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法：如果網(wǎng)絡(luò)D中有一個(gè)可行流f

，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f的增廣鏈。如果沒有增廣鏈，那么f

一定是最大流。如有增廣鏈，可以按照定理2，不斷增大可行流f的流量，最終可以得到一個(gè)最大流。第39頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流三．標(biāo)號(hào)法從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)（如果D中沒有f，可以令f是零流），運(yùn)用標(biāo)號(hào)法，經(jīng)過標(biāo)號(hào)過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個(gè)最大流。用給頂點(diǎn)標(biāo)號(hào)的方法來定義V1*.在標(biāo)號(hào)過程中，有標(biāo)號(hào)的頂點(diǎn)是V1*中的點(diǎn)，沒有標(biāo)號(hào)的點(diǎn)不是V1*中的點(diǎn)。如果vt有了標(biāo)號(hào)，表示存在一條關(guān)于f的增廣鏈。如果標(biāo)號(hào)過程無法進(jìn)行下去，并且vt未被標(biāo)號(hào)，則表示不存在關(guān)于f的增廣鏈。這樣，就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集。第40頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流1．標(biāo)號(hào)過程在標(biāo)號(hào)過程中，網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號(hào)點(diǎn)（分為已檢查和未檢查兩種）?；蛘呤俏礃?biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的。以便找出增廣鏈。第二個(gè)標(biāo)號(hào)是為了用來確定增廣鏈上的調(diào)整量θ。

標(biāo)號(hào)過程開始，先給vs標(biāo)號(hào)（0，+∞）。這時(shí)，vs是標(biāo)號(hào)未檢查的點(diǎn)，其他都是未標(biāo)號(hào)點(diǎn)。一般地，取一個(gè)標(biāo)號(hào)未檢查點(diǎn)vi，對(duì)一切未標(biāo)號(hào)點(diǎn)vj：第41頁/共45頁Copyrights?2006-poweredbynerdpal@HIT§5網(wǎng)絡(luò)最大流1）如果在弧（vi,vj）上，fij<cij,那么給vj標(biāo)號(hào)（vi,l(vj)）.其中l(wèi)(