作者godjoker87 (小吴君)
看板Grad-ProbAsk
标题[理工] 103清大计科12
时间Fri Jan 28 22:51:24 2022
https://i.imgur.com/R19ie8P.jpg
想问这题
没有想法不知如何下手
有找到说可以reduce到HP问题
但是HP每个点degree为二，但这个为k
不知道是怎麽reduce的 希望大神教学
非常感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.116.1.141 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1643381486.A.A00.html
1F：推 timisfool: 之前整理的，可以参考一下 01/28 23:51
3F：推 NCTUCKCurry: 应该是HP可以reduce成degree constrained spinning t 01/29 09:41
4F：→ NCTUCKCurry: ree才对 01/29 09:41
5F：推 NCTUCKCurry: HP的degree为2 就是degree constrained spanning tre 01/29 10:35
6F：→ NCTUCKCurry: e的一个instance了啊 也就是k=2 这样就可以了 01/29 10:35
7F：推 joywilliamjo: HP不就是2 spanning tree的一个特例吗？ 01/29 15:54