作者zxm20243 ( )
看板b98902HW
標題[離散]P123
時間Tue Jan 11 15:30:39 2011
我不確定這個看法是不是對的
所以丟上來請問大家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
1F：推 gn00499901:基本上沒錯吧，挑毛病的話就是：F必然">"min c(S) 01/11 16:12
2F：→ gn00499901:當然寫">="邏輯也沒錯啦，因為我們已經假設不會"=" 01/11 16:14
已修正，感謝烏龜>////<
因為老師講義上的結論下太快了跟不上QQ
所以想要確定一下我這樣想對不對@@
※ 編輯: zxm20243 來自: 140.112.249.34 (01/11 16:19)
3F：推 jessica1338:這個會有問題嗎?@@ 01/11 18:38
4F：推 pinkyenyen:這位同學好會猜題喔！ 01/13 23:10