私の質問：
G(V,E) を全結合グラフとします。ここで、V はノードの集合であり、E はリンクの集合です。スパニング ツリーが辞書順でソートされている場合、グラフ内のすべてのリンクをカバーするために必要なスパニング ツリーの最小数の上限 (最悪の場合) は?
例として、|V|=4、したがって |E|=6 の場合、G(V,E) には次の 16 個のスパニング ツリーが含まれます (辞書順)。リンクに異なるラベルを付けると、スパニング ツリーの順序が異なる場合があることに注意してください。
1 2 3
1 2 4
1 2 6
1 3 4
1 3 5
1 3 6
1 4 5
1 5 6
2 3 4
2 3 5
2 4 5
2 4 6
2 5 6
3 4 6
3 5 6
4 5 6
この場合、グラフ内のすべてのリンクをカバーするために必要なスパニング ツリーの最小数は、5 つのスパニング ツリー ({1 2 3}、{1 2 4}、{1 2 6}、{1 3 4}、{ 1 3 5})。したがって、すべてのリンクはこれら 5 つのスパニング ツリーに含まれます。
小さなグラフのスパニング ツリーの数を数えるのは簡単ですが、大きなサイズのグラフ (たとえば |V|>4) では問題があります。
グラフ内のすべてのリンクをカバーするスパニング ツリーの上限数を計算する式はありますか?
どうもありがとう