[離散]P123

[zxm20243 ( )]

我不確定這個看法是不是對的

所以丟上來請問大家QQ

補真相http://tinyurl.com/4c34njv


對於所有可能存在的F，都應該要滿足P121的式子

由等號右邊得知F <= c(S)

考慮每種存在F，S的切法有很多，所以F要滿足每種c(S)

既然每種c(S)都要滿足，所以對於最小的c(S)仍然要滿足

也就是說，當我們找到一種F = c(S)時

我們就找到了min c(S)

(假設不是min c(S)，那麼這個F必然>min c(S)，矛盾)

同理，也就是我們找到了Maximum flow


不曉得這個解釋OK不OK

先感謝大家的指教了QQ

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.34
推 gn00499901:基本上沒錯吧，挑毛病的話就是：F必然">"min c(S)
→ gn00499901:當然寫">="邏輯也沒錯啦，因為我們已經假設不會"="
已修正，感謝烏龜>////<

因為老師講義上的結論下太快了跟不上QQ

所以想要確定一下我這樣想對不對@@
※ 編輯: zxm20243        來自: 140.112.249.34       (01/11 16:19)
推 jessica1338:這個會有問題嗎?@@
推 pinkyenyen:這位同學好會猜題喔！