出處:交大資聯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
會比較小但不一定會相等 , 我是不是誤解了甚麼@@"