匹配節點的圖形化算法

Question

給定一個有向圖，我可以使用什麼算法來找到它的邊的一個隨機子集，以便每個節點只有一個入口和一個出口邊？

例如，這可能是我給出的圖表：

，這將是一個有效的輸出曲線：

這是有效的，因爲：

• 它包含inp上的所有節點ut圖
• 它的所有邊也都在輸入圖上
• 每個節點都有一條邊離開它並且一條邊接近它（並且不能是相同邊，不允許循環，每個節點都有連接至少一個其他節點）。

如果沒有可能的解決方案應該被檢測到。

有沒有一種有效的算法來解決這個問題？

謝謝！

Answer 1

這是一個節點週期覆蓋問題。它可以解決爲Maximum matchings in bipartite graphs。

簡而言之：

1. 分爲二的每個節點，在每一個曲線圖中的一個分區，以使得所有的邊緣從分區P1到分區P2。在您的示例中，節點A和D將變成分區P1和A2中的節點A1，D1，以及P2中的D2。邊A-D將變爲A1-D2，而D-A - 變爲D1-A2。
2. 然後找到最大匹配，存在一些算法。
3. 然後將節點合併回來，並且獲得了週期覆蓋。

Answer 2

您試圖將圖分解爲一組循環。

This link指向Tarjan的算法，用於在圖中查找循環。然後，您需要一些搜索策略（根據您的限制，某些循環選擇可能不會導致解決方案）。