algorithm - 含める必要のあるエッジが与えられた場合の最小スパニングツリー数

Question

最小全域木の一部ではないエッジeを含む最小全域木の一般的な形式について混乱しています。私の質問は：

Gを、すべてのエッジの重みが1に等しい重み付きグラフとします。GのMSTには、エッジeは含まれません。エッジeを含むという制約でMSTをいくつ作成できますか？

Answer 1

グラフが重み付けされていない場合、スパニングツリーは最小スパニングツリーになります。

同一の重み1は、重みなしと同じと見なすことができます。

グラフ理論の数学分野では、キルヒホッフの定理またはグスタフ・キルヒホフにちなんで名付けられたキルヒホッフの行列ツリー定理は、グラフ内のスパンツリーの数に関する定理です。

数値（eを含むMST）=数値（すべてのMST）<1>-数値（eを含まないMST）<2>

<1>は、キルヒホッフの定理から導き出すことができます。

<2>は、グラフからeを削除した後、キルヒホッフの定理から導き出すことができます。