[理工] 101交大資演

看板Grad-ProbAsk作者 (揪立)時間7年前 (2017/01/25 22:54), 編輯推噓4(4推 0噓 13→)
留言17則, 5人參與, 最新討論串1/4 (看更多)
http://i.imgur.com/B82S6aJ.jpg
想問一下愛為什麼最後一題的c錯 B選項如果我的cut不是min cut那他的flow不就不是最大嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.182.68 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485356084.A.FC6.html
推
01/25 23:00, , 1F
B.如果不是min cut那就會大於f了C.cut數量應該不只O
01/25 23:00, 1F
→
01/25 23:00, , 2F
(n)個
01/25 23:00, 2F
→
01/25 23:09, , 3F
B選項的f沒有說是最大流吧？
01/25 23:09, 3F
→
01/25 23:25, , 4F
cut值大於等於flow值，等於成立於min cut max flow
01/25 23:25, 4F
推
01/25 23:27, , 5F
你的陳述有矛盾 最大流量僅能滿足min cut
01/25 23:27, 5F
→
01/25 23:27, , 6F
又怎麼能滿足比min cut更大的cut?
01/25 23:27, 6F
推
01/25 23:41, , 7F
所以b應該是錯的吧？ 可能比最大流還要大
01/25 23:41, 7F
→
01/26 08:17, , 8F
B是對的，因為他已經寫等於了，那就是max flow
01/26 08:17, 8F
推
01/26 08:36, , 9F
任何cut的capacity值確實可能比max flow大，但是當某個
01/26 08:36, 9F
→
01/26 08:37, , 10F
cut的capacity值跟flow相同時，代表這個cut已經無法容
01/26 08:37, 10F
→
01/26 08:37, , 11F
納更多flow流過去了，所以任何從source跑出來的流量跑
01/26 08:37, 11F
→
01/26 08:38, , 12F
到這個cut一定會被卡住，所以這個flow一定就是max flow
01/26 08:38, 12F
→
01/26 08:39, , 13F
沒錯
01/26 08:39, 13F
→
01/26 08:40, , 14F
此時這個cut就會是minimum cut
01/26 08:40, 14F
→
01/26 08:42, , 15F
我一開始也是被min cut的字義上給混淆了，也覺得cut
01/26 08:42, 15F
→
01/26 08:43, , 16F
不是min cut那個flow就不是max flow，但是當該flow等於
01/26 08:43, 16F
→
01/26 08:43, , 17F
某個cut的capacity時，那個cut就會成為min cut了
01/26 08:43, 17F
‣ 更多 joeboy 的文章
文章代碼(AID): #1OYBmq_6 (Grad-ProbAsk)
‣ 更多 joeboy 的文章
文章代碼(AID): #1OYBmq_6 (Grad-ProbAsk)