推 a19930301: 聽說要正確答案要用買的，不知哪有賣? 09/15 15:11
※ 引述《winnie48 (winnie)》之銘言：
: 先附上題目連結：
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/103/103424.pdf
: 就快要考試了，卻還是都找不到這份的相關討論，所以就po上自己寫的和大家討論！不過
: 這年的感覺有點難，有些不會的題目希望大家能給點提示~有錯誤的歡迎指正！
: 不會寫的題目有：
: 1(b) 這感覺蠻基本...、3(c)、4
: 謝謝！大家加油！
: http://i.imgur.com/gPRLRxT.jpg
: http://i.imgur.com/VfrkNFE.jpg
: http://i.imgur.com/d56ynn5.jpg
3(c)
(1)證明degree k-spanning tree為NP
給定一圖G=(V, E)，與G之子圖T=(V', E')，
應可找到一verification algorithm，使其確認
是否V=V'，T內是否有cycle，每個頂點的degree是否超過k。
此演算法可於polynomial time內完成。
(2)Ham-path<=p degree-k spanning tree
假設現有一演算法A(k)可解degree-k spanning tree，
演算法A(k)可決定一圖G中是否存在一spanning tree且其頂點之度數最高為k。
今以k=2代入，即相當於解Ham-path問題。若A(2)有解，表示G中有Ham-path，
若A(2)無解，則G中無Ham-path。
因為若一樹中之頂點最高度數為2，該樹為一條路徑(path)。
由(1), (2)可證明 bounded-degree spanning tree為 NP complete.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.115.4
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1473921932.A.143.html
※ 編輯: tzutengweng (36.228.115.4), 09/15/2016 14:45:59