作者icebergvodka (肥嘟嘟左卫门)
看板Math
标题Re: [图论] 求定理和证明解释
时间Thu Jan 6 04:16:59 2011
※ 引述《icebergvodka (肥嘟嘟左卫门)》之铭言：
: Max-flow Min-cut theorem
: 这个定理我看了好久还是搞不太清楚它到底想表达什麽= =
: 更别说要看懂他的证明了QQ
: 请版上的神大们出手解救一下Orz
看了很久还是搞不太懂..
我看的这个版本证明应该是想要证明total value最大会等於最小的负载量c吧
这版的符号是写作|f_n|=c_n <-想证明这件事
之後又先令一个路径经过的点所成的集合S_n
我的问题就在这里:
if t在S_n里的话
为什麽它最後是证出|f_(n+1)|>|f_n|呢??
跟一开始的claim关联在哪??
然後:
if t不在S_n的case的证明里
S_n会形成一个cut这没问题,可是为什麽f_n(e)就等於c(e)了??
这两个部份实在是看不懂= =
希望能有专业出手帮忙解答一下QQ
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.26.20.110