algorithm - 计算包含特定边集的生成树的总数

Question

我尝试了以下方法：

首先，我对给定边集中的所有边进行边收缩，以形成修改后的图。

然后我使用矩阵树定理从修改后的图中计算生成树的总数。

我想知道这种方法是否正确，是否还有其他更好的方法。

Answer 1

设 G 为图，设 e 为边，设 G/e 为同一个图，e 收缩。然后，

命题：G中包含e的生成树与G/e的生成树之间存在双射。

这个命题不难证明；您最好自己理解证明，而不是仅仅询问其他人是否正确。显然，如果你有一个包含 e 的 G 的生成 T 树，那么 T/e 是 G/e 的生成树。要考虑的事情是你也可以倒退。

而且，正如亚当指出的那样，您必须小心正确处理具有平行边的图和具有从顶点到自身的边的图。

Answer 2

我不知道它是否正确，但你必须小心边缘收缩会导致平行边缘的事实。您必须确保只有使用哪个平行边不同的树被视为不同的。