多重最小生成树图

Question

我被困在一个条件。我想知道一个图可以有多个最小生成树的情况是什么？ 任何人都可以帮助我吗？

Answer 1

我回答的假设是你有一个边缘权重图，并想知道是否有任何其他MST存在。

您可以通过以下方法做到这一点：

1. 查找具有相同的重量MST其他一些边缘在MST不边缘。 例如，假设边（a，b）在MST中并且具有等于边（c，d）的权重。

2. 从图中删除边（a，b）并再次运行MST。

3. 重复上述步骤直至找不到其他此类边缘或MST具有相同的总重量。

记住一个图有不同的MST，至少两个边必须相等。