《《最大流問題》PPT課件》由會員分享，可在線閱讀，更多相關《《最大流問題》PPT課件（33頁珍藏版）》請在裝配圖網上搜索。
1、圖與網絡分析（二）最大流問題吳 海 佳勤 務 指 揮 系 部 隊 管 理 教 研 室 最 大 流 問 題 是 一 類 應 用 極 為 廣 泛 的 問 題 ， 例 如 在 交通 運 輸 網 絡 中 有 人 流 、 車 流 、 貨 物 流 ， 供 水 網 絡 中有 水 流 ， 金 融 系 統(tǒng) 中 有 現 金 流 ， 通 信 系 統(tǒng) 中 有 信 息流 ， 管 道 運 輸 中 的 石 油 流 ， 等 等 。 20世 紀 50年 代 福 特 (Ford)、 富 克 遜 (Fulkerson)建 立的 “ 網 絡 流 理 論 ” ， 是 網 絡 應 用 的 重 要 組 成 部 分 。 容量網絡： 容 量
2、： 設 一 個 賦 權 有 向 圖 D=（ V, E） ,在 V中 指 定 一個 發(fā) 點 vs和 一 個 收 點 vt ,其 它 的 點 叫 做 中 間 點 。 對 于 D中 的 每 一 條 弧 （ vi , vj） E ,都 有 一 個 非 負 數 cij（ 即每 條 弧 的 最 大 可 能 負 載 ） ， 叫 做 弧 的 容 量 。 容 量 網 絡 ： 對 所 有 的 弧 都 給 出 了 容 量 的 有 向 網 絡 ，記 做 D=（ V， E， C） 。一、基本概念 容量網絡案例有 一 個 管 道 網 絡 ， 使 用 這 個 網 絡 可 以 把 石 油 從 采 地 運 送 到 其 他一 些
3、 點 ， 這 個 網 絡 的 一 部 分 如 下 圖 所 示 。 由 于 管 道 的 直 徑 的 變化 ， 它 的 各 段 管 道 （ vi,vj） 的 容 量 cij也 是 不 一 樣 的 。 cij的 單 位為 萬 加 侖 /小 時 。 如 果 使 用 這 個 網 絡 系 統(tǒng) 從 采 地 v1向 某 地 v7運送 石 油 ， 問 每 小 時 最 多 能 運 送 多 少 加 侖 石 油 ？一、基本概念6 3 52 2 2 4 1 26 3v1 v2 v7v4 v3 v6v5 一、基本概念流與可行流： 弧 上 的 流 ： 網 絡 中 加 在 弧 上 的 負 載 量 ， 是 指 定 義 在弧 集
4、 合 E上 的 一 個 函 數 ， 記 為 f(vi ,vj) =fij 。 圖 上 的 流 ： 加 在 網 絡 中 各 條 弧 上 的 一 組 負 載 量 （ 即定 義 在 弧 集 上 的 一 個 函 數 ） ， 記 為 f=f(vi ,vj) =fij 。 零 流 ： 網 絡 上 所 有 弧 上 的 流 均 為 0， 則 稱 相 應 的 圖 上的 流 為 零 流 。 一、基本概念流與可行流： 可 行 流 ： 在 容 量 網 絡 上 ， 滿 足 容 量 限 制 條 件 和 平 衡條 件 的 流 為 可 行 流 ： 容 量 限 制 條 件 ： 對 每 條 弧 (Vi,Vj),有 0 fij C
5、ij 平 衡 條 件 ： 對 中 間 點 Vi, 有 fij= fki 對 發(fā) 、 收 點 Vs， Vt有 fsj= fkt=v(f) v(f)為 這 個 可 行 流 的 流 量 ， 即 發(fā) 點 的 凈 輸 出 量 或 收 點的 凈 輸 入 量 。 所 謂 最 大 流 問 題 就 是 在 容 量 網 絡 中 ， 尋 找 流 量 最 大的 可 行 流 。 一、基本概念各種?。?對 于 可 行 流 f=fij ， 我 們 把 網 絡 中 使 fij= cij的 弧 稱 為 飽和 弧 ， 使 fij0的 弧 稱 為 非 零 流 弧 一、基本概念容量網絡、流量網絡和殘余網絡的關系：容 量 網 絡 =流
6、 量 網 絡 +殘 余 網 絡6 3 52 2 2 4 1 26 3v1 v2 v7v4 v3 v6v5容 量 網 絡 一、基本概念6 3 52 2 2 41 26 3v1 v2 v7v4 v3 v6v5容 量 網 絡 4 3 50 2 0 21 26 3v1 v2 v7v4 v3 v6v5 2 0 02 2 2 20 00 0v1 v2 v7v4 v3 v6v5殘 余 網 絡 流 量 網 絡 4 3 50 2 0 21 26 3v1 v2 v7v4 v3 v6v5 一、基本概念增廣路： 從 殘 余 網 絡 中 找 到 一 條 從 起 點 到 終 點 的 鏈 路 ， 該 鏈 路就 是 增 廣
7、路 ； 增 廣 路 的 最 大 流 量 取 決 于 組 成 該 鏈 路 的 各 弧 的 最 小 容量 。 4 3 50 2 0 21 26 3v1 v2 v7v4 v3 v6v5殘 余 網 絡 增 廣 路2 2 2 二、最大流問題尋找最大流的思路：定 理 ： 可 行 流 f是 最 大 流 ， 當 且 僅 當 不 存 在 從 起 點 到 終 點的 關 于 f的 可 增 廣 鏈 。1 v1 v2 v4v31 111 二、最大流問題尋找最大流的思路： 初 始 時 ， 流 量 網 絡 的 流 量 為 0， 殘 余 網 絡 =容 量 網 絡 ； 不 斷 從 殘 余 網 絡 中 尋 找 增 廣 路 ， 將
8、 增 廣 路 的 最 大 流 量賦 予 流 量 網 絡 ； 直 至 殘 余 網 絡 中 找 不 到 增 廣 路 ， 流 量 網 絡 的 流 量 最 大1 v1 v2 v4v31 111 二、最大流問題尋找最大流的思路： 初 始 時 ， 流 量 網 絡 的 流 量 為 0， 殘 余 網 絡 =容 量 網 絡 ； 不 斷 從 殘 余 網 絡 中 尋 找 增 廣 路 ， 將 增 廣 路 的 最 大 流 量賦 予 流 量 網 絡 ； 直 至 殘 余 網 絡 中 找 不 到 增 廣 路 ， 流 量 網 絡 的 流 量 最 大1v1 v2 v4 v31 111 找 到 v1-v2-v3-v4這 條 增 廣
9、 路 ， 最大 流 量 為 1； 二、最大流問題尋找最大流的思路： 初 始 時 ， 流 量 網 絡 的 流 量 為 0， 殘 余 網 絡 =容 量 網 絡 ； 不 斷 從 殘 余 網 絡 中 尋 找 增 廣 路 ， 將 增 廣 路 的 最 大 流 量賦 予 流 量 網 絡 ； 直 至 殘 余 網 絡 中 找 不 到 增 廣 路 ， 流 量 網 絡 的 流 量 最 大0v1 v2 v4 v30 101 找 到 v1-v2-v3-v4這 條 增 廣 路 ， 最大 流 量 為 1； 將 該 增 廣 路 最 大 流 量 賦 予 流 量 網 絡 ，得 到 新 的 殘 余 網 絡 ； 二、最大流問題尋找最
10、大流的思路： 初 始 時 ， 流 量 網 絡 的 流 量 為 0， 殘 余 網 絡 =容 量 網 絡 ； 不 斷 從 殘 余 網 絡 中 尋 找 增 廣 路 ， 將 增 廣 路 的 最 大 流 量賦 予 流 量 網 絡 ； 直 至 殘 余 網 絡 中 找 不 到 增 廣 路 ， 流 量 網 絡 的 流 量 最 大0v1 v2 v4 v30 101 找 到 v1-v2-v3-v4這 條 增 廣 路 ， 最大 流 量 為 1； 將 該 增 廣 路 最 大 流 量 賦 予 流 量 網 絡 ，得 到 新 的 殘 余 網 絡 ； 殘 余 網 絡 中 找 不 到 增 廣 路 了 。 二、最大流問題問題出在
11、哪里？0v1 v2 v4v30 101 找 到 v1-v2-v3-v4這 條 增 廣 路 ， 最大 流 量 為 1； 將 該 增 廣 路 最 大 流 量 賦 予 流 量 網 絡 ，得 到 新 的 殘 余 網 絡 ； 殘 余 網 絡 中 找 不 到 增 廣 路 了 。0 v1 v2 v4v31 000 在 從 v1-v2時 ， 下 一 步 有 兩 種 選 擇 ，需 要 回 溯 窮 舉 所 有 路 徑 ， 算 法 效 率 將很 低 。 二、最大流問題反向容量方法 通 過 標 記 反 向 容 量 ， 給 算 法 留 有 后 悔 的 余 地 ；1v1 v2 v4 v31 111 1/0v1 v2 v4
12、v31/0 1/01/01/0 二、最大流問題反向容量方法 在 尋 找 到 一 條 增 廣 路 的 最 大 流 量 后 ， 將 殘 余 網 絡 中 該增 廣 路 各 弧 的 正 向 容 量 減 去 該 最 大 流 量 ， 同 時 在 反 向容 量 中 添 加 該 最 大 流 量 。1/0v1 v2 v4 v31/0 1/01/01/0 0/1v1 v2 v4v30/1 1/00/11/0 二、最大流問題反向容量方法 當 某 條 弧 的 反 向 容 量 大 于 零 ， 則 增 廣 路 可 包 含 該 弧 的反 向 弧 。 尋 找 該 增 廣 路 的 最 大 流 量 ， 將 該 增 廣 路 中 的
13、 正 向 弧 中正 向 容 量 減 去 該 流 量 ， 同 時 反 向 容 量 加 上 該 流 量 ； 將該 增 廣 路 中 的 反 向 弧 中 ， 反 向 容 量 減 去 該 流 量 ， 同 時正 向 容 量 加 上 該 流 量 。0/1 v1 v2 v4v30/1 1/00/11/0 0/1v1 v2 v4v31/0 0/10/10/1 二、最大流問題反向容量方法 直 至 找 不 到 增 廣 路 為 止 。0/1v1 v2 v4v31/0 0/10/10/1 軍事案例（軍用輸油管道網設計）：二、最大流問題6 3 52 2 2 41 26 3v1 v2 v7v4 v3 v6v5 軍事案例（軍
14、用輸油管道網設計）：二、最大流問題6/0 3/0 5/02/0 2/02/0 4/01/0 2/06/0 3/0v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網設計）：二、最大流問題3/3 0/3 2/32/0 2/02/0 4/01/0 2/06/0 3/0v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網設計）：二、最大流問題1/5 0/3 0/50/2 0/22/0 4/01/0 2/06/0 3/0v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網設計）：二、最大流問題1/5 0/3 0/50/2 0/20/2 2/21/0 2/04/2 1/2v
15、1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網設計）：二、最大流問題1/5 0/3 0/50/2 0/20/2 1/30/1 2/03/3 1/2v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網設計）：二、最大流問題1/5 0/3 0/50/2 0/20/2 1/30/1 0/21/5 1/2v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網設計）：二、最大流問題1/5 0/3 0/50/2 0/20/2 1/30/1 0/21/5 1/2v1 v2 v7v4 v3 v6v5最大流量為？ 四、求最大流問題的實戰(zhàn)例1：求 下 圖 所 示 網 絡 中 的 最
16、 大 流 ， 弧 旁 數 為 ),( jiji fc(3 ,3)v2v1 v4 v6vs vtv3 (3,0)(5 , 5)(3 , 2) (5 , 4)(5 ,2)(2 , 2) (4 ,2)(3 ,3) v5(2 ,2)(4 ,2) 四、求最大流問題的實戰(zhàn)例1：求 下 圖 所 示 網 絡 中 的 最 大 流 ， 弧 旁 數 為 ),( jiji fc(3 ,3)v2v1 v4v6vs vtv3 (3,0)(5 , 5)(3 , 2) (5 , 4)(5 ,2)(2 , 2) (4 ,2)(3 ,3) v5(2 ,2)(4 ,2) 0/3v2v1 v4v6vs vtv3 3/00/51/2
17、1/43/20/2 2/20/3 v50/22/2 四、求最大流問題的實戰(zhàn)例2：求 如 圖 所 示 的 網 絡 的 最 大 流 。 (5,5)vs v1 vt v2 v3 (6,4) (3,2) v4 (2,2) (5,4) (6,6)(8,6) (4,4) (2,0) (3,3) (2,0) (3,3) v5 四、求最大流問題的實戰(zhàn)例3：求 下 圖 所 示 網 絡 中 的 最 大 流 。 6vs v1 vt v2 v3 10 6 v4 5 1 7 69 3 5 四、求最大流問題的實戰(zhàn)例4：求 下 圖 所 示 網 絡 中 的 最 大 流 。6 3 52 2 2 41 26 3v1 v2 v7v4 v3 v6v5
《最大流問題》PPT課件
