Bounded Degree Spanning Tree が次数または 2 の NP 完全と見なされる理由は理解していますが (これはハミルトニアン パス問題のインスタンスです)、なぜこれが次数 > 2 に適用されるのかわかりません。次数が 2 を超える NP 完全問題。
10685 次
1 に答える
15
さて、2で囲まれたインスタンスからGeneralkのインスタンスに簡単に縮小できると思います。
直感的には、元のグラフの各ノードに新しい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））}、そして私は正しさの正式な証明を書きません。結局のところ、私たちは数学のフォーラムにいないからです。
頑張って、それが役に立ったことを願っています:)
于 2011-10-21T10:45:20.143 に答える