use*_*882 11 tree graph np-complete
我理解为什么有界度生成树被认为是NP完全的度数或2(它是哈密顿路径问题的一个实例),但我不明白为什么这适用于度> 2.如果有人可以请解释为什么这是对于程度> 2的NP完全问题,这将是最有帮助的
Bar*_*nio 15
好吧,我认为你可以从2的边界实例到General k的实例进行简单的简化.
直觉上,我们将连接到原始图形的新k-2节点的每个节点.因此,每个生成树必须包含从原始节点到我们连接到他的新节点的k-2边,如果存在最多2度的生成树,则存在最多度为k的生成树.原始图.
正式减少将是:
F(V,E)=(V',E'),当:V'= {(v,i)| v在原始图中,0 <i <k + 1),E'= EU {(( v,0),(v,i))},我没有写正确的正式证据,因为毕竟我们不在数学论坛.
祝你好运并希望它有所帮助:)