1. 首頁
  2. 問答
  3. 有向圖的雙向最小生成樹

有向圖的雙向最小生成樹

2010-05-10 44 views
10

給定具有加權邊的有向圖，可以使用什麼算法給出具有最小權重的子圖，但允許從圖中任何頂點移動到任何其他頂點（在假設任何兩個頂點之間的路徑總是存在的情況下）。有向圖的雙向最小生成樹

這樣的算法是否存在？

來源

2010-05-10 Mantas Vidutis

回答

2

這看起來是NP-Hard：跨越子圖問題的最小權重強連接。我相信哈密爾頓循環問題可以歸結爲：給定一個圖G（V，E），構造一個有權邊1的邊DG的邊DG的權重爲1的有向圖DG（| V | +1） 「T。 DG具有與權重子圖完全相關的最小權重強關聯| V |當且僅當G有一個哈密爾頓循環。這裏

紙張上有一個近似算法：http://portal.acm.org/citation.cfm?id=844363

來源

2010-05-19 14:57:31

3

即使他們不是他們自己的權利，同時遵循維塔利的維基百科鏈接時間過得很快發現這個算法：

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm

來源

2010-05-10 07:32:20 Mathew

+0

愛德蒙的算法只保證在圖中每個節點將是從根訪問，不是每個節點都將是所有其他節點進行訪問。 – 2010-05-11 07:51:21

+0

這是NP-Hard。 -1。 – 2010-05-19 16:20:24

+0

我的鏈接的NP分類與它與原始問題的相關性有什麼關係？ – Mathew 2010-05-19 20:27:52

2

拆分每個節點在圖中爲兩個節點。一個節點將接受所有到達原始節點的傳入邊，另一個節點將具有所有傳出邊。然後，在所有邊上放下方向，這樣圖形就是無向的。然後你可以在圖上運行一個標準的MST算法（Prim's，Kruskal's），你將確保每個原始節點都可以被其他原始節點所傳播。

來源

2010-05-11 08:20:34 gmoomau

+0

不幸的是，這不會起作用，因爲它會在最終的圖表中添加不必要的邊緣。至少有一個節點會附加一個額外的邊緣，即使它不需要邊緣。例如，在具有頂點A，B，C和邊AB，BA，BC，CB，AC，CA的圖中，圖的最小跨度可以僅僅是邊AB，BC，CA。但是使用你的方法，這3條邊不會相互連接，並且需要添加額外的邊來完成MST。 – 2010-05-11 22:16:51

0

選擇任一節點，並將其返回。

難道你或許意味着找到（除去可能的節點的數量最少）的最大的強連接子，或最小權重跨度子（不允許節點清除）？

來源

2010-05-19 19:37:55

+0

標題說'生成樹'，所以我認爲後者。 – 2010-05-19 19:46:28

+0

@Moron：啊，我錯過了:)在這種情況下，你的回答是正確的。 – 2010-05-19 19:54:30

相關問題

 相關問題