私はグラフの最小スパニングツリーを見つけることに問題を軽減しました。しかし、もう一つの制約があります。それは、各頂点の総次数がある定数係数を超えてはならないということです。私の問題をモデル化するにはどうすればいいですか？ MSTは間違った経路ですか？私を助けるアルゴリズムを知っていますか？最小スパニングツリーの問題を解決することに固執しました
もう1つの問題：グラフに重複したエッジウェイトがあるため、一意のMSTの数を数える方法はありますか？これを行うアルゴリズムはありますか？
ありがとうございます。
編集：程度では、私は頂点を接続する辺の総数を意味します。エッジ重みを重複することによって、2つのエッジが同じ重みを持つことを意味します。
。？この論文では、多項式時間、最大次数dの少なくともとして良い任意のとしてスパニングツリーで最大次数d + 1のスパニングツリー：http://www.andrew.cmu.edu/user/mohits/mbdst.pdf
//編集元のリンクは現在停止していること、代わりにhttp://research.microsoft.com/pubs/80193/mbdst.pdfを試してみてください。
Haventは全体を読んでいますが、本当に便利です。ありがとう。 – unj2
まあ、それは解決策がないかもしれないことを証明するのは簡単です：ちょうどあなたの限界値よりも高い程度で頂点を持つ木のグラフあなたの入力を行う。..
負荷係数を総重量制約よりも高くするとどうなりますか？それは、私が2番目の最小または3分の1の最小値に対応しようとしていることです。しかし、それはより多くの問題を生むかもしれない経験則を必要とする。たとえば、どのエッジを置き換えるかはどのように決定しますか？神はこの問題を解決する別の方法がありますか？ – unj2
私は分かりません。あなたはあなたの問題が何であるか教えてくれません:-)しかし、deg <= n ...を持つすべての頂点を持つスパニングツリーが必要な場合は、スパニングツリー（最小限またはそれ以外）が含まれているグラフを考え出すことができます次数n + 1を有する少なくとも1つの頂点。ヒューリスティックはその状況であなたを助けません。 –
Gareyジョンソンは、この問題はハミルトンに減らしました： 。（だから、この1は最初のものを近似助け：http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt しかし、より良い労働モデルは...
カウント評価されています：。http://mathworld.wolfram.com/SpanningTree.htmlこれによると、Mathematicaは機能を持っているこのいずれかで任意の提案を
マトリックスツリー定理（mathworldで参照されています）を掘り下げれば、あるスパニングツリーを体系的に別のものに変える方法を見つけることができます。あなたがそれを行うことができれば、あなたの目的に合ったものを見つけるまで、スパニングツリーを循環させることができます。しかし、これはすべて野生の推測です。保証はありません:-) –
単純にkruskalアルゴリズムを適用して、最大次数のノードに接続されている括弧をリストから削除することはできますが、それが最適解を決定するかどうかはわかりません。 ） – akappa
それ以外の場合は、完全なkruskalアルゴリズムを適用し、次にいくつかのローカル検索手法を使用して有効なスパニングツリーを取得できます。 – akappa