我尝试了以下方法:
首先，我对给定的一组边中的所有边进行边收缩，以形成修改后的图。
然后，使用矩阵树定理，从修改后的图中计算出生成树的总数。
我想知道此方法是否正确以及是否还有其他更好的方法。
最佳答案
令G为图，令e为边，令G/e为收缩e的同一图。然后，
命题:在包含e的G的生成树与G/e的生成树之间存在双射。
这个主张并不难证明。您最好自己理解证明，而不是仅仅问其他人是否正确。显然，如果您有一个包含e的G的生成树T，则T/e是G/e的生成树。需要考虑的事情是，您也可以倒退。
而且，正如亚当指出的那样，您必须小心地正确处理具有平行边的图和具有从顶点到自身的边的图。
关于algorithm - 计算包含特定边集的生成树总数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3172718/