[資工] 交大100-97 DS&Algo數題

[qoojordon (穎川琦)]

幾個觀念請教

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小題之間是不是我誤會了甚麼主要的概念 ?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.25.63
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422021068.A.58E.html
→ kather: 99. s->m->t 容量都是1 則不管增加哪條容量 都只能流過1
推 FRAXIS: 100 (54) B只要是 n ~ n(1+e)+1 之間的數字都可以
→ FRAXIS: 因為只是要產生一個gap而已  這是一種reduction的技巧
→ FRAXIS: 99 反例是個有多個min-cut的graph
→ FRAXIS: 97 4(7) usually determined <- 這定義得很模糊..
F大在請教一下,如果要正式的證明reduce

我看到的手法幾乎都同一個套路

1.先想出一個轉換的方式

2.證明(==>) , 在原問題上取出條件成立情形(此例即為G具有H.C.) ,

             會mapping到轉換後的 某個條件成立情形
             (此例為G'滿足n ~ n(1+e)+1 TSP之限制)

             故得證(==>)

3.證明(<==) , 我每次證這一步都會像在說廢話,以此題為例就只是把(==>)反過來講

  於G'中存在滿足n ~ n(1+e)+1 constraint的TSP時 G會具有H.C.

  故得證(<==)


我上述的 2 , 3有犯錯嗎? , 感覺幾乎1的轉換方式想到了就等於證明完了....
※ 編輯: qoojordon (111.251.25.63), 01/23/2015 23:02:11
推 killerw74: 複雜的那題是a>e 喔 e是常數
推 FRAXIS: reduce是這樣沒錯啊 最困難的就是第一步
→ FRAXIS: 課本上的reduce大多都是性質相近的問題 所以步驟123不難
推 guo1111: 推一下 我也想知道97 6 23小題 有人會嗎？
推 galapous: 想問一下reduce為啥要證雙向？