有向图的双向最小生成树

Question

给定带有加权边的有向图,可以使用什么算法给出具有最小权重的子图,但允许从图中的任何顶点移动到任何其他顶点(假设任何两个顶点之间的路径始终存在) .

这样的算法存在吗？

Answer 1

这看起来是 NP-Hard：最小权重强连通跨越子图问题。

我相信哈密顿循环问题可以简化为：给定一个图 G(V,E)，构造一个有向图 DG，对于出现的边，权重为 1，对于不出现的边，权重为 100 (|V|+1)。DG 有一个最小权重强连通跨越子图，其权重恰好为 |V| 当且仅当 G 具有哈密顿循环。