我尝试了以下方法:
首先,我对给定边集中的所有边进行边收缩,以形成修改后的图。
然后我使用矩阵树定理从修改后的图中计算生成树的总数。
我想知道这种方法是否正确,是否还有其他更好的方法。
我尝试了以下方法:
首先,我对给定边集中的所有边进行边收缩,以形成修改后的图。
然后我使用矩阵树定理从修改后的图中计算生成树的总数。
我想知道这种方法是否正确,是否还有其他更好的方法。
设 G 为图,设 e 为边,设 G/e 为同一个图,e 收缩。然后,
命题:G中包含e的生成树与G/e的生成树之间存在双射。
这个命题不难证明;您最好自己理解证明,而不是仅仅询问其他人是否正确。显然,如果你有一个包含 e 的 G 的生成 T 树,那么 T/e 是 G/e 的生成树。要考虑的事情是你也可以倒退。
而且,正如亚当指出的那样,您必须小心正确处理具有平行边的图和具有从顶点到自身的边的图。
我不知道它是否正确,但你必须小心边缘收缩会导致平行边缘的事实。您必须确保只有使用哪个平行边不同的树被视为不同的。