網路的最大流和最小截(編輯修改稿)
2025-06-18 06:10 本頁面
【文章內容簡介】 點在 V 中，未獲標號節(jié)點在 V 中， V 與 V 間的弧即為最小截集；算法結束 (2)節(jié)點 t 獲得標號，找到一條增廣鏈，由節(jié)點 t 標號回溯可找出該增廣鏈；到第二步 5 最大流最小截的標號法步驟 第二步：增廣過程 對 增廣鏈中的前向弧，令 f?=f+q(t)， q(t) 為節(jié)點 t 的標記值 對 增廣鏈中的后向弧，令 f?=f?q(t) 非增廣鏈上的所有支路流量保持不變 第三步：抹除圖上所有標號，回到第一步 ? 以上算法是按廣探法描述的，但在實際圖上作業(yè)時，按深探法進行更快捷 ? 一次只找一條增廣鏈，增廣一次換一張圖 ? 最后一次用廣探法，以便找出最小截集 6 最大流最小截集的標號法舉例 s t13 42 56(14, 14)(9,9)(15 , 9)(16 , 15 )(3,1)(12 , 10 )(6,6)(4, 3)(5,5)(22, 22)(13, 12)(7,5)(6,3)(19, 10)s t13 42 56(14, 14)(9,9)(15 , 10 )(16 , 15 )(3,1)(12 , 10 )(6,5)(4, 4)(5,5)(22, 22)(13, 12)(7,5)(6,3)(19, 11)(s+,?) (s+,6) (2?,6) (3+,1) (4+,1) (s+,?) (s+,5) (2+,2) (5?,2) (4+,2) 7 最大流最小截集的標號法舉例
環(huán)評公示相關推薦
鄂ICP備17016276號-1