最小スパニング ツリー問題の解決に行き詰まっている

Question

私の問題は、グラフ内の最小スパニング ツリーを見つけることに集約されました。しかし、もう 1 つ制約が必要です。 各頂点の次数の合計が特定の定数を超えてはなりません. 。自分の問題をモデル化するにはどうすればよいですか?MST は間違ったパスですか?役立つアルゴリズムを知っていますか?

もう 1 つ問題があります:私のグラフには重複したエッジの重みがあるので、一意の MST の数を数える方法はありますか?これを行うアルゴリズムはありますか?

ありがとう。

編集：程度とは、頂点を接続するエッジの総数を意味します。重複エッジの重みとは、2 つのエッジが同じ重みを持つことを意味します。

Answer 1

この論文では、多項式時間で、少なくとも次と同等の最大次数 d + 1 のスパニング ツリーを見つける方法を示します。 どれでも 最大次数 d のスパニング ツリー: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

//編集 元のリンクは現在非アクティブです。試してください http://research.microsoft.com/pubs/80193/mbdst.pdf その代わり。

Answer 2

まあ、それは解決策がないかもしれないことを証明するのは簡単です：ちょうどあなたの限界値よりも高い程度で頂点を持つ木のグラフあなたの入力を行う..

Answer 3

Gareyジョンソンは、この問題はハミルトンに減らしていた:(だから、これは助けた最初のものを近似：<のhref = "http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/プロジェクト/ m03.ppt」のrel = "nofollowをnoreferrer"> http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.pptする しかし、より良い作業モデルが評価されています...

カウンティング： http://mathworld.wolfram.com/SpanningTree.html に。これによると、Mathematicaは機能を持っています。この1で任意の提案ですか？