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

Question

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

最初に、特定のエッジセットのすべてのエッジに対してエッジ収縮を行い、変更されたグラフを形成します。

次に、変更されたグラフからマトリックスツリー定理を使用して、スパニングツリーの総数を計算します。

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

Answer 1

gをグラフとし、Eをエッジとし、g/eをeを契約した同じグラフとします。それで、

命題：eを含むgのスパニングツリーとg/eのスパニングツリーの間には、双方向があります。

この命題は証明するのが難しくありません。他の人にそれが真実かどうかを尋ねるだけでなく、自分で証拠を理解する方が良いでしょう。明らかに、eを含むgのスパニングtツリーがある場合、t/eはg/eのスパニングツリーです。考えるべきことは、あなたも後ろに行くことができるということです。

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

Answer 2

それが正しいかどうかはわかりませんが、エッジの収縮が平行したエッジにつながる可能性があるという事実に注意する必要があります。平行エッジが使用されることによってのみ異なる木が明確であるとカウントされることを確認する必要があります。