5

我尝试了以下方法:

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

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

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

4

2 回答 2

4

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

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

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

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

于 2010-07-04T16:02:17.977 回答
4

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

于 2010-07-03T20:14:09.573 回答