在有向圖中尋找邊緣不相交路徑的最大數量

Question

如何在有向圖中找到最大數量的邊緣不相交路徑。該圖未加權。 假設圖就像是跟隨...

1 - 2 , 1 - 3 , 4 - 1 , 5 - 1

所以沒有在圖中，兩個邊分離路徑，4->1->2和5->1->3

我如何解決使用匹配算法的問題？

我的問題是...假設我有一個有向圖（可能包含循環）。 如果我在一個節點上放置一個'警衛'，它就可以開始它的旅程。 即使是其他警衛已經去過的城市，警衛也可以多次訪問任何城市。 目標是找到保護所有節點的最小數量的警衛。

Answer 1

計數的所有路徑：

• 開始在圖中爲您提供邊緣的列表中的所有邊緣。
• 雖然仍然有可用邊緣，請繼續提取路徑並對它們進行計數。

提取的路徑：

• 刪除第一個（或任何）可用的邊緣，並呼籲它當前的路徑。
• 嘗試將當前路徑的開始或結束與可用邊的結束或開始匹配。
• 如果沒有可用邊匹配，則此路徑結束。
• 如果可用邊可以延長路徑，則將其添加到當前路徑中，從可用邊列表中刪除該邊並繼續嘗試延長路徑。