给定必须包含的边的最小生成树计数
我对最小生成树的一般形式感到困惑，其中包含不属于最小生成树的边e。我的问题是：
设G为一个加权图，所有边的权重都等于1。G的MST不包括边e 。在包含边 e 的约束下，可以创建多少个 MST？
I am confused about the general form of a minimum spanning tree that includes an edge e that is not part of the minimum spanning tree. My question is:
Let G be a weighted graph with all the edges weight equal to 1. The MST of G does not include an edge e. How many MSTs can be made with the constraint that they include edge e ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
相同的权重1可以被认为与未加权相同。
数量(MST，包括e)＝数量(所有MST) 1 ； -数量(没有e的MST) 2 ；
<1>可以通过基尔霍夫定理导出，并且
<2>从图中删除 e 后，可以通过基尔霍夫定理导出。
Identical weight of 1 can be considered the same as unweighted.
Number (MST including e) = Number (All MST)<1> - Number (MST without e)<2>
<1> can be derived by Kirchhoff's theorem, and
<2> can be derived by Kirchhoff's theorem after removing e from the graph.