algorithm - 断开有向图的最小边数以使其强连接

Question

考虑一个断开有向图的示例， 其中G={V,E}顶点V={a,b,c,d}和边是孤立的。E={(a->b),(a->c)}d

根据这里的答案：（对强连通图的最小补充），确保该图所需的最小边数为 3。

如何找到将这些边添加到哪里，即该图中边的起始和结束顶点？

Answer 1

这是一个令人惊讶的微妙问题。Eswaran 和 Tarjan（见下文）是第一个为其声明线性时间算法的人，但是 Raghavan 发现并纠正了一个错误（关于 Eswaran 和 Tarjan 的强连通性增强问题算法的注释）。链接的 PDF 文章包含对更正算法的完整处理。

@article{doi:10.1137/0205044,
author = {Kapali P. Eswaran and R. Endre Tarjan},
title = {Augmentation Problems},
journal = {SIAM Journal on Computing},
volume = {5},
number = {4},
pages = {653-665},
year = {1976},
doi = {10.1137/0205044},
URL = { 
        http://dx.doi.org/10.1137/0205044
},
eprint = { 
        http://dx.doi.org/10.1137/0205044
}
}