在"最後的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
: 會比較小但不一定會相等 , 我是不是誤解了甚麼@@"