algorithm - 最小化有向图中的边集，保持连通分量

Question

这是完整的问题：

假设我们有一个有向图 G = (V,E)，我们想找到一个图 G' = (V,E')，它具有以下属性：

1. G' 具有与 G 相同的连通分量
2. G' 与 G 具有相同的分量图
3. E' 被最小化。也就是说，E' 尽可能小。

这是我得到的：

首先，运行强连通分量算法。现在我们有了强连接的组件。现在转到每个强连接组件，并在该 SCC 内做一个简单的循环；也就是说，唯一重复的节点是开始/结束节点的循环。这将最小化每个 SCC内的边缘。

现在，我们需要最小化SCC之间的边缘。唉，我想不出这样做的方法。

我的两个问题是：（1）关于最小化SCC之间边缘的部分之前的算法听起来正确吗？(2) 如何最小化 SCC 之间的边缘。

对于 (2)，我知道这相当于最小化 DAG 中的边数。（将 SCC 视为顶点）。但这似乎对我没有帮助。

Answer 1

1. 该算法似乎是正确的，只要您允许封闭游走（即重复顶点）。可能不存在适当的循环（例如在“8”形组件中）并且找到它们是NP-hard。

2. 似乎通过它们连接的有序组件对对组件间边进行分组并在每组中只留下一条边就足够了。

Answer 2

关于步骤 2，最小化 SCC 之间的边，您可以随机选择一个顶点，并运行 DFS，只保留每对 (root, end) 的最长路径，同时删除其他路径。将搜索到的所有顶点存储在列表 L 中。

选择另一个顶点，如果存在于L中，则跳到下一个顶点；如果没有，请重复上述过程。