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

Question

我尝试了以下方法:

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

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

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

Answer 1

设G是一个图，设e是一条边，设G/e是e收缩的同一个图。然后，

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

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

并且，正如 Adam 指出的那样，您必须小心谨慎地正确处理具有平行边的图和具有从顶点到自身的边的图。