運(yùn)籌學(xué)_圖與網(wǎng)絡(luò)分析-資料下載頁
2025-05-14 22:15本頁面
【正文】 ； ? 標(biāo)號(hào)點(diǎn)有兩類一類是已檢查的 ， 一類是未檢查的 。 每個(gè)標(biāo)號(hào)點(diǎn)有兩個(gè)標(biāo)號(hào)：第一個(gè)標(biāo)號(hào)表示這個(gè)點(diǎn)的標(biāo)號(hào)是從哪一點(diǎn)得到的 ， 以便進(jìn)一步找出增廣鏈 ， 第二個(gè)標(biāo)號(hào)是用來表示方向 *1 ( 0 , ) ,sssv V vv?開 始 ： 由 于 始 點(diǎn) 一 定 屬 于 ， 先 給 始 點(diǎn) 標(biāo) 上此 時(shí) 是 標(biāo) 號(hào) 但 是 未 檢 查 的 點(diǎn) 其 他 點(diǎn) 都 是 未 標(biāo) 號(hào) 的 點(diǎn)ijvv選 擇 標(biāo) 號(hào) 但 是 未 檢 查 的 點(diǎn) ， 對(duì) 于 一 切 未 標(biāo) 號(hào) 的 點(diǎn)( , ) , ( , ) ,i j i j i j jjv v f c v iv??若 在 弧 上 ， 則 給 標(biāo) 號(hào)則 變 為 標(biāo) 號(hào) 但 是 未 檢 查 的 點(diǎn) 否 則 不 標(biāo) 號(hào)( , ) 0 , ( , ) ,j i j i jjv v f v iv?若 在 弧 上 ， 則 給 標(biāo) 號(hào)則 變 為 標(biāo) 號(hào) 但 是 未 檢 查 的 點(diǎn) 否 則 不 標(biāo) 號(hào)從 vi出發(fā)的弧 進(jìn)入 vi的弧 根據(jù)圖中弧的容量限制，確定一個(gè)初始的可行流，可以取零流。 t s tv v v?重 復(fù) 上 面 的 步 驟 ， 一 旦 被 標(biāo) 上 號(hào) 就 得 到 了 一 條 從 到 的 增廣 鏈 ， 轉(zhuǎn) 入 調(diào) 整 過 程vi變?yōu)闃?biāo)號(hào)且已檢查的點(diǎn)，在 vi旁加上 *以示區(qū)別 如 果 所 有 的 標(biāo) 號(hào) 都 是 已 經(jīng) 檢 查 過 的 ， 但 是 標(biāo) 號(hào) 過 程 無法 進(jìn) 行 下 去 ， 算 法 結(jié) 束 ， 此 時(shí) 的 可 行 流 就 是 最 大 流 。 1“ ”tv（ ） 找 出 增 廣 鏈?zhǔn)?先 從 開 始 ， 對(duì) 已 標(biāo) 號(hào) 的 點(diǎn) 利 用 反 向 追 蹤 的 方 法上的弧是增廣鏈或，則弧的第一個(gè)標(biāo)號(hào)是假設(shè)?))v,v(()v,v(kvkttkt( , ) ( ( , ) )kki k k iv v iv v v v ?然 后 檢 查 ， 假 設(shè) 的 第 一 個(gè) 標(biāo) 號(hào) 是 ，則 弧 或 是 增 廣 鏈 上 的 弧isvv再 檢 查 ， 直 到 為 止( 2) ?以 為 調(diào) 整 量 進(jìn) 行 調(diào) 整( , )39。 ( , )( , )ij i jij ij i jij i jf v vf f v vf v v???????? ????? ? ??????39。39。 { }2ijff ?去 掉 所 有 點(diǎn) 的 標(biāo) 號(hào) ， 對(duì) 新 的 可 行 流回 到 步 驟 ， 重 新 進(jìn) 行 標(biāo) 號(hào)? ?12m i n ,? ? ??? ?? ?12m i nm i ni j i jijcff?????對(duì) 增 廣 鏈 上 的 前 向 弧對(duì) 增 廣 鏈 上 的 后 向 弧前向弧 后向弧 用標(biāo)號(hào)法求如下圖所示的網(wǎng)絡(luò)最大流 圖中已經(jīng)給出初始流。 vs v2 v1 v4 v3 vt (6,5) (10,4) (6,0) (5,2) vs v2 v1 v4 v3 vt (6,5) (10,4) (6,0) (5,2) (0,+) (s,+) * (1,+) (1,) (1,+) * * (4,+) 增廣鏈： (vs, v1, v4, vt) 2??* vs v2 v1 v4 v3 vt (6,5) (10,4) (6,0) (5,2) (0,+) (s,+) * (1,+) (1,+) * * (4+) 增廣鏈： (vs, v1, v3, vt) 1? ?(2,+) vs v2 v1 v4 v3 vt (6,5) (10,4) (6,0) (5,3) (0,+) * 無法再標(biāo)號(hào)，找到了最大流，流量為 10 課堂練習(xí)： P226,10（ a） ? 截集與截量 設(shè) S， T是 V的子集 ， S∩T=空集 ， 通常將始點(diǎn)在 S中 ， 終點(diǎn)在 T中的所有弧構(gòu)成的集合記為 (S,T) 111 1 1 1( , , ), ( , ) ,s t s tststD V A C V V Vv V v V V V v vvvvv???對(duì) 于 網(wǎng) 絡(luò) ， 若 點(diǎn) 集 被 剖 分 為 兩 個(gè) 非 空 集 合 和 ，使 得 ， 則 把 弧 集 稱 為 是 分 離 的 截 集如 果 把 截 集 中 的 弧 從 網(wǎng) 絡(luò) 中 去 掉 ， 則 從 到 便 不 存 在 路 ，即 截 集 是 從 到 的 必 經(jīng) 之 路 。111 1 1 11111( , ) ( , )( , ) ( , )( , )( , )ijijv v V VV V V Vc V Vc V V c?? ?給 定 一 個(gè) 截 集 ， 截 集 中 所 有 弧 的 容 量 之 和稱 為 這 個(gè) 截 集 的 容 量 ， 記 為 ， 即? 任何一個(gè)可行流的流量不會(huì)超過任何一個(gè)截集的容量，即 11( ) ( , )v f c V V?所有截集中容量最小的是一定是最大流，并且，則使得存在截集絡(luò)的一個(gè)可行流，如果網(wǎng)是網(wǎng)絡(luò)假設(shè))V,V(f)V,V(c)f(v)V,V(DDf*1*1**1*1**1*1*?
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1