[理工] 103清大計科12

[godjoker87 (小吳君)]

https://i.imgur.com/R19ie8P.jpg

想問這題
沒有想法不知如何下手
有找到說可以reduce到HP問題
但是HP每個點degree為二，但這個為k
不知道是怎麼reduce的 希望大神教學
非常感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.1.141 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1643381486.A.A00.html
推 timisfool:  之前整理的，可以參考一下
→ timisfool: https://i.imgur.com/HYHNSa2.jpg
推 NCTUCKCurry: 應該是HP可以reduce成degree constrained spinning t
→ NCTUCKCurry: ree才對
推 NCTUCKCurry: HP的degree為2 就是degree constrained spanning tre
→ NCTUCKCurry: e的一個instance了啊 也就是k=2 這樣就可以了
推 joywilliamjo: HP不就是2 spanning tree的一個特例嗎？