《最大流問題》PPT課件

《《最大流問題》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《最大流問題》PPT課件（33頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、圖與網(wǎng)絡(luò)分析（二）最大流問題吳 海 佳勤 務(wù) 指 揮 系 部 隊(duì) 管 理 教 研 室 最 大 流 問 題 是 一 類 應(yīng) 用 極 為 廣 泛 的 問 題 ， 例 如 在 交通 運(yùn) 輸 網(wǎng) 絡(luò) 中 有 人 流 、 車 流 、 貨 物 流 ， 供 水 網(wǎng) 絡(luò) 中有 水 流 ， 金 融 系 統(tǒng) 中 有 現(xiàn) 金 流 ， 通 信 系 統(tǒng) 中 有 信 息流 ， 管 道 運(yùn) 輸 中 的 石 油 流 ， 等 等 。 20世 紀(jì) 50年 代 福 特 (Ford)、 富 克 遜 (Fulkerson)建 立的 “ 網(wǎng) 絡(luò) 流 理 論 ” ， 是 網(wǎng) 絡(luò) 應(yīng) 用 的 重 要 組 成 部 分 。 容量網(wǎng)絡(luò)： 容 量

2、： 設(shè) 一 個(gè) 賦 權(quán) 有 向 圖 D=（ V, E） ,在 V中 指 定 一個(gè) 發(fā) 點(diǎn) vs和 一 個(gè) 收 點(diǎn) vt ,其 它 的 點(diǎn) 叫 做 中 間 點(diǎn) 。 對 于 D中 的 每 一 條 弧 （ vi , vj） E ,都 有 一 個(gè) 非 負(fù) 數(shù) cij（ 即每 條 弧 的 最 大 可 能 負(fù) 載 ） ， 叫 做 弧 的 容 量 。 容 量 網(wǎng) 絡(luò) ： 對 所 有 的 弧 都 給 出 了 容 量 的 有 向 網(wǎng) 絡(luò) ，記 做 D=（ V， E， C） 。一、基本概念 容量網(wǎng)絡(luò)案例有 一 個(gè) 管 道 網(wǎng) 絡(luò) ， 使 用 這 個(gè) 網(wǎng) 絡(luò) 可 以 把 石 油 從 采 地 運(yùn) 送 到 其 他一 些

3、 點(diǎn) ， 這 個(gè) 網(wǎng) 絡(luò) 的 一 部 分 如 下 圖 所 示 。 由 于 管 道 的 直 徑 的 變化 ， 它 的 各 段 管 道 （ vi,vj） 的 容 量 cij也 是 不 一 樣 的 。 cij的 單 位為 萬 加 侖 /小 時(shí) 。 如 果 使 用 這 個(gè) 網(wǎng) 絡(luò) 系 統(tǒng) 從 采 地 v1向 某 地 v7運(yùn)送 石 油 ， 問 每 小 時(shí) 最 多 能 運(yùn) 送 多 少 加 侖 石 油 ？一、基本概念6 3 52 2 2 4 1 26 3v1 v2 v7v4 v3 v6v5 一、基本概念流與可行流： 弧 上 的 流 ： 網(wǎng) 絡(luò) 中 加 在 弧 上 的 負(fù) 載 量 ， 是 指 定 義 在弧 集

4、 合 E上 的 一 個(gè) 函 數(shù) ， 記 為 f(vi ,vj) =fij 。 圖 上 的 流 ： 加 在 網(wǎng) 絡(luò) 中 各 條 弧 上 的 一 組 負(fù) 載 量 （ 即定 義 在 弧 集 上 的 一 個(gè) 函 數(shù) ） ， 記 為 f=f(vi ,vj) =fij 。 零 流 ： 網(wǎng) 絡(luò) 上 所 有 弧 上 的 流 均 為 0， 則 稱 相 應(yīng) 的 圖 上的 流 為 零 流 。 一、基本概念流與可行流： 可 行 流 ： 在 容 量 網(wǎng) 絡(luò) 上 ， 滿 足 容 量 限 制 條 件 和 平 衡條 件 的 流 為 可 行 流 ： 容 量 限 制 條 件 ： 對 每 條 弧 (Vi,Vj),有 0 fij C

5、ij 平 衡 條 件 ： 對 中 間 點(diǎn) Vi, 有 fij= fki 對 發(fā) 、 收 點(diǎn) Vs， Vt有 fsj= fkt=v(f) v(f)為 這 個(gè) 可 行 流 的 流 量 ， 即 發(fā) 點(diǎn) 的 凈 輸 出 量 或 收 點(diǎn)的 凈 輸 入 量 。 所 謂 最 大 流 問 題 就 是 在 容 量 網(wǎng) 絡(luò) 中 ， 尋 找 流 量 最 大的 可 行 流 。 一、基本概念各種?。?對 于 可 行 流 f=fij ， 我 們 把 網(wǎng) 絡(luò) 中 使 fij= cij的 弧 稱 為 飽和 弧 ， 使 fij0的 弧 稱 為 非 零 流 弧 一、基本概念容量網(wǎng)絡(luò)、流量網(wǎng)絡(luò)和殘余網(wǎng)絡(luò)的關(guān)系：容 量 網(wǎng) 絡(luò) =流

6、 量 網(wǎng) 絡(luò) +殘 余 網(wǎng) 絡(luò)6 3 52 2 2 4 1 26 3v1 v2 v7v4 v3 v6v5容 量 網(wǎng) 絡(luò) 一、基本概念6 3 52 2 2 41 26 3v1 v2 v7v4 v3 v6v5容 量 網(wǎng) 絡(luò) 4 3 50 2 0 21 26 3v1 v2 v7v4 v3 v6v5 2 0 02 2 2 20 00 0v1 v2 v7v4 v3 v6v5殘 余 網(wǎng) 絡(luò) 流 量 網(wǎng) 絡(luò) 4 3 50 2 0 21 26 3v1 v2 v7v4 v3 v6v5 一、基本概念增廣路： 從 殘 余 網(wǎng) 絡(luò) 中 找 到 一 條 從 起 點(diǎn) 到 終 點(diǎn) 的 鏈 路 ， 該 鏈 路就 是 增 廣

7、路 ； 增 廣 路 的 最 大 流 量 取 決 于 組 成 該 鏈 路 的 各 弧 的 最 小 容量 。 4 3 50 2 0 21 26 3v1 v2 v7v4 v3 v6v5殘 余 網(wǎng) 絡(luò) 增 廣 路2 2 2 二、最大流問題尋找最大流的思路：定 理 ： 可 行 流 f是 最 大 流 ， 當(dāng) 且 僅 當(dāng) 不 存 在 從 起 點(diǎn) 到 終 點(diǎn)的 關(guān) 于 f的 可 增 廣 鏈 。1 v1 v2 v4v31 111 二、最大流問題尋找最大流的思路： 初 始 時(shí) ， 流 量 網(wǎng) 絡(luò) 的 流 量 為 0， 殘 余 網(wǎng) 絡(luò) =容 量 網(wǎng) 絡(luò) ； 不 斷 從 殘 余 網(wǎng) 絡(luò) 中 尋 找 增 廣 路 ， 將

8、 增 廣 路 的 最 大 流 量賦 予 流 量 網(wǎng) 絡(luò) ； 直 至 殘 余 網(wǎng) 絡(luò) 中 找 不 到 增 廣 路 ， 流 量 網(wǎng) 絡(luò) 的 流 量 最 大1 v1 v2 v4v31 111 二、最大流問題尋找最大流的思路： 初 始 時(shí) ， 流 量 網(wǎng) 絡(luò) 的 流 量 為 0， 殘 余 網(wǎng) 絡(luò) =容 量 網(wǎng) 絡(luò) ； 不 斷 從 殘 余 網(wǎng) 絡(luò) 中 尋 找 增 廣 路 ， 將 增 廣 路 的 最 大 流 量賦 予 流 量 網(wǎng) 絡(luò) ； 直 至 殘 余 網(wǎng) 絡(luò) 中 找 不 到 增 廣 路 ， 流 量 網(wǎng) 絡(luò) 的 流 量 最 大1v1 v2 v4 v31 111 找 到 v1-v2-v3-v4這 條 增 廣

9、 路 ， 最大 流 量 為 1； 二、最大流問題尋找最大流的思路： 初 始 時(shí) ， 流 量 網(wǎng) 絡(luò) 的 流 量 為 0， 殘 余 網(wǎng) 絡(luò) =容 量 網(wǎng) 絡(luò) ； 不 斷 從 殘 余 網(wǎng) 絡(luò) 中 尋 找 增 廣 路 ， 將 增 廣 路 的 最 大 流 量賦 予 流 量 網(wǎng) 絡(luò) ； 直 至 殘 余 網(wǎng) 絡(luò) 中 找 不 到 增 廣 路 ， 流 量 網(wǎng) 絡(luò) 的 流 量 最 大0v1 v2 v4 v30 101 找 到 v1-v2-v3-v4這 條 增 廣 路 ， 最大 流 量 為 1； 將 該 增 廣 路 最 大 流 量 賦 予 流 量 網(wǎng) 絡(luò) ，得 到 新 的 殘 余 網(wǎng) 絡(luò) ； 二、最大流問題尋找最

10、大流的思路： 初 始 時(shí) ， 流 量 網(wǎng) 絡(luò) 的 流 量 為 0， 殘 余 網(wǎng) 絡(luò) =容 量 網(wǎng) 絡(luò) ； 不 斷 從 殘 余 網(wǎng) 絡(luò) 中 尋 找 增 廣 路 ， 將 增 廣 路 的 最 大 流 量賦 予 流 量 網(wǎng) 絡(luò) ； 直 至 殘 余 網(wǎng) 絡(luò) 中 找 不 到 增 廣 路 ， 流 量 網(wǎng) 絡(luò) 的 流 量 最 大0v1 v2 v4 v30 101 找 到 v1-v2-v3-v4這 條 增 廣 路 ， 最大 流 量 為 1； 將 該 增 廣 路 最 大 流 量 賦 予 流 量 網(wǎng) 絡(luò) ，得 到 新 的 殘 余 網(wǎng) 絡(luò) ； 殘 余 網(wǎng) 絡(luò) 中 找 不 到 增 廣 路 了 。 二、最大流問題問題出在

11、哪里？0v1 v2 v4v30 101 找 到 v1-v2-v3-v4這 條 增 廣 路 ， 最大 流 量 為 1； 將 該 增 廣 路 最 大 流 量 賦 予 流 量 網(wǎng) 絡(luò) ，得 到 新 的 殘 余 網(wǎng) 絡(luò) ； 殘 余 網(wǎng) 絡(luò) 中 找 不 到 增 廣 路 了 。0 v1 v2 v4v31 000 在 從 v1-v2時(shí) ， 下 一 步 有 兩 種 選 擇 ，需 要 回 溯 窮 舉 所 有 路 徑 ， 算 法 效 率 將很 低 。 二、最大流問題反向容量方法 通 過 標(biāo) 記 反 向 容 量 ， 給 算 法 留 有 后 悔 的 余 地 ；1v1 v2 v4 v31 111 1/0v1 v2 v4

12、v31/0 1/01/01/0 二、最大流問題反向容量方法 在 尋 找 到 一 條 增 廣 路 的 最 大 流 量 后 ， 將 殘 余 網(wǎng) 絡(luò) 中 該增 廣 路 各 弧 的 正 向 容 量 減 去 該 最 大 流 量 ， 同 時(shí) 在 反 向容 量 中 添 加 該 最 大 流 量 。1/0v1 v2 v4 v31/0 1/01/01/0 0/1v1 v2 v4v30/1 1/00/11/0 二、最大流問題反向容量方法 當(dāng) 某 條 弧 的 反 向 容 量 大 于 零 ， 則 增 廣 路 可 包 含 該 弧 的反 向 弧 。 尋 找 該 增 廣 路 的 最 大 流 量 ， 將 該 增 廣 路 中 的

13、 正 向 弧 中正 向 容 量 減 去 該 流 量 ， 同 時(shí) 反 向 容 量 加 上 該 流 量 ； 將該 增 廣 路 中 的 反 向 弧 中 ， 反 向 容 量 減 去 該 流 量 ， 同 時(shí)正 向 容 量 加 上 該 流 量 。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 軍事案例（軍用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題6 3 52 2 2 41 26 3v1 v2 v7v4 v3 v6v5 軍事案例（軍

14、用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題6/0 3/0 5/02/0 2/02/0 4/01/0 2/06/0 3/0v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題3/3 0/3 2/32/0 2/02/0 4/01/0 2/06/0 3/0v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題1/5 0/3 0/50/2 0/22/0 4/01/0 2/06/0 3/0v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題1/5 0/3 0/50/2 0/20/2 2/21/0 2/04/2 1/2v

15、1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題1/5 0/3 0/50/2 0/20/2 1/30/1 2/03/3 1/2v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題1/5 0/3 0/50/2 0/20/2 1/30/1 0/21/5 1/2v1 v2 v7v4 v3 v6v5 軍事案例（軍用輸油管道網(wǎng)設(shè)計(jì)）：二、最大流問題1/5 0/3 0/50/2 0/20/2 1/30/1 0/21/5 1/2v1 v2 v7v4 v3 v6v5最大流量為？ 四、求最大流問題的實(shí)戰(zhàn)例1：求 下 圖 所 示 網(wǎng) 絡(luò) 中 的 最

16、 大 流 ， 弧 旁 數(shù) 為 ),( 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) 四、求最大流問題的實(shí)戰(zhàn)例1：求 下 圖 所 示 網(wǎng) 絡(luò) 中 的 最 大 流 ， 弧 旁 數(shù) 為 ),( 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 四、求最大流問題的實(shí)戰(zhàn)例2：求 如 圖 所 示 的 網(wǎng) 絡(luò) 的 最 大 流 。 (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 四、求最大流問題的實(shí)戰(zhàn)例3：求 下 圖 所 示 網(wǎng) 絡(luò) 中 的 最 大 流 。 6vs v1 vt v2 v3 10 6 v4 5 1 7 69 3 5 四、求最大流問題的實(shí)戰(zhàn)例4：求 下 圖 所 示 網(wǎng) 絡(luò) 中 的 最 大 流 。6 3 52 2 2 41 26 3v1 v2 v7v4 v3 v6v5