※ 引述《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.