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

作者: skellroyal (skellroyal)   2015-01-15 01:19:44
在"最後的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
: 會比較小但不一定會相等 , 我是不是誤解了甚麼@@"
作者: qoojordon (穎川琦)   2015-01-15 07:57:00
取這組的話也會cut到(A,C)和(B,C),它們不用算進去是因為沒有flow流過嗎 ? 為什麼(A,C)(B,C)沒算進cut值?先謝謝你的回答~
作者: shanbb (Moriz)   2015-01-15 10:47:00
樓上是跳針回兩個一樣嗎XD結果電腦板是正常的囧,抱歉我想是不是因為min cut上的邊必順向滿逆向空(A,C)(B,C)是逆向邊
作者: qoojordon (穎川琦)   2015-01-15 19:33:00
謝謝S大的想法,我想應該和你說的一樣,逆向邊不會貢獻flow,所以求出來的cut恰巧不用算進容量的都是逆向邊
作者: skellroyal (skellroyal)   2015-01-15 21:20:00
定義的第2點,cormen是定義成cut的capacity,就是由S流向T的所有邊之capacity總和
作者: qoojordon (穎川琦)   2015-01-15 21:45:00
謝謝你~

Links booklink

Contact Us: admin [ a t ] ucptt.com