圖 的 基 本 概 念 與 模 型樹最 短 路 問 題網(wǎng) 絡 的 最 大 流最 小 費 用 流應 用 舉 例 近 代 圖 論 的 歷 史 可 追 溯 到 18世 紀 的 七 橋 問 題 穿 過Knigsberg城 的 七 座 橋 ， 要 求 每 座 橋 通 過 一 次 且 僅 通 過 一 次 。 這 就 是 著 名 的 “ 哥 尼 斯 堡 7 橋 ” 難 題 。 Euler1736年 證 明 了 不可 能 存 在 這 樣 的 路 線 。 例 1、 有 甲 、 乙 、 丙 、 丁 、 戊 五 個 球 隊 ，它 們 之 間 比 賽 的 情 況 也 可 以 用 圖 表 示 出 來 。V1 V 2 V3 V4V5e5 e4e1 e2 e3e6e7 一 、 圖 基 本 概 念 例 2 某 單 位 儲 存 八 種 化 學 藥 品 ， 其 中 某 些藥 品 是 不 能 存 放 在 同 一 個 庫 房 里 的 。 為 了 反 映這 個 情 況 可 以 用 點 V1,V2,V8分 別 代 表 這 八種 藥 品 ， 若 藥 品 Vi和 藥 品 Vj是 不 能 存 放 在 同一 個 庫 房 的 ， 則 在 Vi和 Vj之 間 連 一 條 線 。 V1 V2 V3 V4 V 5 V8 V7 V6 圖 的 表 示 方 法 ： 一 般 地 ， 當 用 圖 論 研 究 一 個 實 際 問 題 時 ，常 以 頂 點 （ Vertex） 表 示 要 研 究 的 對 象 ， 以它 們 之 間 的 連 線 ， 表 示 某 種 關 系 ， 這 種 連 線稱 為 邊 （ Edge） ， 目 的 是 為 了 解 決 某 個 極 值問 題 。 圖 中 的 點 用 v表 示 ， 邊 用 e表 示 。 對 每條 邊 可 用 它 所 連 接 的 點 表 示 ，記 作 ： e1=v1,v1; e2=v1,v2; , EVG 強 調 點 與 點 之 間 的 關 聯(lián) 關 系 ， 不 講 究 圖 的 比 例 大小 與 形 狀 ；每 條 邊 上 賦 有 一 個 權 ；建 立 網(wǎng) 絡 模 型 ， 求 最 大 值 或 最 小 值 。 14 2 653 876 63 162 7 433 71 6 v3e7e4 e8e5e6 e1e2 e3v1v2v4 v5 端 點 ,關 聯(lián) 邊 ,相 鄰若 有 邊 e可 表 示 為 e=vi,vj， 稱 vi和 vj是 邊 e的 端 點 ， 反 之 稱 邊 e為 點 vi或 vj的 關 聯(lián) 邊 。 若 點 vi、 vj與 同 一 條 邊 關聯(lián) ， 稱 點 vi和 vj相 鄰 ； 若 邊 ei和 ej具有 公 共 的 端 點 ， 稱 邊 ei和 ej相 鄰 。二 、 關 于 圖 的 另 外 一 些 名 稱 和 術 語 ： 環(huán) , 多 重 邊 , 簡 單 圖如 果 邊 e的 兩 個 端 點 相 重 ， 稱 該 邊 為環(huán) 。 如 右 圖 中 邊 e1為 環(huán) 。 如 果 兩 個 點之 間 多 于 一 條 ， 稱 為 多 重 邊 ， 如 右 圖中 的 e4和 e5， 對 無 環(huán) 、 無 多 重 邊 的 圖稱 作 簡 單 圖 。 v3e7e4 e8e5e6 e1e2 e3v1v2v 4 v5 次 ， 奇 點 ， 偶 點 ， 孤 立 點與 某 一 個 點 vi相 關 聯(lián) 的 邊 的 數(shù) 目 稱 為點 vi的 次 （ 也 叫 做 度 ） ， 記 作 d(vi)。右 圖 中 d(v1) ,d(v3)=5,d(v5)=1。 次為 奇 數(shù) 的 點 稱 作 奇 點 ， 次 為 偶 數(shù) 的點 稱 作 偶 點 ， 次 為 1的 點 稱 為 懸 掛 點 ，次 為 0的 點 稱 作 孤 立 點 。 v3e7e4 e8e5e6 e1e2 e3v1v2v 4 v5圖 的 次 : 一 個 圖 的 次 等 于 各 點 的 次 之 和 。 定 理 1 任 何 圖 中 ， 頂 點 次 數(shù) 之 和 等 于 所 有 邊 數(shù) 的 2倍 。定 理 2 任 何 圖 中 ， 次 為 奇 數(shù) 的 頂 點 必 為 偶 數(shù) 個 。證 明 ： 由 于 每 條 邊 必 與 兩 個 頂 點 關 聯(lián) ， 在 計 算 點 的 次 時 ， 每 條 邊均 被 計 算 了 兩 次 ， 所 以 頂 點 次 數(shù) 的 總 和 等 于 邊 數(shù) 的 2倍 。證 明 ： 設 V1和 V2分 別 為 圖 G中 奇 點 與 偶 點 的 集 合 。 由 定 理 1可 得 ：mvdvdvd Vv VvVv 2)()()( 21 2m為 偶 數(shù) ， 且 偶 點 的 次 之 和 也 為 偶 數(shù) ， 所 以 必 為 偶數(shù) ， 即 奇 數(shù) 點 的 個 數(shù) 必 為 偶 數(shù) 。 2 )(Vv vd 1 )(Vv vd 鏈 ， 圈 ， 連 通 圖圖 中 某 些 點 和 邊 的 交 替 序 列 ， 若 其中 各 邊 互 不 相 同 ， 且 對 任 意 vi,t-1和vit均 相 鄰 稱 為 鏈 。 用 表 示 ： v3e7e4 e8e5e6 e1e2 e3v1v2v 4 v5, 110 kk vevev 起 點 與 終 點 重 合 的 鏈 稱 作 圈 。 如果 每 一 對 頂 點 之 間 至 少 存 在 一 條鏈 ， 稱 這 樣 的 圖 為 連 通 圖 ， 否 則稱 圖 不 連 通 。 子 圖 ， 部 分 圖 (支 撐 子 圖 )圖 G1=V1、 E1和 圖 G2=V2， E2如 果 有 稱 G1是 G2的 一 個 子 圖 。若 有 ， 則 稱 G1是 G2的 一個 部 分 圖 (支 撐 子 圖 )。2121 EEVV 和 2121 EEVV ， v3e7e4 e8e5e6 e1e2 e3v1v2v 4 v5v3e4 e8e5e6v2v4 v5 v3e7e4 e8e6 e2 e3v1v2v4 v5(a) (b) （ G圖 ） 網(wǎng) 絡 （ 賦 權 圖 ）賦 權 圖 ） :權 可 以 代 表 距 離 、 費 用 、 通 過 能 力 (容 量 )等 等 。無 向 網(wǎng) 絡 :端 點 無 序 的 賦 權 圖 稱 為 .有 向 網(wǎng) 絡 :端 點 有 序 的 賦 權 圖 稱 為 。 9 1020 157 1419 25 6 圖 的 矩 陣 描 述 ： 鄰 接 矩 陣 、 關 聯(lián) 矩 陣 、 權 矩 陣 等 。1. 鄰 接 矩 陣對 于 圖 G=（ V， E） ， | V |=n， | E |=m， 有 nn階 方 矩 陣A=(aij) nn， 其 中 其 它 之 間 有 關 聯(lián) 邊 時與當 且 僅 檔0 vv1 jiija v5v1 v2 v3v4v6 433 2 2564 37 010101 101001 010111 101010 001101 111010 65432166 654321 vvvvvvA vvvvvv例 6.2 下 圖 所 表 示 的 圖 可 以 構 造 鄰 接 矩 陣 A如 下 對 于 賦 權 圖 G=(V,E), 其 中 邊 有 權 , 構 造 矩 陣 B=(bij) nn 其 中 ： ),( ji vv jiw Evv Evvwb ji jijiji ),(0 ),( 6543216543 21 030303 302004 020576 305020 007204 346040 vvvvvvvvvvvvB v5 v1 v2 v3v4v6 433 2 2564 37例 6.4 下 圖 所 表 示 的 圖 可 以 構 造 權 矩 陣 B如 下 : G=(V,E) 鄰 接 矩 陣 關 聯(lián) 矩 陣 邊 e=u,v 關 聯(lián) 邊 端 點 環(huán) 多 重 邊 簡 單 圖多 重 圖 0 1 奇 數(shù) 偶 數(shù) 子 圖子圖 生成子圖 孤立點 懸掛點 奇點 偶點頂 點 數(shù) p 邊 數(shù) q 點 邊 關 系各 種 鏈 的 概 念 歐 拉 圖 與 中 國 郵 路 問 題歐 拉 圖 C ab d哥 尼 斯 堡 七 橋 問 題 ac b d(b) 定 理 2 連 通 無 向 圖 G為 歐 拉 鏈 的 充 要 條 件 是 它 恰 含 兩 個 奇 次頂 點 。 定 義 1. 在 連 通 無 向 圖 G中 ,若 存 在 經(jīng) 過 每 條 邊 恰 好 一 次 的 一 個圈 或 一 條 鏈 ,就 稱 此 圈 或 鏈 為 歐 拉 圈 或 歐 拉 鏈 。 若 圖 G含 一 條 歐拉 圈 ， 則 稱 為 歐 拉 圖 。 定 理 1 連 通 無 向 圖 G為 歐 拉 圖 的 充 要 條 件 是 它 的 全 部 頂 點 都是 偶 次 頂 點 。 （ G中 無 奇 次 頂 點 ） 歐 拉 鏈歐 拉 圖 中 國 郵 路 問 題 定 理 3 使 圖 G成 為 總 權 最 小 的 歐 拉 圖 的 充 要 條 件 是 ： （ 1） 在 有 奇 次 頂 點 的 圖 G中 ， 通 過 加 重 復 邊 的 方 法 使 圖不 再 包 含 奇 次 頂 點 ， 但 原 圖 的 每 條 邊 最 多 只 能 加 一 條 重復 邊 。 （ 2） 在 圖 G的 每 個 回 路 上 ， 重 復 邊 之 總 權 不 超 過 該 回 路非 重 復 邊 之 總 權 。 （ 或 回 路 總 長 的 一 半 ） 例 1 試 為 圖 4-13（ a)構 成 總 權 最 小 的 歐 拉 圖 。 圖 中線 旁 的 數(shù) 字 為 相 應 邊 的 權 。12 433 212 4 （ a) 圖 4-13 例 2 試 為 圖 4-14（ a） 所 示 的 街 道 規(guī) 劃 最 優(yōu) 投 遞 路 線 。 解 ： 可 按 以 上 所 述 步 驟 進 行 ， 最 終 結 果 示 于 圖 4-14（ b)， 總權 等 于 52， 重 復 邊 的 長 度 等 于 10。1 334 3 3 33 332 2 2 圖 4-14（ a）2 41 3 33 3 333 32 2 圖 4-14（ b）22 第 二 節(jié) 樹樹 是 圖 論 中 結 構 最 簡 單 但 又 十 分 重 要 的 圖 。 在 自 然 和 社 會 領域 應 用 極 為 廣 泛 。例 6.2 乒 乓 求 單 打 比 賽 抽 簽 后 ， 可 用 圖 來 表 示 相 遇 情 況 ， 如下 圖 所 示 。 A B C D E F G H 運 動 員 例 6.3 某 企 業(yè) 的 組 織 機 構 圖 也 可 用 樹 圖 表 示 。廠 長人 事 科 財 務 科 總 工程 師 生 產(chǎn) 副廠 長 經(jīng) 營 副廠 長 開 發(fā) 科 技 術 科 生 產(chǎn) 科 設 備 科 供 應 科 銷 售 科 檢 驗 科動 力 科 樹 ： 無 圈 的 連 通 圖 即 為 樹性 質 1： 任 何 樹 中 必 存 在 次 為 1的 點 。性 質 2： n 個 頂 點 的 樹 必 有 n-1 條 邊 。性 質 3： 樹 中 任 意 兩 個 頂 點 之 間 ， 恰 有 且 僅 有 一 條 鏈 。性 質 4： 樹 連 通 ， 但 去 掉 任 一 條 邊 ， 必 變 為 不 連 通 。性 質 5： 樹 無 回 圈 ， 但 不 相 鄰 的 兩 個 點 之 間 加 一 條 邊 ， 恰得 到 一 個 圈 。 v1 v2v3v4v5v6 圖 的 最 小 部 分 樹 (支 撐 樹 )如 果 G2是 G1的 部 分 圖 ， 又 是 樹 圖 ， 則 稱 G2是 G1的 部 分 樹（ 或 支 撐 樹 ） 。 樹 圖 的 各 條 邊 稱 為 樹 枝 ， 一 般 圖 G1含 有 多個 部 分 樹 ， 其 中 樹 枝 總 長 最 小 的 部 分 樹 ， 稱 為 該 圖 的 最 小部 分 樹 （ 或 最 小 支 撐 樹 ） 。v1 v2v 3v4v5 v1 v2v3v4v5G1 G2 例 如 ， 圖 4-18（ a） 是 一 個 有 四 個 頂 點 （ n=4）的 連 通 圖 ， 它 共 有 nn-2=42=16個 生 成 樹 。V1 V 2V3 V4 圖 4-18（ a） 破 圈 法 ： 任 取 一 圈 ， 去 掉 圈 中 最 長 邊 ， 直 到 無 圈 。5v1v2 v3v4 v5v6843 7526 18v1v 2 v3v4 v5v643 52 1 邊 數(shù) n-1=5 v1v2 v3 v4 v5v643 52 1得 到 最 小 樹 ： Min C(T)=15 避 圈 法 :去 掉 G中 所 有 邊 ， 得 到 n個 孤 立 點 ； 然 后 加 邊 。加 邊 的 原 則 為 ： 從 最 短 邊 開 始 添 加 ， 加 邊 的 過 程 中 不 能 形 成圈 ， 直 到 點 點 連 通 (即 :n-1條 邊 )。5v1v 2 v3v4 v5v6843 7526 18 v1v2 v3v4 v5v643 52 15v1v2 v3v4 v5v6843 7526 18 Min C(T)=15 3 74 9 346321Min C(T)=12 Min C(T)=152 54 17331 44 75答 案 ： 3 412 23 23 242 Min C(T)=122 13 6 385345 6 74 54 321 Min C(T)=18 1 某 一 點 到 另 一 點 的 最 短 路 的 Dijkstra法2 所 有 點 對 間 的 最 短 路 返 回第 三 節(jié) 最 短 路 問 題 就 是 從 給 定 的 網(wǎng) 絡 圖 中 找 出 一 點 到 各 點 或 任 意 兩 點 之 間距 離 最 短 的 一 條 路 .有 些 問 題 ， 如 選 址 、 管 道 鋪 設 時 的 選 線 、 設 備 更 新 、 投資 、 某 些 整 數(shù) 規(guī) 劃 和 動 態(tài) 規(guī) 劃 的 問 題 ， 也 可 以 歸 結 為 求 最 短路 的 問 題 。 因 此 這 類 問 題 在 生 產(chǎn) 實 際 中 得 到 廣 泛 應 用 。 里 特 城 （ Littletown） 是 一 個 鄉(xiāng) 村 的 小 鎮(zhèn) 。 它 的消 防 隊 要 為 包 括 許 多 農(nóng) 場 社 區(qū) 在 內 大 片 的 地 區(qū) 提 供服 務 。 在 這 個 地 區(qū) 里 有 很 多 道 路 ， 從 消 防 站 到 任 何一 個 社 區(qū) 都 有 很 多 條 路 線 。 因 為 時 間 是 一 個 到 達 火災 發(fā) 生 點 的 主 要 因 素 ， 所 以 消 防 隊 隊 長 希 望 事 先 能夠 確 定 從 消 防 站 到 每 一 個 農(nóng) 場 社 區(qū) 的 最 短 路 。例 子 ： 里 特 城 的 消 防 隊 問 題 最 短 路 ： O A B E F T 19 英 里 1、 算 法 的 基 本 思 想 一 種 標 號 的 迭 代 過 程具 體 算 法 是 在 圖 上 進 行的 最 短 路 是到 的 最 短 路 是到則 的 最 短 路 是到則 的 最 短 路 經(jīng) 過 點到 終 點若 起 點 nnn nnn nnn ns vvpvv vvvpvv vvvvpvv vvvvv , , , ,333 3222 32111 321 2.有 向 圖 的 狄 克 斯 屈 拉 (Dijkstra)標 號 算 法 步 驟點 標 號 ： p(vj) 起 點 vs到 點 vj的 最 短 路 長 ；邊 標 號 ： a(i， j)=p(i)+lij，步 驟 ： (1)令 起 點 的 標 號 ； p(v s) 0。先 求 有 向 圖 的 最 短 路 ， 設 網(wǎng) 絡 圖 的 起 點 是 vs ,終 點 是 vt ,以 vi為 起點 vj為 終 點 的 弧 記 為 （ i， j） ,距 離 為 lij (2)找 出 所 有 vi已 標 號 vj未 標 號 的 弧 集 合 Ai=(i， j)， 如 果 這樣 的 弧 不 存 在 或 vt已 標 號 則 計 算 結 束 ；(3)計 算 集 合 Ai中 弧 的 標 號 ： a(i， j)= p(i)+lij(4)選 一 個 點 標 號 返 回 到 第 (2)步 。 )(,),(|),(min)( kpvAijijiavp kjk 處 標 號在 終 點 61012 3 2 14 675 8 11165 圖 5 19【 例 5-1】 圖 5 1中 的 權 cij表 示 vi到 vj的 距 離 （ 費 用 、 時 間 ） ， 從v1修 一 條 公 路 或 架 設 一 條 高 壓 線 到 v7， 如 何 選 擇 一 條 路 線 使 距 離最 短 ， 建 立 該 問 題 的 網(wǎng) 絡 數(shù) 學 模 型 。 【 解 】 設 xij為 選 擇 弧 (i， j)的 狀 態(tài) 變 量 ， 選 擇 弧 (i， j)時 xij 1， 不選 擇 弧 (i， j)時 xij 0， 得 到 最 短 路 問 題 的 網(wǎng) 絡 模 型 ：( , )12 ( , ) ( , )57 13 1467min 1 0 2,3, ,610 ( , )ij iji j Eij kii j E k i Eij Z c xx x xx x ix xx i j E 或 1， 61012 3 2 14 675 8 11165 圖 5 196 1012 9 20p(9,v2) 18P（ 6, V1） 16P(12,v1) 17 P(16,v3)24 32P(18,v3) 29 P(29,v5)【 例 5-1】 用 Dijkstra算 法 求 圖 5 1 所 示 v1到 v7的 最 短 路 及 最 短 路 長 v 1 到 v7的 最 短 路 為 ： p17= v1, v2, v3, v5, v7 ， 最 短 路 長 為 L17=29 14P（ 0,V1） 61012 3 2 14 675 8 11165 圖 5 196 1012 9 20p(9,v2) 18P（ 6, V1） 16P(12,v1) 17 P(16,v3)24 32P(18,v3) 29 P(29,v5)v 1 到 v7的 最 短 路 為 ： p17= v1, v2, v3, v5, v7 ， 最 短 路 長 為 L17=29 14P（ 0,V1） 從 上 例 知 ， 只 要 某 點 已 標 號 ， 說 明 已 找 到 起 點 vs到 該 點 的 最 短 路線 及 最 短 距 離 ， 因 此 可 以 將 每 個 點 標 號 ， 求 出 vs到 任 意 點 的 最 短路 線 ， 如 果 某 個 點 vj不 能 標 號 ， 說 明 vs不 可 達 vj 。 【 例 6-5】 求 圖 6-10所 示 v1到 各 點 的 最 短 路 及 最 短 距 離 452 61 7 83 93 26 121618P(0,v1) 4 52 P(2,v1)3 10P(3,v1)9 6 126P(4,v1) 11 P(6,v3)P(6,v3)18812 24P(8,v5) 24 P(18,v5)所 有 點 都 已 標 號 ， 點 上 的 標 號 就 是 v 1到 該 點 的 最 短 距 離 ， 最 短 路線 就 是 紅 色 的 鏈 。 圖 6-10 3 .無 向 圖 最 短 路 的 求 法 每 次 迭 代 只 有 一 個 節(jié) 點 獲 得 標 號 ， 若 有 兩 個 或 兩 個 以 上 節(jié) 點 的臨 時 標 號 同 時 最 小 ， 可 任 選 一 個 標 號 ；標 號 Pj 表 示 vs 到 vj 的 最 短 路 ， 第 k 次 迭 代 得 到 的 永 久 標號 ， 最 多 有 n1 次 迭 代 ；可 以 應 用 于 簡 單 有 向 圖 和 混 合 圖 ， 在 臨 時 標 號 時 ， 所 謂 相 鄰 必須 是 箭 頭 指 向 的 節(jié) 點 ； 若 第 n1 次 迭 代 后 仍 有 節(jié) 點 的 標 號 為 ， 則 表 明 vs 到 該 節(jié) 點 無 有 向 路 徑 ；vs 到 所 有 點 的 最 短 路 也 是 一 棵 生 成 樹 ， 但 不 是 最 小 生 成 樹這 個 算 法 只 設 用 于 全 部 權 為 非 負 情 況 ,如 果 某 邊 上 權 為 負 的 ,算法 失 效 ;當 vi與 vj兩 點 之 間 至 少 有 兩 條 邊 相 關 聯(lián) 時 ， 留 下 一 條 最 短 邊 ，去 掉 其 它 關 聯(lián) 邊 。 1024 14913 5 7 87v1 v2v3 v4v5 v6 例 求 下 圖 所 示 網(wǎng) 絡 之 頂 點 1至 6的 最 短 路 和 最 短 路 長 。P（ 0， v1） P（ 10， v1） P（ 15， v2）P（ 22， v5） P（ 22， v5）P（ 23， v2） 14 2 653 876 63 162 7 433 71 6 二 、 所 有 點 對 間 的 最 短 路 Floyd算 法 1、 寫 出 圖 的 權 矩 陣 )( )( 不 存 在到 的 直 達 路 線 距 離到 ji jiijij vv vvld nnijdD )( 、 輸 入 權 矩 陣 （ ） ； 、 對 n個 頂 點 的 圖 G,該 方 法 迭 代 n步 結 束 ，第 k次 迭 代 的 矩 陣 Dk的 元 素 dij(k)按 下 式 選 取 dij(k) =mindij(k-1),dik(k-1） +dkj(k-1） 其 中 ， i,j=1,2,3, ,n。 但 當 i=k或 j=k時 ，dij(k)=dij(k-1).。 、 （ ） 中 的 元 素 就 是 到 的 最 短 路 長 。 v1 v3v4v2 v5512 3 10655 2 28442例 求 下 圖 所 示 網(wǎng) 絡 圖 各 點 對 間 的 最 短 路 和 最 短 路 長 。 0442 4062 82032 21005 215054321)0( vvvvvD 0442 40372 82032 27605 2150 413412 21421354321)1( vvvvvD 04427 40372 52032 27605 72150 521 413412 325214213 12554321)2( vvvvvD 04426 40362 52032 27605 62140531 4134132 325214213 132513254321)4( vvvvvD 04426 40362 52032 27605 62140531 4134132 325214213 132513254321)3( vvvvvD 04426 40362 52032 26605 62140531 4134132 325254213 132513254321)5( vvvvvD 0442 40372 82032 27605 2150 11 1154321)1( vvvvvD 231 47 4 32 910例 求 下 圖 所 示 網(wǎng) 絡 圖 各 點 對 間 的 最 短 路 和 最 短 路 長 。 課 堂 練 習 ：1. 用 Dijkstra算 法 求 下 圖 從 v1到 v6的 最 短 距 離 及 路 線 。v 3 v54v1 v2 v4 v635 22 2 421v1到 v6的 最 短 路 為 ： 6521 vvvv 2. 求 從 v1到 v8的 最 短 路 徑 2 371 84 56 613 4 105 2 7 5 93 4 682 2 371 84 56 613 4 105 2 7 5 93 4 682 p2=2p4=1p1=0p6=3 p7=3 p5=6 p3=8p8=10v1到 v8的 最 短 路 徑 為 v1v4v7v5v8， 最 短 距 離 為 10 最 短 路 問 題 的 應 用 ：例 6.7 電 信 公 司 準 備 在 甲 、 乙 兩 地 沿 路 架 設 一 條 光 纜 線 ， 問如 何 架 設 使 其 光 纜 線 路 最 短 ？ 下 圖 給 出 了 甲 乙 兩 地 間 的 交 通圖 。 權 數(shù) 表 示 兩 地 間 公 路 的 長 度 （ 單 位 ： 公 里 ） 。 v 1 （ 甲 地 ） 15 17 6244310 6 5v2 v7 (乙 地 )v3 v4 v5 v6 解 ： 這 是 一 個 求 無 向 圖 的 最 短 路 的 問 題 。 如 何 制 定 一 個 運 輸 計 劃 使 生 產(chǎn) 地 到 銷 售 地 的 產(chǎn) 品 輸 送 量 最 大 。這 就 是 一 個 網(wǎng) 絡 最 大 流 問 題 。 實 例 ： 公 司 的 最 大 流 問 題 公 司 是 歐 洲 一 家 生 產(chǎn) 豪 華 汽 車 的 制 造 商 。 雖 然 它 生 產(chǎn) 的 汽 車 在 所 有 發(fā) 達 國 家 的 銷 量 都 不 錯 ， 但 是 對 于 這 家 公 司 來 說 ， 出 口 到 美 國 顯 得 尤 其 重 要 。 公 司 因 為 提 供 優(yōu) 質 的 服 務 而 獲 得 很 好 的 聲 譽 ， 保 持 這 個 聲 譽 一 個 很 重 要 的 秘 訣 是 它 有 著 充 裕 的汽 車 配 件 供 應 ， 從 而 能 夠 隨 時 供 貨 給 公 司 眾 多 的 經(jīng) 銷 商 和授 權 維 修 店 。 這 些 供 應 件 主 要 存 放 在 公 司 的 配 送 中 心 里 ，這 樣 一 有 需 求 就 可 以 立 即 送 貨 。 卡 爾 需 要 優(yōu) 先 考 慮 的 是 改進 這 些 配 送 中 心 的 不 足 之 處 。 背景 該 公 司 在 美 國 有 幾 個 配 送 中 心 。 但 是 ， 離 洛 杉 礬 中 心 最近 的 一 個 配 送 中 心 卻 坐 落 在 離 洛 杉 礬 1000 多 英 里 的 西 雅 圖 。由 于 的 汽 車 在 加 利 福 尼 亞 越 來 越 受 歡 迎 ， 所 以 保 證洛 杉 礬 中 心 良 好 的 供 應 就 顯 得 尤 為 重 要 了 。 因 此 ， 現(xiàn) 在 那 里的 供 應 不 斷 減 少 的 現(xiàn) 狀 成 為 了 公 司 高 層 管 理 真 正 關 心 的 問題 正 如 現(xiàn) 在 卡 爾 深 切 領 會 到 了 一 樣 。 大 部 分 的 汽 車 配 件 以 及 新 車 是 在 該 公 司 坐 落 于 德 國 斯 圖加 特 的 總 廠 和 新 車 一 起 生 產(chǎn) 的 。 也 就 是 這 家 工 廠 向 洛 杉 礬中 心 供 應 汽 車 配 件 。 由 于 其 中 的 一 些 配 件 體 積 很 大 ， 某 些配 件 的 需 求 量 很 多 ， 這 就 使 得 供 應 的 總 量 非 常 龐 大 每月 有 超 過 300， 000立 方 英 尺 的 配 件 需 要 運 到 。 現(xiàn) 在 ， 下 個月 需 要 多 得 多 的 數(shù) 量 以 補 充 正 在 減 少 的 庫 存 。 卡 爾 需 要 盡 快 做 出 一 個 方 案 ， 使 得 下 個 月 從 總 廠 運 送到 洛 杉 礬 配 送 中 心 的 供 應 件 盡 可 能 的 多 。 他 已 經(jīng) 認 識 到 了這 是 個 最 大 流 問 題 一 個 使 得 從 總 廠 運 送 到 洛 杉 礬 配 送中 心 的 配 件 流 最 大 的 問 題 。 因 為 總 廠 生 產(chǎn) 的 配 件 量 遠 遠 要大 于 能 夠 運 送 到 配 送 中 心 的 量 ， 所 以 ， 可 以 運 送 多 少 配 件的 限 制 條 件 就 是 該 公 司 配 送 網(wǎng) 絡 的 容 量 。 問 題 LA STLIROBONONY 80 6070 40 5030 5070 40BMZ的 網(wǎng) 絡 模 型 ， 圖 中 的 數(shù) 字 代 表 該 弧 的 容 量 一 基 本 概 念二 求 最 大 流 的 標 號 法 返 回 如 圖 4-23 是 聯(lián) 接 某 產(chǎn) 品 產(chǎn) 地 v1和 銷 售 地 v6點的 交 通 網(wǎng) 。s t48 4 4122 6 79 s t4， 38,4 4,0 4,21,12,22,2 6,0 7,49,3 一 、 基 本 概 念 ： 對 網(wǎng) 絡 上 的 每 條 弧 (vi,vj)都 給 出 一 個 最 大 的 通過 能 力 ， 稱 為 該 弧 的 ， 簡 記 為 cij。 容 量 網(wǎng) 絡 中 通 常 規(guī) 定一 個 (也 稱 源 點 ， 記 為 s)和 一 個 (也 稱 匯 點 ， 記 為 t)，網(wǎng) 絡 中 其 他 點 稱 為 。s t48 4 4122 6 79 2. 網(wǎng) 絡 的 最 大 流是 指 網(wǎng) 絡 中 從 發(fā) 點 到 收 點 之 間 允 許 通 過 的 最 大 流 量 。3. 流 與 可 行 流 流 是 指 加 在 網(wǎng) 絡 各 條 弧 上 的 實 際 流 量 ， 記 為 fij。若 fij=0， 稱 為 零 流 。 在 網(wǎng) 絡 中 滿 足 下 述 條 件 的 流 為 可 行 流 ： （ 1） 、 容 量 限 制 條 件 ： 0 fij cij （ 2） 、 平 衡 條 件 ： （ 終 點 ）起 點 ）ti tsisiff ijij vBv jivAv ij F ,0 (F)()( 結 論 ： 任 何 網(wǎng) 絡 上 一 定 存 在 可 行 流 。 （ 零 流 即 是可 行 流 ）網(wǎng) 絡 最 大 流 問 題 ：指 滿 足 容 量 限 制 條 件 和 中 間 點 平 衡 的 條 件 下 ， 使 F值達 到 最 大 。 割 與 割 集割 是 指 容 量 網(wǎng) 絡 中 的 發(fā) 點 和 收 點 分 割 開 ， 并 使 st的 流 中 斷的 一 組 弧 的 集 合 。 割 容 量 是 組 成 割 集 合 中 的 各 條 弧 的 容 量 之和 ， 用 表 示 。),( VVc ),(),( ),(),( VVji ji vvcVVc如 下 圖 中 ， AA將 網(wǎng) 絡 上 的 點 分 割 成 兩 個 集 合 。 并有 ， 稱 弧 的 集 合 =(vs,v3),(v2,v4),(v2,v5)是 一 個 割 。 VV ,VtVs , （ S， ）=(vs,v3),(v2,v4),(v2,v5)s割 容 量 是 ： 9+6+5=20 vs v2v3 v4 v5v6 vt（ 4， 0）（ 13， 11） （ 5， 5）（ 9， 9） （ 5， 4）（ 5， 5）（ 6， 6） （ 5， 2） （ 9， 7）（ 4， 4）（ 4， 4） （ 10， 9） 在 網(wǎng) 絡 中 st的 最 大 流 量 等 于 它 的 最 小 割 集 的 容 量 ，即 ： v (f ) = c (V, V) 在 網(wǎng) 絡 的 發(fā) 點 和 收 點 之 間 能 找 到 一 條 鏈 ， 在 該 鏈 上 所 有指 向 為 st的 弧 ， 稱 為 前 向 弧 ， 記 作 +,存 在 f0， 則 稱 這 樣 的 鏈 為增 廣 鏈 。 例 如 下 圖 中 ， sv2v1v3v4t。 網(wǎng) 絡 N中 的 流 F是 最 大 流 當 且 僅 當 N中 不 包 含 任 何 增 廣鏈 二 、 求 網(wǎng) 絡 最 大 流 的 標 號 法由 一 個 流 開 始 ， 系 統(tǒng) 地 搜 尋 增 廣 鏈 ， 然 后 在 此 鏈 上 增 流 ，繼 續(xù) 這 個 增 流 過 程 ， 直 至 不 存 在 增 廣 鏈 。(1) 找 出 第 一 個 可 行 流 ， （ 例 如 所 有 弧 的 流 量 fij =0。 ）(2) 用 標 號 的 方 法 找 一 條 增 廣 鏈 首 先 給 發(fā) 點 s標 號 (),標 號 中 的 數(shù) 字 表 示 允 許 的 最 大 調 整 量 。 選 擇 一 個 點 v i 已 標 號 并 且 另 一 端 未 標 號 的 弧 沿 著 某 條 鏈向 收 點 檢 查 ： 如 果 弧 的 起 點 為 vi， 并 且 有 fij0， 則 vj標 號 (fji)(3) 重 復 第 (2)步 ， 可 能 出 現(xiàn) 兩 種 結 局 ： 標 號 過 程 中 斷 ， t無 法 標 號 ， 說 明 網(wǎng) 絡 中 不 存 在 流 量 可 增鏈 ， 目 前 流 量 為 最 大 流 。 同 時 可 以 確 定 最 小 割 集 ， 記 已 標 號的 點 集 為 V,未 標 號 的 點 集 合 為 V,(V,V)為 網(wǎng) 絡 的 最 小 割 。 t得 到 標 號 ， 反 向 追 蹤 在 網(wǎng) 絡 中 找 到 一 條 從 s到 t得 由 標 號點 及 相 應 的 弧 連 接 而 成 的 流 量 可 增 鏈 。 繼 續(xù) 第 (4)步 所 有 非 增 廣 鏈 上 的 弧對 增 廣 鏈 上 所 有 后 向 弧對 增 廣 鏈 上 所 有 前 向 弧F tF tFF )( )(4) 修 改 流 量 。 設 原 圖 可 行 流 為 f， 令得 到 網(wǎng) 絡 上 一 個 新 的 可 行 流 F。(5) 擦 除 圖 上 所 有 標 號 ， 重 復 (1)-(4)步 ， 直 到 圖 中 找 不 到 任 何流 量 可 增 鏈 ， 計 算 結 束 。 例 6.10 用 標 號 算 法 求 下 圖 中 st的 最 大 流 量 ， 并 找 出 最 小 割 。 v1 v3v2 v48,7 9,3 5,410,86,12,09,95,47,5 解 ： (1) 先 給 s標 號 () v1 v3v2 v48,7 9,3 5,410,86,12,09,95,47,5(0,) F0=12 v1 v3v2 v48,7 9,3 5,410,86,12,09,95,47,5(0) (2) 檢 查 與 s點 相 鄰 的 未 標 號 的 點 ， 因 fs1cs1， 故 對 v1標 號=min, cs1-fs1=1, (s,1) v1 v3v2 v48,7 9,3 5,410,86,12,0,9,95,47,6(0,) (s,1)(2) 檢 查 與 v1點 相 鄰 的 未 標 號 的 點 ， 因 f13c13， 故 對 v3標 號=min1, c13-f13= min1, 6= 1 (v1,1) v1 v3v2 v48,7 9,3 5,410,86,12,09,95,47,5(0,) (s,1) (v1,1)(3) 檢 查 與 v3點 相 鄰 的 未 標 號 的 點 ， 因 f3t0， 若 cij-fij=0當 作 為 反 向 弧 使 用 時 ：bij- = -bij， 若 fij0， 若 fij=0 為 了 便 于 計 算 和 檢 查 ， 常 在 每 條 弧 上 依 次 注 出 以 下 四 個 數(shù)字 ： (1)弧 容 量 cij； (2)弧 流 量 fij； (3) bij+ （ 作 為 正 向 弧 使 用 時 在其 上 流 過 單 位 物 品 的 費 用 ） ； (4) bij- （ 作 為 反 向 弧 使 用 時 在 其上 流 過 單 位 物 品 的 費 用 ） 。 . 以 b ij+或 bij-弧 aij的 權 （ 弧 長 ） ， 用 Dijkstra算 法 求 vsVi的 最 短 路 P。 4. 取 增 流 量 min=min ijaij P 對 P上 的 各 弧 增 流 ， 這 里 的 ij為 弧 ij的 流 量 可 增 值 。 5. 轉 回 第 2步 ， 直 至 每 3步 求 不 出 有 限 長 的 最 短 路 為 止 。這 時 已 得 到 最 小 費 用 的 最 大 流 。 例 12 求 下 圖 網(wǎng) 絡 的 最 小 費 用 最 大 流 ， 各 弧 的 容 量 （ 弧 旁 的第 一 個 數(shù) 字 和 通 過 單 位 物 品 的 費 用 （ 弧 旁 的 第 二 個 數(shù) 字 ） 如 圖 中所 示 。 s t4,1 6,6 5,22,33,26,4 6,3 返 回 1、 標 號 過 程 中 ， 是 否 一 定 要 對 所 有 的 頂 點全 部 逐 個 順 序 標 記 ？2、 如 果 可 以 同 時 得 到 若 干 條 增 廣 鏈 是 否 可以 同 時 調 整 流 量 ？ 3、 同 一 個 問 題 每 一 次 標 號 過 程 所 尋 找 的增 廣 鏈 是 否 唯 一 ？ 最 大 流 是 否 唯 一 ？ 最 小割 是 否 唯 一 ？4、 對 多 發(fā) 點 、 多 收 點 的 容 量 網(wǎng) 絡 怎 麼 求最 大 流 ？ 比 賽 安 排 問 題 有 5名 運 動 員 參 加 游 泳 比 賽 ， 下 表 給 出 了 每 位 運動 員 參 加 的 項 目 。 問 如 何 安 排 ， 才 能 使 得 每 位 運 動員 都 不 連 續(xù) 地 參 加 比 賽 ？第 七 節(jié) 應 用 舉 例 游 泳 比 賽 運 動 員 及 參 加 項 目運 動 員 50m仰 泳 50m蛙 泳 100m蝶 泳 100m自 由 泳 200m自 由 泳A * B * * * v1 v5 v4 v3v2 圖 1 游 泳 比 賽 安 排 v4, v1, v2, v3 , v5 線 路 鋪 設 問 題 下 圖 是 一 個 城 鎮(zhèn) 的 地 圖 ， 現(xiàn) 在 要 在 該 城 鎮(zhèn) 的 各 地 點 間 鋪設 管 道 已 知 各 點 相 互 之 間 的 鋪 設 費 用 （ 單 位 ： 千 元 ） ， 如 何設 計 鋪 設 線 路 ， 使 各 地 互 通 的 總 鋪 設 費 用 最 少 ？3 8 7 12452 57 410 679 8 51 其 最 小 總 費 用 為 ：31 （ 千 元 ） 例 6.8 設 備 更 新 問 題 。 某 公 司 使 用 一 臺 設 備 ， 在 每 年 年 初 ，公 司 就 要 決 定 是 購 買 新 的 設 備 還 是 繼 續(xù) 使 用 舊 設 備 。 如 果 購置 新 設 備 ， 就 要 支 付 一 定 的 購 置 費 ， 當 然 新 設 備 的 維 修 費 用就 低 。 如 果 繼 續(xù) 使 用 舊 設 備 ， 可 以 省 去 購 置 費 ， 但 維 修 費 用就 高 了 。 請 設 計 一 個 五 年 之 內 的 更 新 設 備 的 計 劃 ， 使 得 五 年內 購 置 費 用 和 維 修 費 用 總 的 支 付 費 用 最 小 。 已 知 ：設 備 每 年 年 初 的 價 格 表年 份 1 2 3 4 5年 初 價 格 11 11 12 12 13 設 備 維 修 費 如 下 表使 用 年 數(shù) 0-1 1-2 2-3 3-4 4-5每 年 維 修 費 用 5 6 8 11 18解 ： 將 問 題 轉 化 為 最 短 路 問 題 ， 如 下 圖 ： 用 vi表 示 “ 第 i年 年初 購 進 一 臺 新 設 備 ” ,弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v6 把 所 有 弧 的 權 數(shù) 計 算 如 下 表 ， 把 權 數(shù) 賦 到 圖 中 ， 再 用Dijkstra算 法 求 最 短 路 。1 2 3 4 5 61 16 22 30 41 592 16 22 30 413 17 23 314 17 235 186 v1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23 最 終 得 到 下 圖 ， 可 知 ， v1到 v6的 距 離 是 53， 最 短 路 徑 有 兩 條 ： v1v3v6和 v1v4v6 V1（ 0,s） v 3 v4 (41,1) v5 v622 30 41 5916 (22,1) 30 41 3123 17 1817 23 V2（ 16,1）16 (30,1) (53,3)(53,4) v1 v2 v3 v4 v5 v615 16 17 18 1955402921 22 30 41 31 2423(0,s) (15,1) (12,1) (29,1) (40,1) (52,3) 選 址 問 題 有 六 個 居 民 點 ： v1、 v2、 v3、 v4、 v5、 v6擬 修 建一 所 小 學 ， 已 知 各 地 點 的 學 生 人 數(shù) 分 別 為 25、 20、30、 10、 35和 45人 ， 其 道 路 如 下 圖 所 示 ， 試 確 定 學校 設 于 哪 一 個 居 民 點 ， 才 能 使 學 生 所 走 的 總 路 程 最少 ？ v1 v6v5v3 v4v22 64 81 36137 D0= 0 2 7 M M M2 0 4 6 8 M7 4 0 1 3 MM 6 1 0 1 6M 8 3 1 0 3 M M M 6 3 0解 : D6= 0 2 6 7 8 112 0 4 5 6 96 4 0 1 2 57 5 1 0 1 48 6 2 1 0 311 9 5 4 3 0 考 慮 到 各 點 的 學 習 人 數(shù) ,對 D6的 每 一 行 乘 以 相應 各 點 的 人 數(shù) ,得 到D= 0 50 150 175 200 275 40 0 80 100 120 180180 120 0 30 60 150 70 50 10 0 10 40280 210 70 35 0 105495 405 225 180 135 0 D=1065 835 535 520 525 750 V1 V2 V3 V4 V5 V6學 校 應 設 在 V4 點對 照 D的 各 元 素 按 列 相 加 ,即 得 到 將 學 校 設 在不 同 點 時 所 走 的 總 路 程 .由 C6得 到 相 應 路 徑 :V1.v4: v1v2v3-v4V2.v4: v2v3-v4V3.v4 : v3-v4V5.v4: v5-v4V6.v4: v6v5-v4 消 防 站 定 位 問 題 某 市 有 五 個 火 災 易 發(fā) 點 v1、 v2、 v3、 v4、 v5， 現(xiàn) 需 在 其中 的 一 個 點 處 設 置 消 防 站 ， 問 應 設 在 哪 個 點 才 能 使 消 防 站 的最 大 服 務 距 離 最 小 。 這 五 個 點 之 間 的 路 網(wǎng) 和 各 段 路 長 如 下 圖所 示 。 v1 v2 v5 v3 v41 1 4 2 1 4 1053243 6558901426 40345 55012 84305 95410vvvvvD 54321)5( 消 防 站 應 設 在 v3或 者 v4點 有 三 個 倉 庫 運 送 某 種 產(chǎn) 品 到 四 個 市 場 上 去 ， 倉 庫 的 供應 量 和 市 場 的 需 求 量 見 下 表 。 倉 庫 與 市 場 之 間 路 線 上 的容 量 如 表 所 示 （ 容 量 為 零 表 示 兩 點 間 無 直 接 的 路 線 可通 ） 。 確 定 現(xiàn) 有 路 線 容 量 是 否 能 滿 足 市 場 的 需 求 。 若 不能 ， 應 修 改 哪 條 線 路 的 容 量 。 市 場倉 庫 供 應 量需 求 量 20 20 60 20 A1 30 10 0 40 20 A2 0 0 10 50 20 A3 20 10 40 5 100 B1 B2 B3 B4 解 ： 用 點 A1 A2 A3表 示 三 個 倉 庫 倉 庫 ， 點 B1 、 B2 、 B3 、 B4表 示 四 個 市 場 。 20， 2020， 20100， 50 30， 2010， 040， 1010， 050， 2020， 0 10， 1040， 405， 0S A1A2A3 B1B2B3B4 T20,2020,1060,4020,20 F1=90 20， 2020， 20 100， 70 30， 510， 1040， 510， 1050， 1020， 15 10， 1040， 405， 5S A1A2A3 B1B2B3B4 T20,2020,2060,5020,20 F1=110網(wǎng) 絡 運 輸 最 大 流 分 派 問 題 某 飛 行 隊 有 五 名 正 駕 駛 員 和 五 名 副 駕 駛 員 。 由 于 種 種 原因 ， 某 些 正 、 副 駕 駛 員 不 能 同 機 飛 行 ， 某 些 則 可 以 ， 如 下表 所 示 （ “ *”表 示 可 同 機 飛 行 ） 。 每 價 飛 機 出 航 時 需 正 、 副駕 駛 員 各 一 人 ， 問 最 多 能 有 幾 架 飛 機 同 時 出 航 ？ 應 如 何 安 排正 、 副 駕 駛 員 ？ 正 、 副 駕 駛 員 同 機 飛 行 情 況正副 B1 B2 B3 B4 B5 A1 * A2 * * A3 * * A4 * * A5 * S A1A2A3A4A5 B1B2B3B4B5 T1,01,11,11,11,1 1,01,11,01,01,11,11,01,1 1,11,11,01,11,1 分 派 問 題 網(wǎng) 絡 圖 fmax =4 工 廠 B1、 B2和 B3需 要 從 三 個 地 方 A1、 A2、 A3供 應 原 料 ，工 廠 B2不 能 缺 貨 ， 工 廠 B1和 B3缺 貨 時 要 造 成 損 失 ， 單 位 運價 、 材 料 供 應 量 和 需 求 量 等 均 示 于 下 表 中 ， 試 確 定 使 總 費 用最 低 的 原 料 分 配 方 案 。 供 應 地工 廠 A1 A2 A3 需 要 量 缺 貨損 失B1 3 2 - 8B2 2 3 4 14B3 - 4 2 10 1不 允 許缺 貨 2可 供 量 10 9 7 A A1A2A3A4 B1B2B3 B10,09,07,06,0 10,310,26,1 10,07,4 7,29,4 9,39,2 6,2 8,014,0 返 回F1 下 圖 中 A， B， C， D， E， F分 別 代 表 島 和 陸 地 。 它 們 之間 有 橋 相 連 。 若 河 的 兩 岸 分 別 被 敵 對 雙 方 占 領 ,問 至 少 應切 斷 那 幾 座 橋 才 能 阻 止 對 方 部 隊 過 河 ? BC D EAF 奎 克 公 司 正 在 研 制 一 種 新 產(chǎn) 品 ,計 劃 在 20個 月 后 投 放 市 場奎 克 公 司 希 望 迅 速 推 出 新 產(chǎn) 品 去 參 與 競 爭其 競 爭 對 手 計 劃 將 把 一 種 很有 銷 售 潛 力 的 新 產(chǎn) 品 投 放 市 場現(xiàn) 在 還 有 四 個 沒 有 時 間 重 疊 的 階 段 沒 有 完 成 ,每個 階 段 的 實 施 水 平 可 以 提 高 ,撥 款 3000萬 元管 理 層 希 望 確 定 這 四 個 階 段 各 自 應 該 采 取 哪 一 種 水 平 從 而在 3000萬 預 算 限 制 內 ,使 得 這 種 產(chǎn) 品 可 以 盡 快 地 推 向 市 場 ? 1322應 急 2534優(yōu) 先 (4)(7)(4)5正 常 開 始 生 產(chǎn) 和 分 銷(月 )制 造 系 統(tǒng)設 計 (月 )研 制(月 )剩 下 的 研 究(月 )水 平 準 備 奎 克 新 產(chǎn) 品 的 各 階 段 所 需 時 間 6001200900900應 急 300900600600優(yōu) 先 -300正 常 開 始 生 產(chǎn) 和 分 銷制 造 系 統(tǒng)設 計研 制剩 下 的 研 究水 平 準 備 奎 克 新 產(chǎn) 品 各 階 段 的 費 用 單 位 :萬 元 0,30 T 4,03,3 4,33,6 4,63,9 4,93,122,122,152,182,211,211,241,275 42 3 23 232 535 35 35 2 12 1212 0000 1,210,30 2 ,15 3,3 4,0 T總 長 為 :2+3+3+2+0= 10 (個 月 )應 急 優(yōu) 先 應 急 優(yōu) 先 300010合 計 900 2應 急優(yōu) 先應 急優(yōu) 先剩 下 的 研 究研 制制 造 系 統(tǒng) 設 計開 始 生 產(chǎn) 和 分 銷 成 本 (萬 元 )時 間 (月 )水 平階 段 332 6001200 300奎 克 最 短 路 問 題 的 最 優(yōu) 解 v41024 1495 7 87v1 v2v 3 v5 v613