幾個觀念請教
http://ppt.cc/9uZQ
http://ppt.cc/2jHQ
[NCTU 100 19題組(54)]
Problem I 是 constraint TSP
Problem III 是 H.C. (Hamilton Cycle)
題幹的敘述是 III reduce到 I , 印象中, 兩個問題之間證明reduce關係
需要說明兩個問題能再多項式複雜度內的轉換下,彼此互相對應
　　G有H.C. 　←→　G'在constraint n(1+e)內有TSP
註: G'是加入題幹中D[i,j]修正後的圖
不知道我這樣解釋正確嗎 ?
[NCTU 99]
想找反例
解釋是因為只增加某根capacity仍無確保多出來的flow可以透過augment path 到達t嗎?
[NCTU98]
我自己標了幾個比較噁心的複雜度 , 好奇他們之間的比序關係是?
a < e < b < d < c < f
[NCTU 97 4(7)]
查版上之前分享的答案是T , 不過好像爭議不多 , 沒有太多討論
WIKI上的weight-balance tree的敘述和題幹說明不太類似??
http://en.wikipedia.org/wiki/Weight-balanced_tree
[NCTU 97 6]
版上之前的分享答案是 (c,d)增加到4 , max flow=5
不過我直接把附圖當成沒有作完的 residual network不用增加(c,d)得到也是5
min cut在(s,a),(s,c),(s,e)
不曉得2,3小題之間是不是我誤會了甚麼主要的概念 ?

99. s->m->t 容量都是1 則不管增加哪條容量 都只能流過1

100 (54) B只要是 n ~ n(1+e)+1 之間的數字都可以因為只是要產生一個gap而已 這是一種reduction的技巧99 反例是個有多個min-cut的graph97 4(7) usually determined <- 這定義得很模糊..

複雜的那題是a>e 喔 e是常數

reduce是這樣沒錯啊 最困難的就是第一步課本上的reduce大多都是性質相近的問題 所以步驟123不難

推一下 我也想知道97 6 23小題 有人會嗎？

想問一下reduce為啥要證雙向？