algorithm - 通过添加最小边制作二部图 SCC

Question

有一个二分图 B(E, V1, V2) 使得 e = (v1, v2) 对于 e ∈ E, v1 ∈ V1, v2 ∈ V2。 B 中的边是有向的。

我想制作一个图 G(E ∪ E', V2 ∪ V2) 使得图 G 是强连通分量，具有最小 sizeof(E')。 (sizeof(A) 是集合A中的元素个数)E' 不必是 V1 -> V2。

例如，对于 V1 = {1, 2, 3} 和 V2 = {a, b}，有一个二分图 B(E, V1, V2)，其中 E = {(1, a), (2 , a), (2, b), (3, b)}。然后 E' = {(a, 3), (a, 1), (b, 2)} 使 G(E ∪ E', V2 ∪ V2) 中的所有顶点都是强连通的。(每当我选择顶点对 v1 和v2，存在一条从v1到v2的路径)

有人可以给我一些想法吗？或者是否有关于此的知名算法？

Answer 1

Eswaran 和 Tarjan 的一个定理说，具有 r 个源(即没有传入边的顶点)和 s 个汇点(即没有传出边的顶点)的无环有向图可以通过添加 max(r, s) 条边来强连接(参见例如 here )。因此，您需要添加 max(sizeof(A), sizeof(B)) 边。这本书还解释了如何找到解决方案(一个简单的匹配顶点的系统)。