算法在大圖中找到神經點2

假設我有一個大的連接頂點的任意圖形，如下所示。假設這些是網絡連接。一些連接（紅色）更有助於損害其他人。如果兩個紅色連接失敗，許多點與其餘島嶼的成員沒有更多的聯繫。算法在大圖中找到神經點2

怎樣才能找到這些神經連接？

是否有一個現有的算法呢？

graph sample

來源

2012-07-25 RED SOFT ADAIR

也許適應最小切割算法？ – 2012-07-25 16:16:42

你能提供任何鏈接嗎？ – 2012-07-25 16:18:08

這是一篇維基百科文章：http：//en.wikipedia.org/wiki/Min_cut。這個想法是均勻稱重邊緣，看起來你的紅色邊緣將是最小切割。 – 2012-07-25 16:20:05

剛剛送走我的頭頂，我會說，你需要看流網絡：http://en.wikipedia.org/wiki/Flow_network。

來源

2012-07-25 16:18:43

我非常瞭解這一頁 - 謝謝 – 2012-07-25 16:19:47

您想知道Edge Connectivity。在你的情況下，你似乎只關心圖形是2邊連接的，這種情況下可能有特定的算法，但我不確定。下面是一個簡單的算法，我認爲應該工作：

For all edges, E, in your graph, G: 
    Remove E from G. 
    Find any path, P, from src(E) to dst(E). 
    Remove all edges in P from G. 
    Find a path from src(E) to dst(E), 
    if none exists then E is one of your important edges.

這並不快，但是，它需要O（E *（E + V）），如果你的圖是平面的，那麼這是不是太糟糕，因爲O（E）== O（V），所以需要時間O（V^2）。如果你的圖形連接得多，那麼這可能與O（V^4）一樣糟糕，這可能是令人望而卻步的。

來源

2012-07-25 18:45:11

算法在大圖中找到神經點2

回答

相關問題