圖論方法建模

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

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

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

4、2總造價(jià)最低各補(bǔ)給點(diǎn)到油庫(kù)的花費(fèi)均達(dá)到最??？8通路與路徑在圖G中，首尾相接的一串邊稱為通路，邊和頂點(diǎn)都不重復(fù)的通路稱為路徑。v1v2v3v4e1e2e3e4e5通路： W=v1e1v2e2v3e5v1e4v4路徑： P=v1e1v2e2v3e3v4準(zhǔn)備知識(shí)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的最短路。固定起點(diǎn)的最短路問(wèn)題每對(duì)頂點(diǎn)之間的最短路問(wèn)題10鄰接矩陣對(duì)賦權(quán)圖G，其鄰接矩陣A=(aij)vv，其中：v1v2v3v47521311v1v7v6v2v8v5v3v4257343264361741

5、8212尋找最短路的方法很多，最適合這一問(wèn)題的是Dijkstra算法。定義d(vj)為從v1到vj的當(dāng)前“距離”Dijkstra算法的過(guò)程就是不斷更新d(vj)，最終使得所有d(vj)達(dá)到最小。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簡(jiǎn)易公路建設(shè)方案1

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

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

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

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