大家晚安
有幾題資演想請教~
20.
(58)
http://i.imgur.com/TShP2Xu.jpg
想問(58)題的C為什麼是對的呢?
Ford-Fulkerson複雜度不是|f*|E嗎，應該跟capacity無關?
19.
http://i.imgur.com/O2UOidz.jpg
http://i.imgur.com/71MWKtm.jpg
想問的是
promblem1是在說哪個問題?
problem2是TSP嗎?(TSP可以讓每條邊加權值是1?)
problem3是LP嗎?(LP可以讓每條邊加權值是1?)
(57)的D是什麼詭異的敘述!?不知道怎麼問，但就是...想問xd
17.
(51)
http://i.imgur.com/InGHWGN.jpg
這題也是很詭異，怎麼看出他可以化成D選項的呢?
(E)又是哪裡錯?為什麼無法表示全部?
先謝謝各位了~祝大家考試順利

題組19. 分別是HP/Shortest-path/Longest-path

58.C) 我認為是: f*是最大流量，而minimum cut <->flow達到capcity。又flow加起來= capacity. D)每邊的capacity 都不同，不一定min cut就唯一。57)prob1:我覺得是TSP 因為他說degree at most 2, 又想到Hamilton cycle過每點之恰兩邊

感謝樓上各位大大我再想想看