圖算法檢測偶數週期

我有一個無向圖。該圖中的一條邊是特殊的。我想查找包含第一條邊的偶數循環的所有其他邊。圖算法檢測偶數週期

我不需要列舉所有的週期，這本質上是NP我認爲。我只需要知道每個邊緣是否滿足上述條件。

一個蠻力搜索當然是有效的，但速度太慢了，我正在努力想出更好的東西。任何幫助讚賞。

2012-08-26 john

這裏沒有足夠的信息來提供你正在尋找的質量的答案。提前多久知道哪個邊緣特殊？你允許預處理數據嗎？您事先接觸了多少數據（例如，加載它），您是否可以修改預處理數據的方式？ – ninjagecko

此外，如果不能濫用預處理，您可能需要查看所有循環**，儘管我無法以這種或那種方式考慮該斷言的證明。 – ninjagecko

@ninjagecko該圖表示化學結構，即頂點是原子，邊是這些原子之間的化學鍵。用戶不斷編輯化學結構，並且該算法預計隨着用戶執行編輯而實時運行。儘管我們也保留了一些其他結構（例如我們始終知道邊是否是週期的一部分），但我們使用圖的簡單鄰接表結構。如果我理解你的話，預處理不是一種選擇，因爲圖形（和特殊邊緣）總是在變化。 – john

我想我們有一個答案（我必須相信我的同事的想法）。基本上他的想法是在偶數週期的空間內完成洪水填充算法。這是有效的，因爲如果您通過合併兩個較小的週期形成較大的偶數週期，那麼較小的週期必須均爲偶數或雙方都是奇數。類似地，合併奇數和偶數循環總是形成更大的奇數循環。

這是一個實際的選擇，只是因爲我可以想象由交替的偶數和奇數週期組成的病理情況。在這種情況下，我們永遠不會找到兩個相鄰的偶數週期，所以算法會很慢。但我相信這種情況不會出現在真實的化學中。至少在目前所知的化學中，30年前我們從未聽說過富勒烯。

來源

2012-08-30 08:47:43 john

-1

如果你的圖有一個小節點度，你可以考慮使用不同的圖形表示：

讓三個原子u,v,w和兩個化學鍵e=(u,v)和k=(v,w)。表示此類數據的典型方法是將u,v,w作爲節點存儲，e,k作爲圖的邊。

然而，一個可能代表e和k如在圖中的節點，具有像f=(e,k)邊緣其中f表示從u到w，f=(e,k)或f=(u,v,w)一個兩步驟鏈路。運行任何算法以查找這樣的圖上的週期將返回原始圖上的所有偶數週期。

當然，這隻有在原始圖形具有小節點度時纔是有效的。當用戶執行編輯時，您可以輕鬆編輯相應的替代表示。

來源

2013-03-14 23:53:38 michai

圖算法檢測偶數週期

回答

相關問題