給定必須包含的邊的最小生成樹數

Question

我對包含邊界e的最小生成樹的一般形式感到困惑，該邊緣不是最小生成樹的一部分。我的問題是：

讓ģ是加權曲線圖與所有的邊緣權重等於1 ģ的MST不包括邊緣ë。可以制定多少MST，限制條件是它們包括邊緣e？

Answer 1

當一個圖未加權時，任何生成樹都是Minimum Spanning Tree。的1

相同重量可被認爲是相同未加權。

在圖論中Kirchhoff's theorem或基爾霍夫矩陣樹定理古斯塔夫基爾霍夫的名字命名的數學領域是關於生成樹的圖形數定理。

數（MST包括E）=號（所有MST）< 1> - 數（MST無E）< 2>

< 1>可以通過基爾霍夫定理導出，並

在從圖中去除e之後可以由基爾霍夫定理導出。