最小化有向图中的边集，保持连通组件

Question

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

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

首先，运行强连通分量算法。现在我们有了强连通分量。现在进入每个强连通分量，在该SCC内形成一个简单的循环；也就是说，只重复起始/结束节点的循环。这将最小化每个SCC内的边缘。

现在，我们需要最小化SCCs之间的边缘。不幸的是，我想不出一种方法来做到这一点。

我的两个问题是：(1) 在最小化SCCs之间的边缘部分之前，算法是否正确？(2) 如何最小化SCCs之间的边缘。

对于(2)，我知道这等价于最小化DAG中的边数。(将SCCs视为顶点)。但这似乎对我没有帮助。

- user678392

---

抱歉我的无知：您所说的“组件图”是什么意思？我不理解1和2之间的区别。 - dingalapadum

Answer 1

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

2. 似乎将跨组件边按连接的组件有序对分组，并仅留下每组中的一条边就足够了。

- Rafał Dowgird

---

在两个强连通分量之间，只能有一个方向的弧；因此，考虑无序对就足够了。 - Falk Hüffner

@FalkHüffner 没错，但实际上你需要对这些对进行排序，以便生成无序对的规范表示形式 :-) - Rafał Dowgird

@Rafał Dowgird 谢谢！但是我有几个问题：（1）什么是适当的循环，（2）我不明白你的第二个问题在说什么。您是否意味着在SCC图中连接的每对SCC之间仅保留一条边？这如何保持属性：G'具有与G相同的组件图。 - user678392

(1) 正确的循环是指没有顶点出现两次的循环。(2) 在组件图中，A和B之间的边存在，当且仅当在原始图中A和B中的任意两个顶点之间存在一条边。因此，只要组件之间存在至少一条原始边，组件图就会被保留。 - Rafał Dowgird

Answer 2

关于第 2 步，最小化强连通分量(SCC)之间的边，您可以随机选择一个顶点并运行深度优先搜索(DFS)，仅保留每对(root, end)的最长路径，同时删除其他路径。将所有搜索过的顶点存储在列表 L 中。

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

- Alan Yang