Re: [資工]交大103 資結 12題 max flow

看板Grad-ProbAsk作者skellroyal (skellroyal)時間9年前 (2015/01/15 01:19)推噓3(3推 0噓 9→)

留言12則, 3人參與討論串2/2 (看更多)

在"最後的residual network"中，令S:{自S可到的點}, T:{自S不可到的點} 則(S,T)是"原本"flow network的min-cut (題目的圖) min-cut:(S,T)滿足: 1. S∪T=V 且 S∩T={} 2. S->T的邊的weight和為所有cut中最小我想你說的"min-cut值"，應該是第2點提到的weight和，因為max flow的值會被所有cut的值給限制，又min-cut的值是所有cut中最小的，所以max flow值就會等於min-cut的值 (cormen p723) 以交大這題為例，min-cut為S={S,C},T={A,B,D,T} (因為S只能走到C) max flow為5，原本的圖S->T的邊有(S,A)和(C,D)它們的weight加總為2+3=5 ※ 引述《qoojordon (穎川琦)》之銘言： : 出處:交大資聯103 12題 : Q1-1: : 一flow network 如下圖 , 求min cut =? : 3 : A——→B 4 : 2↗｜／↑↘ : S ｜1 ／3 ｜1 T : 4↘↓↙ ｜↗3 : C——→D : 3 : 回頭看以前沒寫完整的題目有不確定自己是否正確 : 做完FF Algo (flow) : 2,3 : 2,2 A——→B 2,4 : ↗｜0,1 ／↑↘ : S ｜／｜0,1T : 3,4↘↓↙0,3 ｜↗ : C——→D 3,3 : 3,3 : 我求出來的max flow =5 : min cut=({S} , {A,B,C,D,T} ) 即切到的edge set為上圖黃色標記 : 定理的max flow = min cut , min cut的值是怎麼取的? : 假設我min cut是取正確的 , 所以min cut代表的值 = 2+3 ? (是取cut上的flow加總?) : 因為小黃書上寫的cut值是"切集的容量" , 依這個定義取出來的值(2+4)只能保證max flow : 會比較小但不一定會相等 , 我是不是誤解了甚麼@@" -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.0.129 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1421255986.A.0E2.html ※ 編輯: skellroyal (1.160.0.129), 01/15/2015 01:23:14

推

qoojordon

01/15 07:57, , 1^F

01/15 07:57, 1^F

→

qoojordon

01/15 07:59, , 2^F

01/15 07:59, 2^F

→

qoojordon

01/15 08:00, , 3^F

01/15 08:00, 3^F