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

[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), 來自: 59.115.86.253
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1421250510.A.A0A.html
推 FRAXIS: min-cut是{S, C}