運(yùn)籌學(xué)_圖與網(wǎng)絡(luò)分析(已改無(wú)錯(cuò)字)
2023-06-26 22:15:14 本頁(yè)面
【正文】 k(m+1)都成立則逆向追蹤 ， 找出最短路 ， 算法終止 ；若存在 L1k(m) L1k(m+1), 則令 m=m+1， 返回第 2步 ? 求從 v1到 v4的最短路 v1 v2 v3 v4 3 2 2 1 4 5 (0) v1 v2 v3 v4 3 2 2 1 4 5 (1,2) (1,3) (2,1) (0) v1 v2 v3 v4 3 2 2 1 4 5 (3,1) (1,3) (2,0) 課堂練習(xí) : P225 7 ? 無(wú)向圖 v1 v2 v3 v4 v5 2 3 1 4 1 5 3 將算法稍作修改：在未標(biāo)號(hào)點(diǎn)集中 找出與標(biāo)號(hào)點(diǎn) vi有邊相連 的點(diǎn) vj 網(wǎng)絡(luò)最大流問(wèn)題 10856341117V 1V 2V 3V 4V 5V 635下圖表示從產(chǎn)地 v1到銷(xiāo)地 v6的交通網(wǎng) ， 弧旁邊的數(shù)字表示這條運(yùn)輸線(xiàn)的最大通過(guò)能力 ， 產(chǎn)品經(jīng)過(guò)這個(gè)交通網(wǎng)從 v1運(yùn)到 v6， 要求制定一個(gè)運(yùn)輸方案使得從 v1運(yùn)到 v6的產(chǎn)品數(shù)量最多 。 (5)(3)( 2 )( 3 )(3)(1) (1)(6)(2)V 1V 2V 3V 4V 5V 6(2)基本概念 ?網(wǎng)絡(luò)與流 對(duì)有向圖 D=(V,A)， 如果其中指定某一點(diǎn) vs為發(fā)點(diǎn) ， 另一點(diǎn) vt為收點(diǎn) ，其他點(diǎn)則稱(chēng)為中間點(diǎn) 。 若對(duì)于有向圖 D中的每一條弧 (vi,vj) ∈ A， 都有一個(gè)數(shù) c(vi,vj) ≥0與它對(duì)應(yīng) ， 稱(chēng) c為弧的容量 ， 記為 D=(V,A ,C) 定義在弧集合 A上的一個(gè)函數(shù) f={f(vi,vj)}稱(chēng)為網(wǎng)絡(luò) D上的流 ， 并稱(chēng) f(vi,vj)為弧 (vi,vj)上的流量 ， 簡(jiǎn)記為 fij ? 可行流： 滿(mǎn)足下述條件的流稱(chēng)為可行流： (1)容量限制：對(duì)于每一個(gè)弧 (vi,vj) ∈ A， 0≤fij ≤ cij (2)平衡條件： 對(duì)于中間點(diǎn)：流出量等于流入量，即對(duì)于每個(gè) i(i≠s,t)有 對(duì)于發(fā)點(diǎn)： )f(vffA)v,v(jsA)v,v(sjsjjs?? ????)f(vffA)v,v(jtA)v,v(tjtjjt??? ????對(duì)于收點(diǎn)： 稱(chēng) v(f)為可行流的流量，發(fā)點(diǎn)的凈輸出量等于收點(diǎn)的凈輸入量。 最大流問(wèn)題就是要找出一個(gè)可行流使得 v(f)達(dá)到最大 0ffA)v,v(jiA)v,v(ijijji?? ????? 飽和弧和非飽和弧 網(wǎng)絡(luò) D=(V,A ,C)， f={f(vi,vj)}是 D的可行流，則如果某一條弧 (vi,vj) ∈ A滿(mǎn)足 (1) fij = cij ，則稱(chēng) (vi,vj)為飽和?。? (2) fij cij ， 則稱(chēng) (vi,vj)為非飽和弧； (3) fij =0 ， 則稱(chēng) (vi,vj)為零流弧； (4) fij 0 ， 則稱(chēng) (vi,vj)為非零流?。? ? 前向弧和后向弧 網(wǎng)絡(luò) D中與給定的鏈 方向一致的弧 稱(chēng)為前向弧，記作 ； 與給定的鏈方向相反的弧稱(chēng)為后向弧，記作 ； ?????? 增廣鏈 (可擴(kuò)充鏈 ) stf D v vDf???假 設(shè) 是 有 向 圖 的 一 個(gè) 可 行 流 ， 是 從 到 的 一 條 鏈 ，如 果 滿(mǎn) 足 下 面 的 條 件 ， 則 稱(chēng) 為 關(guān) 于 可 行 流 的 增 廣 鏈( 1 ) ( , ) 0 ,i j ij ijv v f c????? ? ?在 弧 上 ， 即 中 的 每 一 條 弧 是 非 飽 和 弧 ；( 2) ( , ) 0 ,i j ij ijv v f c????? ? ?在 弧 上 ， 即 中 的 每 一 條 弧 是 非 零 弧 ；是一條增廣鏈且），（），），（，），（，），（，（）為一條鏈，，，（中在例????}v4v5{}v6v5v4v3v3v2v2v1{v6v5,v4v3v2v1,5?????(5)(3)( 2 )( 3 )(3)(1)(6)(2)V 1V 2V 3V 4V 5V 6 (1) (2)4 0 0 2 1 大家想想：增廣鏈的意義在哪里？ ? 根據(jù)定理，對(duì)于給定的可行流 f，要判斷它是不是最大流只需要判斷 D中有沒(méi)有關(guān)于 f的增廣鏈。 ? 如果有，則需要對(duì) f進(jìn)行改進(jìn)；如果沒(méi)有增廣鏈，則已經(jīng)得到最大流。 定理 ：可行流 f*是最大流，當(dāng)且僅當(dāng)不存在關(guān)于 f*的增廣鏈 尋找最大流的標(biāo)號(hào)法 ? 網(wǎng)絡(luò) D中的點(diǎn)分為兩類(lèi) ， 一類(lèi)是標(biāo)號(hào)點(diǎn) (屬于 V1* )， 一類(lèi)是非標(biāo)號(hào)點(diǎn) (不屬于 V1* )
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1