私の問題は、グラフ内の最小スパニング ツリーを見つけることです。しかし、各頂点の合計次数が一定の係数を超えてはならないというもう 1 つの制約が必要です。問題をモデル化するにはどうすればよいですか? MST は間違ったパスですか? 私に役立つアルゴリズムを知っていますか？
もう 1 つの問題: グラフのエッジの重みが重複しているため、一意の MST の数をカウントする方法はありますか? これを行うアルゴリズムはありますか?
ありがとうございました。
編集：度とは、頂点を接続するエッジの総数を意味します。重複するエッジの重みとは、2 つのエッジの重みが同じであることを意味します。
Garey Johnsonは、この問題をハミルトンに減らしました:(これは役に立ちました。最初の問題の概算：http：//caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt ただし、より良い作業モデルは高く評価されています...
カウント： http： //mathworld.wolfram.com/SpanningTree.html。これによると、数学には機能があります。これで何か提案はありますか？
まあ、解決策がないかもしれないことを証明するのは簡単です.入力グラフを、制限よりも高い次数を持つ頂点を持つツリーにするだけです..