[理工] Minimum-cut一問

[ssssIssss (O_O)]

這個問題一直卡很久了，每次都模模糊糊的帶過Orz

想請教一下，怎麼用Max-flow來切minimum-cut呢？

是直接找（從源點往匯點的path-回流）加起來會是max-flow的地方切嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486391672.A.21E.html
推 hypnos135g: 順滿逆空
→ hypnos135g: 即滿足cut capacity
→ joeboy: 你的capacity跟你的flow一樣他就是min cut
但是有時候並不一定會滿到跟capacity一樣@@
推 yupog2003: 我都是想像從source流出一堆水，流到不能再流，所經過
→ yupog2003: 的點就是min cut的一側，其他點是另一側，然後切下去
→ yupog2003: 就會是min cut
好抽象@@ 有什麼固定的找法嗎

懂了，我發現我昨天腦袋壞了，感謝yu大！
※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 08:59:52
推 FRAXIS: 找 maximum flow 的 residual network
→ FRAXIS: 此時 residual network 會是 disconnected 的
→ FRAXIS: 令在 residual network 上與 source 連通的點集為 S
→ FRAXIS: 所有 S 連向 非 S 且不在 residual network 的邊
→ FRAXIS: 應該就是一個 min-cut 了
太棒了！完全理解！感謝F大！
推 hypnos135g: "cut" capacity 會滿哦 不是單一edge的capacity
→ hypnos135g: cut capcity=sum 順向的flow edge capacity
推 hypnos135g: 一個network有多條cut 每條cut有自己的capacity 代表
→ hypnos135g: 這條cut 最多可流出的量 而我們要找所有cut中capacity
→ hypnos135g: 最小的就會是max flow 所以才叫minimum cut(我的想法)
→ hypnos135g: 因為每條cut代表整個network可流出的量的限制(宏觀)。
→ hypnos135g: 而min cut就是最嚴格的限制
對的，我發現我誤算誤理解了@@感謝h大！！
※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 12:31:36