计算包含特定边集的生成树总数
我尝试了以下方法：
首先，我对给定边集中的所有边进行边收缩，以形成修改后的图。
然后，我使用矩阵树定理从修改后的图中计算生成树的总数。
我想知道这个方法是否正确，是否还有其他更好的方法。
I have tried the following approach:
First I do edge contraction for all the edges in the given set of edges to form a modified graph.
Then I calculate the total number of spanning trees, using the matrix tree theorem, from the modified graph.
I want to know if this method is correct and if there are some other better methods.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
设 G 为图，e 为边，G/e 为 e 收缩后的同一个图。那么，
命题： G 中包含 e 的生成树与 G/e 的生成树之间存在双射。
这个命题并不难证明；你最好自己去理解这个证明，而不是只问别人它是否正确。显然，如果你有一个 G 的生成 T 树，其中包含 e，那么 T/e 是 G/e 的生成树。需要考虑的是，你也可以倒退。
而且，正如 Adam 指出的那样，您必须小心正确处理具有平行边的图和具有从顶点到自身的边的图。
Let G be a graph, let e be an edge, and let G/e be the same graph with e contracted. Then,
Proposition: There is a bijection between the spanning trees of G that contain e, and the spanning trees of G/e.
This proposition is not hard to prove; you're better off understanding the proof yourself instead of just asking other people whether it's true. Obviously if you have a spanning T tree of G that contains e, then T/e is a spanning tree of G/e. The thing to think through is that you can also go backwards.
And, as Adam points out, you have to be careful to properly handle graphs with parallel edges and graphs with edges from a vertex to itself.
我不知道它是否正确，但你必须小心边缘收缩可能导致平行边缘的事实。您必须确保仅因使用的平行边而不同的树被视为不同的树。
I don't know if it's correct or not, but you'll have to be careful of the fact that edge contraction can lead to parallel edges. You'll have to make sure that trees differing only by which parallel edge is used are counted as being distinct.