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

Question

我尝试了以下方法：

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

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

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

- amitkarmakar

---

应该没问题。正如Adam Crume指出的那样，您现在正在使用多重图。幸运的是，存在一个适用于多重图的矩阵树定理版本，需要稍微不同的拉普拉斯矩阵。 - Il-Bhima

谢谢。还有其他方法吗？ 我想到这个方法只是凭直觉。 - amitkarmakar

Answer 1

我不知道这是否正确，但你必须注意边缩减可能会导致平行边。你必须确保只有使用不同平行边的树被视为不同。

- Adam Crume

Answer 2

让 G 为一张图，e 为一条边，G/e 为将 e 合并后得到的相同图。则，

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

这个命题不难证明；最好自己理解证明过程，而不是只问别人它是否正确。显然，如果你有一棵包含 e 的 G 的生成树 T，则 T/e 是 G/e 的生成树。需要思考的是，你也可以反过来做。

此外，正如 Adam 指出的那样，你必须小心处理具有平行边和从一个顶点到其自身的边的图。

- Greg Kuperberg