作者skellroyal (skellroyal)
看板Grad-ProbAsk
標題Re: [資工]交大103 資結 12題 max flow
時間Thu Jan 15 01:19:44 2015
在"最後的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: 取這組的話也會cut到(A,C)和(B,C),它們不用算進去是因 01/15 07:57
→ qoojordon: 為沒有flow流過嗎 ? 為什麼(A,C)(B,C)沒算進cut值? 01/15 07:59
→ qoojordon: 先謝謝你的回答~ 01/15 08:00
推 shanbb: 樓上是跳針回兩個一樣嗎XD 01/15 10:47
→ shanbb: 結果電腦板是正常的囧，抱歉 01/15 11:12
→ shanbb: 我想是不是因為min cut上的邊必順向滿逆向空 01/15 11:14
→ shanbb: (A,C)(B,C)是逆向邊 01/15 11:16
→ qoojordon: 謝謝S大的想法,我想應該和你說的一樣,逆向邊不會貢獻 01/15 19:33
→ qoojordon: flow,所以求出來的cut恰巧不用算進容量的都是逆向邊 01/15 19:34
→ skellroyal: 定義的第2點，cormen是定義成cut的capacity， 01/15 21:20
→ skellroyal: 就是由S流向T的所有邊之capacity總和 01/15 21:21
推 qoojordon: 謝謝你~ 01/15 21:45