[理工] Minimum-cut一問

看板Grad-ProbAsk作者 (O_O)時間8年前 (2017/02/06 22:34), 8年前編輯推噓5(5推 0噓 13→)
留言18則, 4人參與, 最新討論串1/1
這個問題一直卡很久了，每次都模模糊糊的帶過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
推
02/06 22:46, , 1F
順滿逆空
02/06 22:46, 1F
→
02/06 22:47, , 2F
即滿足cut capacity
02/06 22:47, 2F
→
02/06 23:02, , 3F
你的capacity跟你的flow一樣他就是min cut
02/06 23:02, 3F
但是有時候並不一定會滿到跟capacity一樣@@
推
02/07 06:07, , 4F
我都是想像從source流出一堆水，流到不能再流，所經過
02/07 06:07, 4F
→
02/07 06:08, , 5F
的點就是min cut的一側，其他點是另一側，然後切下去
02/07 06:08, 5F
→
02/07 06:08, , 6F
就會是min cut
02/07 06:08, 6F
好抽象@@ 有什麼固定的找法嗎 懂了，我發現我昨天腦袋壞了，感謝yu大！ ※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 08:59:52
推
02/07 09:03, , 7F
找 maximum flow 的 residual network
02/07 09:03, 7F
→
02/07 09:03, , 8F
此時 residual network 會是 disconnected 的
02/07 09:03, 8F
→
02/07 09:04, , 9F
令在 residual network 上與 source 連通的點集為 S
02/07 09:04, 9F
→
02/07 09:06, , 10F
所有 S 連向 非 S 且不在 residual network 的邊
02/07 09:06, 10F
→
02/07 09:06, , 11F
應該就是一個 min-cut 了
02/07 09:06, 11F
太棒了！完全理解！感謝F大！
推
02/07 11:04, , 12F
"cut" capacity 會滿哦 不是單一edge的capacity
02/07 11:04, 12F
→
02/07 11:06, , 13F
cut capcity=sum 順向的flow edge capacity
02/07 11:06, 13F
推
02/07 11:08, , 14F
一個network有多條cut 每條cut有自己的capacity 代表
02/07 11:08, 14F
→
02/07 11:08, , 15F
這條cut 最多可流出的量 而我們要找所有cut中capacity
02/07 11:08, 15F
→
02/07 11:08, , 16F
最小的就會是max flow 所以才叫minimum cut(我的想法)
02/07 11:08, 16F
→
02/07 11:27, , 17F
因為每條cut代表整個network可流出的量的限制(宏觀)。
02/07 11:27, 17F
→
02/07 11:27, , 18F
而min cut就是最嚴格的限制
02/07 11:27, 18F
對的，我發現我誤算誤理解了@@感謝h大！！ ※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 12:31:36
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1Oc8bu8U (Grad-ProbAsk)