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) 边来实现强连接（参见例如在这里）。因此，您需要添加 max(sizeof(A), sizeof(B)) 边。这本书还解释了如何找到解决方案（一个简单的顶点匹配系统）。