圖中的禁止路徑

我們提供了有向圖（數據流圖）。我們希望禁止數據到達圖的某些節點，這意味着我們將禁止刪除路徑，但必須保持圖形連接。圖中的禁止路徑

我提出了一個簡單的例子來使問題清晰：

讓我們如下圖：

一個------>乙--------> C- -------> D

我想禁止數據到達節點C，所以邊緣BC將被刪除。同時，我希望數據達到D.因此，將創建一個來自B-D的新邊緣。

上面的任務是否有一個有效的算法？

謝謝。

來源

2017-02-23 StamDad

您可以只刪除所有不需要的節點，並且如果圖形斷開連接，請將數據源的邊緣添加到數據接收器？ –

不允許達到的每個節點X都具有輸入邊緣和輸出邊緣。在我們討論數據流圖時，僅在X之前的節點僅到達X之後的其中一個j節點是不夠的。您可以插入一個虛擬（Steiner）節點X'，該虛擬節點X'除沒有標記外沒有任何功能X您發送所有i邊緣並連接j個輸出邊緣。否則，您可能必須連接其中一個傳入邊緣發起的每個節點，並將其連接到X引出邊緣的所有j個節點。（否則數據流被破壞）。

修復一對一節點是一個常量時間操作，但修復一個這樣的節點X的所有關係需要O（i * j）時間，即它是二次的入射邊緣的數量。

從，b和c的數據流至X，並從那裏向任一的x，y或z。

因此，從數據可以到達的x，y和z。

要從A-> X，我們必須從增加邊緣是從十到達的所有節點因爲我們要爲到達每邊做X，我們得到一個二次邊緣複雜。

編輯:(由於評論）對於兩個禁止節點X和Y有一個邊緣形式X到Y，這樣的邊緣可以留下來。在去除了所有禁止節點的邊界（禁止節點除外）之後，被禁止的節點可能形成大小大於1的連通分量。這不是問題，因爲每個這樣的連通分量僅包含禁止的節點和邊界，並且不能從剩下的流程圖。

在此之後，我們只刪除從有效節點到禁止節點的邊緣。這些邊緣必須被移除才能滿足需求。沒有其他邊緣被移除，因此這是滿足請求的最小量。（我認爲這裏沒有什麼需要證明的。）

來源

2017-02-24 07:31:52 gue

謝謝gue 所以基本上，算法如下： 1-搜索源和節點X之間的所有路徑。 2-保存X的鄰居是一個集合A 3-保存路徑中的節點，並將X作爲鄰居在集合B中。 4-從集合B和X的節點中刪除egdes 5 - 將集合B中節點的邊添加到集合A中的節點。如果它是正確的...這種算法的複雜性是什麼？ – StamDad

對於1，如果來源是指具有通向X的直接邊緣的節點，那麼是的。根據圖形的存儲方式，這應該是恆定的時間到達X的鄰居。所有通過X的路徑都必須經過一個以X結尾的節點，因此只需要這些節點。由於你的條件是不能達到X，所以只有在X處結束的邊緣必須被移除，從X邊緣離開X應該沒問題。在帖子中提到了複雜性，因爲對於i傳入和j傳出邊緣，複雜性需要每個這樣的節點X的O（i * j）時間。 – gue

再次感謝這個例子，我還有一個問題，如何證明通過使用這個方法我已經刪除了可能的最小邊緣？ – StamDad

圖中的禁止路徑

回答

相關問題