運(yùn)籌學(xué)——圖與網(wǎng)絡(luò)分析實(shí)用教案

1、會計(jì)學(xué)1運(yùn)籌學(xué)運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析第一頁，共41頁。OR3 2北京濟(jì)南徐州青島南京上海連云港鄭州武漢天津第1頁/共41頁第二頁，共41頁。OR3 3v5v4v3v2v1第2頁/共41頁第三頁，共41頁。OR3 4第3頁/共41頁第四頁，共41頁。OR3 5v7v1v2v3v4e1e2e3e4e5e6e7a9v1v2v3v4v5v6a1a2a8a4a3a5a6a7a10e7第4頁/共41頁第五頁，共41頁。OR3 6qvdVv2)(第5頁/共41頁第六頁，共41頁。OR3 7第6頁/共41頁第七頁，共41頁。OR3 8第7頁/共41頁第八頁，共41頁。OR3 9第8頁/共41頁第九頁，

2、共41頁。OR3 10第9頁/共41頁第十頁，共41頁。OR3 11nii12步。第10頁/共41頁第十一頁，共41頁。OR3 12V2(v1,6）)()(min0PwPwP路P0的權(quán)稱為(chn wi)從vs到vt的距離，記為：d（ vs，vt ）第11頁/共41頁第十二頁，共41頁。OR3 13n最短路算法最短路算法nDijkstra算法算法 ：有向圖：有向圖 ，wij0n一般結(jié)論：一般結(jié)論：nDijkstra算法基本算法基本(jbn)思想思想:n采用標(biāo)號法采用標(biāo)號法: P標(biāo)號和標(biāo)號和T標(biāo)號標(biāo)號nP標(biāo)號：已確定出最短路的節(jié)點(diǎn)標(biāo)號：已確定出最短路的節(jié)點(diǎn)(永久性標(biāo)號永久性標(biāo)號)。nT標(biāo)號：未確

3、定出最短路的節(jié)點(diǎn)，但表示其距離的上限標(biāo)號：未確定出最短路的節(jié)點(diǎn)，但表示其距離的上限(試探試探性標(biāo)號性標(biāo)號)。n算法的每一步都把某一點(diǎn)的算法的每一步都把某一點(diǎn)的T標(biāo)號改為標(biāo)號改為P標(biāo)號直至改完為止標(biāo)號直至改完為止.nSi：P標(biāo)號節(jié)點(diǎn)的集合。標(biāo)號節(jié)點(diǎn)的集合。n 的最短路到的最短路到isjsvvisvvjisvvvvv,.,.,.,第12頁/共41頁第十三頁，共41頁。OR3 14ijijjwvPvTvT)(),(min)()(min)(iivTvP第13頁/共41頁第十四頁，共41頁。OR3 15第14頁/共41頁第十五頁，共41頁。OR3 16wvvvvijisijsjiisvvjisddvvv

4、vvvvjs),(),(,.,.,.,.,min最短路最短路的最短路到第15頁/共41頁第十六頁，共41頁。OR3 17dsj)1(dsj)2(第16頁/共41頁第十七頁，共41頁。OR3 18到各點(diǎn)的最短路。即為則該有：，步，對所有的若進(jìn)行到某一步，如第對（vvvdvvdvvdwvvdvvdwvvdsjskjskjskijistijstsjjspjkpjktpj),(),(),(.,21),.,2 , 1(),(),(,.,2),.,2 , 1(),()1()1()()1(min第17頁/共41頁第十八頁，共41頁。OR3 19wdjj1)1(1)()1(1)(1minwddijtiitjd

5、dkjkj)1(1)(1dkj)(1第18頁/共41頁第十九頁，共41頁。OR3 20第19頁/共41頁第二十頁，共41頁。OR3 21025-30-2406400-3047203-10025-3020-3611020-36615020-3361410020-336910020-336910wdjj1) 1 (1)() 1 (1)2(1minwddijiij)min()2(1)3(1wddijiijddjj)6(1)5(1第20頁/共41頁第二十一頁，共41頁。OR3 22第21頁/共41頁第二十二頁，共41頁。OR3 23第22頁/共41頁第二十三頁，共41頁。OR3 24第23頁/共41頁

6、第二十四頁，共41頁。OR3 25vsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)第24頁/共41頁第二十五頁，共41頁。OR3 26第25頁/共41頁第二十六頁，共41頁。OR3 27第26頁/共41頁第二十七頁，共41頁。OR3 280),(),(vvvvijjiffjiij)(),(),(fvvvvvjssjffjssj)(),(),(fvvvvvtjjtffjttj)( fv第27頁/共41頁第二十八頁，共41頁。OR3 29)( fv)()(),(0)()(),(0tifvtsisifvAffvvcfjiijjiiji

7、j第28頁/共41頁第二十九頁，共41頁。OR3 30.,),(1111111111）的截集，記為（的弧的全體稱為分離指向，則把從且使得，和分成兩部分的點(diǎn)集截集：如果將VVvvVVVVVvVvVVtstsVCAVDV1V1V1V1VV*1*1,第29頁/共41頁第三十頁，共41頁。OR3 31第30頁/共41頁第三十一頁，共41頁。OR3 32n則稱 為從vs到vt的（關(guān)于f的）增廣鏈。 fijf cfcfijijijij00),(),(vvvvjiji第31頁/共41頁第三十二頁，共41頁。OR3 33的可行流要大，重復(fù)這個過程，直到不存在關(guān)于該流的增廣鏈時就的得到了最大流。第32頁/共41

8、頁第三十三頁，共41頁。OR3 34可行流f 是最大流的充分必要條件(b yo tio jin)是不存在從 到 可行(kxng)流f 是最大流的充分必要條件是不存在從 到 可行流f 是最大流的充分必要條件是不存在從 f*f*第33頁/共41頁第三十四頁，共41頁。OR3 35f* ffcijijij*minmin),(min 0 ),(),(),(*vvfvvfvvffjiijjiijjiijij f*f*f*f*f*f*第34頁/共41頁第三十五頁，共41頁。OR3 36f*必必是是最最大大流流。于于是是）（所所以以，）（）（顯顯然然有有：）于于是是得得截截集集（記記的的增增廣廣鏈鏈，故故因因?yàn)闉椴徊淮娲嬖谠陉P(guān)關(guān)于于則則令令且且若若則則令令且且若若令令fVVfVVvvVVvvcfVVVVVvfVvfVvVvcfVVvcvVjijiijijtjjiijijijs*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1i*1,)(,),(0,),(.,.,0,v 第35頁/共41頁第三十六頁，共41頁。OR3 37第36頁/共41頁第三十七頁，共41頁。OR3 38第37頁/共41頁第三十八頁，共