graph - 从强连通图中删除边

Question

这个问题有名字吗？

给定一个具有边权重的有向且强连接图，找到最小成本的边集，以便删除该边集会导致图不再是强连接的。

有人知道/有解决方案的想法吗？我正在考虑将此设置为网络流量问题，但我不确定如何进行。

Answer 1

最接近的主题名为“渗透问题”。您正在描述“渗透阈值”和“渗透图中的路径”的一个方面。关于它有一个完整的理论。现在你有一个谷歌的关键字。

有趣的是，您的搜索是由一些实用模型引起的，而不是图、路径和分形的理论。