algorithm - グラフに少なくとも X 個の最小スパニング ツリーがあるかどうかを確認するにはどうすればよいですか?

Question

グラフに少なくとも 'X' 個の MST が存在するかどうかを調べるための効率的なアルゴリズムを探しています。ポインタはありますか？

Answer 1

これは完全なアルゴリズムを具体化するものではありませんが、An algorithm to see if there are just two MSTs in a graph?に対する受け入れられた回答です。(by @j_random_hacker) は、おそらく非常に役立つポイントを提示します。彼の答えから取られた：

さらに、すべてのMST は、重みが等しいエッジのすべてのセットを順序付けする特定の方法を選択してから、Kruskal アルゴリズムを実行することによって生成できます。

おそらく、これを利用して MST の数を取得するアルゴリズムを作成できます。まあ、この事実をそのまま利用するだけでは、おそらく「効率的なアルゴリズム」の領域に到達することはありませんが、効率的なアルゴリズムはいくつかの同様の事実を利用することになると思います。また結果が出たら追記します。