從強連接圖中刪除邊緣

Question

此問題是否有名稱？

給定一個帶有邊權的有向連通圖。

Find a smallest cost set of edges such that removing that set of edges results in a 
graph that isn't strongly connected anymore. 

任何人都知道/有解決方案的想法？我想這是網絡流量問題，但我不知道如何繼續。

謝謝

Answer 1

最接近的一個按主題命名爲「滲流問題」。您正在描述「滲流閾值」和「滲透圖中的路徑」的一個方面。關於它有一個完整的理論。現在你有一個關鍵字谷歌。

有趣的是，您的搜索是由一些實際的模型引起的，而不是圖形，路徑和分形的理論。