Re: [圖論] 求定理和證明解釋
※ 引述《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
討論串 (同標題文章)