特定のノードの次数を最小にする最小スパニングツリー

Question

（すべての最小スパニングツリーの中で）ノードの次数を最小にする最小スパニングツリーを見つけるにはどうすればよいでしょうか。

同じ重さの複数のエッジがある場合には、vに触れないものを選択すると、問題を解決するKruskalアルゴリズムを修正しますか？

Answer 1

質問に部分的に答えるには、質問でスケッチされたKruskalのアルゴリズムを変更しても問題は解決しません。

V = {1,2,3}, 
E = {{1,2}, {2,3}, {3,1}}, 
w({1,2}) = 1, 
w({1,3}) = 1, 
w({2,3}) = 2 

と1が最小スパニングツリーの程度を最小化することとなっているノードであるグラフG=(V,E,w)を考えます。次に、エッジが

S1={{1,2},{1,3}} 

重量2の最小スパニングツリーを構成設定します。しかし、Kruskalのアルゴリズムの修正版は一般性を失うことなく、{1,2}を選択することにより、{1,3}が禁止され、{2,3}が選択される。合計では、選択されたエッジに

S2={{1,2},{2,3}} 

ノード1がS2においてより低い程度を有するセットが、S2の総重量は、最小スパニングツリーを構成しないことを意味し、3あります。さらに

は、最小化されるべきノードv度が少なくとも3最小スパニングツリーにおけるvつ以上の地域の可能性を有することでなければならないことに注意してください。

徹底的に検索すると、vの可能な近傍を選択してください。 vは最大でn近傍を有するので、そのような近傍は多くて2^nである。 Primによるアルゴリズムを使用して、これらのそれぞれを、選択された近隣を含むことに関してコスト最小のvのスパニングツリーに展開する。コスト最小のこれらすべてのソリューションでは、vの度合が最小になるソリューションを選択します。しかしながら、このアプローチは多項式時間アルゴリズムを生成しない。