考虑一个断开的有向图 G={V,E}
的例子,顶点 V={a,b,c,d}
和边 E={(a->b),(a->c)}
其中顶点 d
是孤立的。
根据此处的答案:( Minimal addition to strongly connected graph ),确保此图结果所需的最小边数为 3。
如何找到将这些边添加到的位置,即此图中边的起始和结束顶点?
最佳答案
这是一个非常微妙的问题。 Eswaran 和 Tarjan(见下文)是第一个为它声明线性时间算法的人,但有一个错误,由 Raghavan 发现并纠正(A note on Eswaran And Tarjan's algorithm for the strong connectivity augmentation problem)。链接的 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
}
}
关于algorithm - 断开连接的有向图使其强连接的最小边数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43205606/