接続された無向グラフが与えられた場合、最大次数が最小のスパニング ツリーを見つける問題はよく研究されています (M. F¨urer、B. Raghvachari、「最小次数スパニング ツリーを最適次数から 1 以内に近似する」、離散アルゴリズムに関する ACM-SIAM シンポジウム (SODA)、1992 年)。この問題は NP 困難であり、近似アルゴリズムは参考文献に記載されています。
私は次の問題に興味があります - 接続された無向グラフ G = (V1,V2,E) が与えられた場合、すべての内部ノード (非葉ノード) で最小次数が最大のスパニング ツリーを見つけます。この問題が研究されているかどうか誰か教えてください。それはNP困難ですか、それともそれを解決するための多項式時間アルゴリズムが存在しますか? また、便宜上、グラフは二部グラフと見なすことができます。
3セットで正確にカバーすることで、この問題を解決できるようです。次数 4 の頂点によって 3 セットを表します。各セットには、元の問題インスタンスの要素を表す 3 つのノードに接続する 3 つのエッジがあります。追加の 4 番目のエッジは、すべての「3 セット」ノードを単一の頂点 V に接続します。
このグラフはバイパライトです。すべてのエッジは「3 セット」ノードと「要素」ノード (または V) の間にあります。このグラフには、元の問題に解決策がある場合に限り、最大最小次数 = 4 のスパニング ツリーがあります。
明らかに、ノード V がツリーの最大最小次数を下げないように十分な 3 セットが必要ですが、この制限は問題の NP 困難性を変更しません。
Evgeny Kluev のコメントで述べたように、(有限) ツリーの葉の次数は 1 です (そうでなければ、サイクルが存在し、構造はツリーではありません)。
代わりに、接続された無向グラフ G 上のすべての可能なスパニング ツリーの中から最大次数のノードを持つスパニング ツリーを見つけることを意図している場合は、ルート R がすべての中で最大次数を持つ G のノード M であるスパニング ツリーを形成します。 G のノードであり、M のすべての隣接ノードは R の子です。