algorithm - 给定必须包含的边的最小生成树计数

Question

我对包含不属于最小生成树一部分的边e的最小生成树的一般形式感到困惑。我的问题是：

令G为所有边权重等于 1 的加权图。G的 MST不包括边e。在包含边e的约束下，可以制作多少个 MST ？

Answer 1

当图未加权时，任何生成树都是最小生成树。

相同的权重 1可以认为与未加权相同。

在图论的数学领域中，以古斯塔夫·基尔霍夫命名的基尔霍夫定理或基尔霍夫矩阵树定理是关于图中生成树数量的定理。

数字（包括 e 的 MST）= 数字（所有 MST）<1> - 数字（不带 e 的 MST）<2>

<1> 可以由基尔霍夫定理导出，并且

<2> 可以从图中去掉e 后由基尔霍夫定理推导出来。