網(wǎng)路的最大流和最小截(已修改)
2025-05-29 06:10 本頁面
【正文】 1 網(wǎng)路的最大流和最小截 網(wǎng)路的最大流的概念 ? 網(wǎng)路流一般在有向圖上討論 ? 定義網(wǎng)路上支路的 容量 為其最大通過能力，記為 cij ，支路上的實(shí)際 流量 記為 fij ? 圖中規(guī)定一個(gè)發(fā)點(diǎn) s，一個(gè)收點(diǎn) t ? 節(jié)點(diǎn)沒有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ) ? 容量限制條件 ： 0? fij ? cij ? 平衡條件 ： ??????????? ????tifvtsisifvffijij vBvjivAvij)(,0)()()(? 滿足上述條件的網(wǎng)路流稱為 可行流 ，總存在 最大可行流 ? 當(dāng)支路上 fij = cij ，稱為 飽和弧 ? 最大流問題也是一個(gè)線性規(guī)劃問題 vi A(vi) B(vi) 2 截集與截集容量 定義 ：把網(wǎng)路分割為兩個(gè)成分的弧的最小集合，其中一 個(gè)成分包含 s 點(diǎn)，另一個(gè)包含 t 點(diǎn) 。 ? 一般包含 s 點(diǎn)的成分中的節(jié)點(diǎn)集合用 V表示，包含 t 點(diǎn)的成分中的節(jié)點(diǎn)集合用 V表示 ? 截集容量 是指截集中正向弧的容量之和 ????VjVi ijcVVC ),(? 福特 富克森定理 ：網(wǎng)路的最大流等于最小截集容量 s t5342( 4,0)( 3,0)( 2,0)( 1,0)( 1,0)( 5,0)( 3,0)( 2,0)( 5,0)3 確定網(wǎng)路最大流的標(biāo)號(hào)法 ? 從任一個(gè)初始可行流出發(fā)，如 0 流 ? 基本算法：找一條從 s 到 t 點(diǎn)的 增廣鏈 (augmenting path) ? 若在當(dāng)前可行流下找不到增廣鏈，則已得
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1