BGL - 確定所有縮略圖

給定一個圖，我想查找所有邊（如果有的話），如果移除將圖分散爲兩個組件。BGL - 確定所有縮略圖

最初的想法是將1的權重指定給所有邊，然後計算圖的最小切割。 mincut> 1意味着沒有單個邊緣，當被移除時導致分裂。

對於mincut == 1，如果該算法會爲每個最小切割提供它所包含的邊，那將會很不錯。

不幸的是，BGL似乎並不支持這樣的事：

的stoer_wagner_min_cut功能決定完全最小切口之一，也是它的重量。

（http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/stoer_wagner_min_cut.html）

有沒有一種方法，使這項工作與BGL（即確定超過一個mincut更多）或我將不得不拿出不同的東西？

來源

2015-10-15 User1291

所以你要找到所有切割中只有一個邊緣？我希望boost支持連通性檢查，所以如果只刪除那條邊，你應該能夠檢查每條邊是否保持連接。或者，[Tarjan的算法找到橋樑]（https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Tarjan.27s_Bridge-finding_algorithm）會更快;也許檢查是否在boost中實現，或者你可以自己實現它，它的描述看起來並不複雜。 –

不檢查每個邊緣的連接性是否有大量開銷？感謝tarjan。然而，如果我後來想要修改算法以檢查缺少橋接的算法，那麼對於刪除將分割圖的邊（e0，e1）對呢？無法很好地運行每個邊緣一次的tarjan，我可以嗎？ – User1291

在這種情況下，您想要[k-connectivity]（https://en.wikipedia.org/wiki/K-edge-connected_graph#Computational_aspects），這通常是使用流程網絡解決的，但我不確定如何有效檢查所有k個邊的刪除，刪除將會斷開圖形。也許對於[biconnectivity]（https://en.wikipedia.org/wiki/Biconnected_component）有一些東西，但你必須仔細研究。 –

這可能會有點晚了......

從我看到你只需要找到一個不屬於任何週期圖中的所有邊（假設圖已連接）。

這可以通過迭代去除葉節點（以及連接到它們的邊）來完成，就像你在topological sorting中做的一樣，直到沒有葉節點離開，即剩餘圖中的每條邊都屬於至少一個週期。在這個過程中刪除的所有邊緣將是你想要的。

僞代碼，對於無向連通圖G=(V,E)，你可以這樣做：

S = Ø 
while(there exists a node n∈V s.t. degree(n)==1) 
    e = edge connected to n 
    S = S∪{e} 
    E = E-{e} 
    V = V-{n} 
return S

它可以在O完成（| V | + | E |）時間

來源

2016-09-11 13:36:33 MasterYoda

BGL - 確定所有縮略圖

回答

相關問題