[資工]交大103 資結 12題 max flow
出處:交大資聯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), 來自: 59.115.86.253
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1421250510.A.A0A.html
推
01/15 01:09, , 1F
01/15 01:09, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：