计算含特定的一组边的

Question

我曾尝试以下方法生成树的总数：

首先我做边缘收缩在给定的一组边的所有边，以形成一个修改的曲线图。

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

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

Answer 1

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

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

这个命题不难证明;你最好自己理解证明，而不是只问别人是否是真的。显然，如果你有一个包含e的G的跨越T树，那么T/e是一个G/e的生成树。要考虑的事情是你也可以倒退。

而且，正如Adam所指出的那样，您必须小心妥善处理具有平行边的图形和从顶点到其自身的边的图形。

Answer 2

我不知道它是否正确，但您必须注意边缘收缩可能会导致平行边缘的事实。您必须确保仅使用平行边缘的树木不同。