algorithm - 特定のエッジのセットを含むスパニングツリーの総数を計算する

Question

私は次のアプローチを試しました：

まず、指定されたエッジのセット内のすべてのエッジに対してエッジ収縮を実行して、修正されたグラフを作成します。

次に、修正されたグラフから、行列ツリーの定理を使用して、スパニングツリーの総数を計算します。

この方法が正しいかどうか、そして他にもっと良い方法があるかどうか知りたいです。

Answer 1

正しいかどうかはわかりませんが、エッジの収縮によってエッジが平行になる可能性があることに注意する必要があります。平行エッジが使用されているだけで異なるツリーが、別個のものとしてカウントされることを確認する必要があります。

Answer 2

Gをグラフ、eをエッジ、G/eをeを縮小した同じグラフとします。それで、

命題：eを含むGの全域木とG/eの全域木の間には全単射があります。

この命題を証明するのは難しいことではありません。他の人にそれが本当かどうか尋ねるよりも、自分で証明を理解するほうがよいでしょう。明らかに、eを含むGのスパニングTツリーがある場合、T/eはG/eのスパニングツリーです。考え抜くのは、後戻りすることもできるということです。

また、Adamが指摘しているように、平行なエッジを持つグラフと、頂点からそれ自体へのエッジを持つグラフを適切に処理するように注意する必要があります。