圖與網(wǎng)絡(luò)-西安電子科技大學(xué)經(jīng)濟(jì)管理學(xué)院-文庫吧在線文庫
【正文】 步驟 表 19l關(guān)于 fl－ 1的可增容最短路 pl最短路長︱ pl︱可調(diào)容量l（ vt）系統(tǒng)容量v（ f）總費(fèi)用1 v1v4v6v7 10 1 1 102 v1v4v7 11 2 3 323 v1v4v3v6v7 12 2 5 564 v1v4v3v5v7 16 1 6 725 v1v2v5v7 17 3 9 1236 v1v2v3v5v7 22 1 10 145 對 于 圖 18的求解 過 程可用表 20中之定理內(nèi)容來解 釋 此算法原理。 將 N上所有流量等于 v0的可行流中費(fèi)用最小的可行流 f稱為流量為 v0的最小費(fèi)用流，進(jìn)一步當(dāng) v0又是N中最大流的流量時，則稱此 f為最小費(fèi)用最大流。（ 2）調(diào)整規(guī)則： 1o 若（ vi， vj）為順向弧，則對 pl路徑的順向弧作調(diào)整，其調(diào)整量 △ ij＝ fij＋ l（ v）； 2o 若（ vi， vj）為逆向弧，則對 pl途經(jīng)的逆向弧作調(diào)整，其調(diào)整量 △ ji＝ fji－ l（ v）； 3o G中不在 pl路上的各弧不作調(diào)整。3．順向弧、逆向弧與可增路 def11：設(shè) f是網(wǎng)絡(luò) N的一可行流， P是 N中從 vs到 vt的一條路，對于路 P途經(jīng)的各弧，若弧的方向與路的方向相同，則稱該弧為順向弧，若弧的方向與路的方向相反，則稱該弧為逆向弧。表 16 （例 6求解價(jià)格）5=i=mn+1167。V2V1V5V4V6V3V2V1V5V4V6V3 V2V1V5V4V6V3（ a） （ b） （ c） 圖 五def 8： 若 T是圖 G的一個生成子圖而且又是一 棵樹，則稱樹 T是圖 G的一個生成樹（又稱支 撐樹）；又若樹 T=(V1,E1)為圖 G=(V,E,W) 的 一個生成樹，令 稱為樹 T的權(quán) （或長度），則 G中具最小權(quán)的生成樹稱為 G 的最小生成樹，亦即若有 則有 T* 為 G 的最小生成樹，此中 F為 G的全 體生成樹的集合。5 1 2圖（一圖（一））表一（例表一（例 1 求解過程求解過程 ））例 2 求如下 G之最小路V1V4V2 V6 V8V5 V7333V366661 17圖圖 二二7 42解解 表表 二二表三表三 （例（例 2求解過程）求解過程）由表三知 V1 V8最短路 P1： V8 V6 V2 V1最短路 P2： V8 V6 V5 V3 V2 V1 最短路長 |P1|=2+7+4=13 |P2|=2+3+3+1+4=13 447123 3 2（三）通信線路布設(shè)問題（教材 P209）例 3. 甲、乙兩地之間的公路網(wǎng)絡(luò)如圖三，電信公司準(zhǔn)備在甲、乙兩地沿公路沿線架設(shè)一光纜線，問應(yīng)如何架設(shè)此線路方案，以使光纜線路架設(shè)總長度最短？圖圖 三三解：本例之一步可達(dá)距離陣如解：本例之一步可達(dá)距離陣如 G={V,E,W},V={V 1V2V3V4V5V6V7}， 本例本例 G為無向圖，求解過程見表四為無向圖，求解過程見表四W=表四表四 （例（例 3求解過程）求解過程）① 由表四可得 最短路 P： V7 V6 V5 V3 V1 最短距離 |P|=10+4+2+6=22 ② 還可得到自 V1（ 甲）到任一中間點(diǎn)之最短路，例如 V1 V4 最短路由表四可知為 P14 V4 V5 V3 V1 |P14|=186 2 4 10（ 四）設(shè)備更新問題（教材 P212） 例 4. 某公司設(shè)備管理部門欲制定一個五年期某設(shè)備的更新計(jì)劃，要求給出這五年中購置該設(shè)備的年份及購置新設(shè)備的使用年限。 2 算法思想： 設(shè) G中從 Vs到 Vt的最小路 P： Vs… Vj… Vk… Vt，則由上述命題知： P不僅是從 Vs到 Vt的最小路，而且從 Vs到 P中任意中間點(diǎn)的最短路也在 P上，為此可采用如下求解思路： ⑴ 為求得 Vs到 Vt的最短路，可先求得 Vs到中間點(diǎn)的最短路，然后由中間點(diǎn)再逐步過渡到終點(diǎn) Vt。V1 V3V2 V4V1V2 V4V1 V3V2 V4 （（ a）） 圖圖 G （（ b）） 圖圖 G1 （（ c）） 圖圖 G24 賦權(quán)圖（加權(quán)圖）與網(wǎng)路def 5： 設(shè) G是一個圖（或有向圖），若對 G的每一條邊（或?。?eij都賦予一實(shí)數(shù) ωij， 稱其為該邊（?。┑臋?quán)，則 G連同其他弧上的權(quán)集合稱為一個賦權(quán)圖，記作 G= (V, E, W) 或 G= (V, A, W) ， 此中 W={ω ij}， ωij為對應(yīng)邊（?。?eij的權(quán)。 如右圖之（ a），右圖之（ b） 不是簡單圖。l 若 G為簡單圖，且 G中每個點(diǎn)對之間均有一條邊相連，則稱 G為完全圖。若 G= (V, E, W) （ 或 (V, A, W) ） 為賦權(quán)圖，且在 G的 V中指定一個發(fā)點(diǎn)（常記為 Vs） 和一個收點(diǎn)（記為 Vt）， 其余點(diǎn)稱為中間點(diǎn)，則稱這樣指定了發(fā)點(diǎn)與收點(diǎn)的賦權(quán)圖 G為網(wǎng)絡(luò)。 ⑵ 在計(jì)算過程中，需要把 V中 “ 經(jīng)判斷為最短路 P途徑之點(diǎn) i” 和 “ 尚未判斷是否為最短路 P途徑 之點(diǎn) j” 區(qū)分開來，可設(shè)置集合 I和 J,前者歸入 I， 后者歸入 J， 并令算法初始時， I中僅包含 Vs， 其他點(diǎn)全在 J中，然后隨著求解過程的進(jìn) 行， I中的點(diǎn)逐漸增加（相應(yīng) J中的點(diǎn)逐漸減 少），直到終點(diǎn) Vt歸入 I（ 相應(yīng) J=φ ）， 此時 迭代結(jié)束。 在此五年中購置該設(shè)備的年初價(jià)格見表五，設(shè)備使用不同年限的維護(hù)費(fèi)見表六。 Th1： 設(shè) T=(V,E)是 |V|≥ 3的一個無向圖，則下列六個關(guān)于樹的定義是等價(jià)的：⑴ T連通且無圈⑵ T的任何兩個頂點(diǎn)間均必有一條且僅有一條通 路相連⑶ T連通且有 n1條邊，此中 n= |V|⑷ T有 n1條邊且無圈 ， 此中 n= |V|⑸ T無圈，但在 T中任兩個不相鄰的頂點(diǎn)間添加 一條邊，則可構(gòu)成一條回路⑹ T連通，但去掉任一條邊后
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1