運籌學_圖與網(wǎng)絡(luò)分析(參考版)
2025-05-18 22:15本頁面
【正文】 111 1 1 11111( , ) ( , )( , ) ( , )( , )( , )ijijv v V VV V V Vc V Vc V V c?? ?給 定 一 個 截 集 ， 截 集 中 所 有 弧 的 容 量 之 和稱 為 這 個 截 集 的 容 量 ， 記 為 ， 即? 任何一個可行流的流量不會超過任何一個截集的容量，即 11( ) ( , )v f c V V?所有截集中容量最小的是一定是最大流，并且，則使得存在截集絡(luò)的一個可行流，如果網(wǎng)是網(wǎng)絡(luò)假設(shè))V,V(f)V,V(c)f(v)V,V(DDf*1*1**1*1**1*1*?。 { }2ijff ?去 掉 所 有 點 的 標 號 ， 對 新 的 可 行 流回 到 步 驟 ， 重 新 進 行 標 號? ?12m i n ,? ? ??? ?? ?12m i nm i ni j i jijcff?????對 增 廣 鏈 上 的 前 向 弧對 增 廣 鏈 上 的 后 向 弧前向弧 后向弧 用標號法求如下圖所示的網(wǎng)絡(luò)最大流 圖中已經(jīng)給出初始流。 ( , )( , )ij i jij ij i jij i jf v vf f v vf v v???????? ????? ? ??????39。 t s tv v v?重 復 上 面 的 步 驟 ， 一 旦 被 標 上 號 就 得 到 了 一 條 從 到 的 增廣 鏈 ， 轉(zhuǎn) 入 調(diào) 整 過 程vi變?yōu)闃颂柷乙褭z查的點，在 vi旁加上 *以示區(qū)別 如 果 所 有 的 標 號 都 是 已 經(jīng) 檢 查 過 的 ， 但 是 標 號 過 程 無法 進 行 下 去 ， 算 法 結(jié) 束 ， 此 時 的 可 行 流 就 是 最 大 流 。 定理 ：可行流 f*是最大流，當且僅當不存在關(guān)于 f*的增廣鏈 尋找最大流的標號法 ? 網(wǎng)絡(luò) D中的點分為兩類 ， 一類是標號點 (屬于 V1* )， 一類是非標號點 (不屬于 V1* ) ； ? 標號點有兩類一類是已檢查的 ， 一類是未檢查的 。 最大流問題就是要找出一個可行流使得 v(f)達到最大 0ffA)v,v(jiA)v,v(ijijji?? ????? 飽和弧和非飽和弧 網(wǎng)絡(luò) D=(V,A ,C)， f={f(vi,vj)}是 D的可行流，則如果某一條弧 (vi,vj) ∈ A滿足 (1) fij = cij ，則稱 (vi,vj)為飽和弧； (2) fij cij ， 則稱 (vi,vj)為非飽和弧； (3) fij =0 ， 則稱 (vi,vj)為零流弧； (4) fij 0 ， 則稱 (vi,vj)為非零流??； ? 前向弧和后向弧 網(wǎng)絡(luò) D中與給定的鏈 方向一致的弧 稱為前向弧，記作 ； 與給定的鏈方向相反的弧稱為后向弧，記作 ； ?????? 增廣鏈 (可擴充鏈 ) stf D v vDf???假 設(shè) 是 有 向 圖 的 一 個 可 行 流 ， 是 從 到 的 一 條 鏈 ，如 果 滿 足 下 面 的 條 件 ， 則 稱 為 關(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ù)定理，對于給定的可行流 f，要判斷它是不是最大流只需要判斷 D中有沒有關(guān)于 f的增廣鏈。 (5)(3)( 2 )( 3 )(3)(1) (1)(6)(2)V 1V 2V 3V 4V 5V 6(2)基本概念 ?網(wǎng)絡(luò)與流 對有向圖 D=(V,A)， 如果其中指定某一點 vs為發(fā)點 ， 另一點 vt為收點 ，其他點則稱為中間點 。 求從 v1到 v8的最短路 1632611 04103246322V 1V 2V 4V 3V 5V 6V7V 8V 9(0) (1,1) (1,3) (
法律信息相關(guān)推薦
鄂ICP備17016276號-1