圖論方法建模

1、圖論方法建模 1 歐拉七橋問題2 圖的基本概念3 簡易公路建設(shè)方案4 前線彈藥供應(yīng)11 歐拉七橋問題18世紀在哥尼斯堡城（今俄羅斯加里寧格勒）有一條名叫普萊格爾（Pregel）的河流橫經(jīng)其中，河上有7座橋，將河中的兩個島和河岸連結(jié)。城中的居民經(jīng)常沿河過橋散步，于是提出了一個問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點?北岸南岸中心島東區(qū)21736年歐拉把這個問題的物理背景變換并簡化為一種數(shù)學(xué)設(shè)計（稱作圖）：即把每一塊陸地用一個點來代替，將每一座橋用連接相應(yīng)的兩個點的一條線來代替，從而相當(dāng)于得到一個圖。歐拉證明了這個問題沒有解，并指出歐幾里得幾何并不適用于這個問題，因為橋不

2、涉及“大小”，也不能用“量化計算”來解決。32 圖的基本概念定義 1：有序二元組G=(V, E)稱為圖，其中：V=v1, v2, , vn表示頂點集，E=e1, e2, , em表示邊集。 所謂的圖，直觀的講就是在平面上n個點，把其中的一些點對用線連接起來，不考慮點的位置與曲線的曲直長短，這樣形成的一個關(guān)系結(jié)構(gòu)就是一個圖。如果各條邊都加上方向，則稱為有向圖，否則稱為無向圖。如果有的邊有方向，有的邊無方向，則稱為混合圖。如果圖的每一條邊都對應(yīng)一個實數(shù)，則稱該實數(shù)為對應(yīng)邊的權(quán)，稱該圖為賦權(quán)圖。43 簡易公路建設(shè)方案現(xiàn)代戰(zhàn)爭對后勤保障的依賴程度日漸提高。上世紀九十年代的海灣戰(zhàn)爭，截止1991年2月2

3、7日沙漠風(fēng)暴行動地面作戰(zhàn)結(jié)束時為止，美軍向海灣地區(qū)共運送了48.5萬人，280萬噸部隊裝備，650萬噸成品油料，82.5萬噸的后勤支援物資。5某合同戰(zhàn)術(shù)訓(xùn)練基地為保障即將進行的聯(lián)合軍事演習(xí)，準備在原有的1個油庫的基礎(chǔ)上，再設(shè)立7個固定的燃料補給點。3 簡易公路建設(shè)方案6v1v7v6v2v8v5v3v4油庫與補給點的位置如圖所示，其中油庫位于v1點，補給點位于v2, , v8點。7經(jīng)過前期的測繪工作，如果在油庫和補給點之間修建簡易公路，由于地形不同，每段公路花費如圖，每單位費用為1萬元。請根據(jù)測繪結(jié)果，規(guī)劃一個總造價最低的建設(shè)方案。v1v7v6v2v8v5v3v42573432643617418

4、2總造價最低各補給點到油庫的花費均達到最??？8通路與路徑在圖G中，首尾相接的一串邊稱為通路，邊和頂點都不重復(fù)的通路稱為路徑。v1v2v3v4e1e2e3e4e5通路： W=v1e1v2e2v3e5v1e4v4路徑： P=v1e1v2e2v3e3v4準備知識9定義 2：設(shè)P(u, v)是賦權(quán)圖G中u到v的路徑，則：（1） 為路徑P的權(quán)；（2）從u到v的具有最小權(quán)的路P*(u, v)，稱為u到v的最短路。固定起點的最短路問題每對頂點之間的最短路問題10鄰接矩陣對賦權(quán)圖G，其鄰接矩陣A=(aij)vv，其中：v1v2v3v47521311v1v7v6v2v8v5v3v4257343264361741

5、8212尋找最短路的方法很多，最適合這一問題的是Dijkstra算法。定義d(vj)為從v1到vj的當(dāng)前“距離”Dijkstra算法的過程就是不斷更新d(vj)，最終使得所有d(vj)達到最小。v1v7v6v2v8v5v3v425734326436174182定義d(vj)為從v1到vj的當(dāng)前“距離”13d(vj)v1 v2 v3 v4 v5 v6 v7 v80 1 2 7 4 8 v1v7v6v2v8v5v3v425734326436174182 2 4 7 4 8 14d(vj)v1 v2 v3 v4 v5 v6 v7 v8 2 4 7 4 8 3 7 4 8 v1v7v6v2v8v5v3

6、v42573432643617418215d(vj)v1 v2 v3 v4 v5 v6 v7 v8 3 7 4 8 v1v7v6v2v8v5v3v425734326436174182 6 4 8 916d(vj)v1 v2 v3 v4 v5 v6 v7 v8 6 4 8 9 6 6 9v1v7v6v2v8v5v3v42573432643617418217d(vj)v1 v2 v3 v4 v5 v6 v7 v8 6 6 9 6 9 9v1v7v6v2v8v5v3v42573432643617418218v1v7 6v6 4v2 1v8 9v5 6v3 2 v4 32243611簡易公路建設(shè)方案1

7、9Dijkstra算法算法步驟W表示圖G的帶權(quán)鄰接矩陣，d(vj)表示從v1到vj的只允許經(jīng)過已選出頂點的最短路的權(quán)。（1）令d(vj)=w1j, S=v1, R=VS=v2,vn（2）在R中尋找一個頂點vk，使得置S=Svk， R=VS。若R=，終止算法。（3）修正d(vj)，對R中的每個vj，令轉(zhuǎn)回（2）204 前線彈藥供應(yīng)與我國有陸地邊境的某國近來局勢緊張，為應(yīng)對可能發(fā)生的局部沖突，某裝甲師奉命開赴前線。該師下屬代號為T的某團，裝備有先進的PLZ-05式自行榴彈炮。該團進駐陣地后，發(fā)現(xiàn)臨時設(shè)立的彈藥補給點沒有儲備155mm榴彈炮，距離最近的儲備有該型炮彈的倉庫是后方的S倉庫。團指揮官命令

8、作戰(zhàn)參謀立即著手規(guī)劃運輸線路，要求在3天之內(nèi)完成至少20個基數(shù)的彈藥儲備。21對地圖進行簡化，陣地記為vt，倉庫記為vs，各道路節(jié)點記為v1，v2，v5。道路看做是連接各點的邊，道路每天的通過能力（容量）記為邊的權(quán)值cij。在最后確定的方案中，每條道路的實際流量記為xij 。v1v2v3v5v4vsvt43642522341675網(wǎng)絡(luò)最大流問題：在規(guī)定期限內(nèi)盡可能多地運送物資。綜合地圖和偵察連匯報的情況，作戰(zhàn)參謀發(fā)現(xiàn)，T團距離倉庫S路程較遠，道路情況復(fù)雜，有二級公路，也有臨時鋪設(shè)的簡易公路。由于前線實行交通管制，這些道路全部為單向通行。 。22道路通過能力（容量）記為邊的權(quán)值cij，每條道路的

9、實際流量記為xij 。v1v2v3v5v4vsvt4364252234167523標號算法給定初始可行流 xij （零流），逐漸增大流量，當(dāng)不能增加流量時停止，得到的就是最大流。v1v2v3v5v4vsvt436425223416750000000000000024第一次修改從 vs 到 vt 找到一條路，使得這條路上所有cij 0。修改對應(yīng) xij 的使流量達到最大。v1v2v3v5v4vsvt436425223416750000000000000020122225第二次修改從 vs 到 vt 找到一條路，使得這條路上所有cij 0。修改對應(yīng) xij 的使流量達到最大。v1v2v3v5v4v

10、svt236425021416750002020000002020222226第三次修改從 vs 到 vt 找到一條路，使得這條路上所有cij 0。修改對應(yīng) xij 的使流量達到最大。v1v2v3v5v4vsvt236205021216752022020002002040322427第四次修改從 vs 到 vt 找到一條路，使得這條路上所有cij 0。修改對應(yīng) xij 的使流量達到最大。v1v2v3v5v4vsvt234205021016732022220024002034033128由c4t = c5t = 0，可知不可能再有所有cij 0 的路存在，算法結(jié)束。v1v2v3v5v4vsvt233204020016732022320