[理工] 離散 ch8. 最小切集

[ben4562002 (Bin)]

https://i.imgur.com/SJdyCsO.jpg
https://i.imgur.com/VcJWrzL.jpg

請問這題的minimum cut為何可以切出{a, b, d, f}為一組呢？
d跟f滿了應該要被排除在外(吧?)

感謝幫助解惑的各位了！
----
Sent from BePTT on my Sony G8142

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.164.177 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1576575438.A.17B.html
推 pyramidinc: 我不會離散的labeling 方法 只會畫residual network
→ pyramidinc: 如果從這個角度來看的話 因為a到c 還有路 所以d 和 f
→ pyramidinc: 可以透過c抵達 我的想法是這樣
→ pyramidinc: 有錯還請其他人指正
→ zuchang: 最大流量=最小切集 你就找哪條切線流量是10就好
→ zuchang: A->z 這種方向才要算 所以ef 那條2不算
推 mi981027: min cut在maxflow mincut thm的證明裡有說明找法
→ mi981027: 基本上就是s在residual network裡能走到的點都歸在S 剩
→ mi981027: 下就在T
→ mi981027: https://i.imgur.com/owDy7cq.jpg
→ ben4562002: 謝謝三位高手解惑xd用residual network去分兩個集合
→ ben4562002: 瞬間就懂了~