algorithm - 如何为最小生成树增加弹性？

Question

我有一个完整的、加权的、无向图。边权重是两个节点之间连接的成本，因此最小生成树是具有最低总成本的边的子集，使得图保持连接。

MST 必须始终连接，但不幸的是连接不是很可靠，所以我想为这个图/网络添加冗余。

是否可以计算边的子集，从而使总边成本最小化并且边连通性超过某个最小值？

我可以看到暴力破解是如何实现的，但我一直在寻找更实用的东西。我没能找到很多关于这个问题的信息，我想主要是因为我不具备搜索所需的词汇。

我目前的想法是:

• 计算 MST
• 虽然它仍然低于某个连通性
  • 找到最低于该连通性的节点
  • 激活权重最低的那个节点的边

我没有同时找到某个连通性下的所有节点的原因是因为激活边可能会给另一个边足够的连通性。

我很确定这不会产生 100% 可证明的最佳网络，因为使用这种方法，可能会过度连接节点(例如，您为一个节点激活 k 条边，然后另一个节点激活更多共享边，使得其中一些是多余的)。我希望这是有道理的。

如有任何提示，我们将不胜感激!

Answer 1

关于 edge connected graphs 的维基百科文章结束于，一个相关问题:找到 G 的最小 k 边连接生成子图(即:在 G 中选择尽可能少的边，您的选择是 k 边连接的)对于 k 是 NP-hard >= 2。然后他们引用了 1979 年的一篇论文来证明这一点。

因此，我建议采取贪婪的方法，小心翼翼地离开。