java - ノードを照合するためのグラフ化アルゴリズム

Question

有向グラフが与えられた場合、すべてのノードが正確に1つの入力エッジと正確に1つの出力エッジを持つように、エッジのランダムなサブセットを見つけるために使用できるアルゴリズムは何ですか？

たとえば、これは私が与えられたグラフである可能性があります：

そして、これは有効な出力グラフになります。

これは次の理由で有効です。

• 入力グラフ上のすべてのノードが含まれています
• そのすべてのエッジも入力グラフ上にあります
• すべてのノードには、ノードを離れるエッジとそこに来るエッジが1つだけあります（同じエッジにすることはできません。ループは許可されません。すべてのノードは、少なくとも1つの他のノードに接続する必要があります）。

検出すべき解決策がない場合。

これを解決するための効率的なアルゴリズムはありますか？

ありがとう！

Answer 1

これは、ノードサイクルのカバレッジの問題です。これは、2部グラフの最大マッチングとして解くことができます。

要するに：

1. すべてのノードを2つに分割し、それぞれをグラフの1つのパーティションに分割して、すべてのエッジがパーティションP1からパーティションP2に移動するようにします。サンプルでは、​​ノードAとDは、パーティションP1ではノードA1、D1になり、P2ではA2、D2になります。エッジADはA1-D2に変わり、DA-はD1-A2に変わります。
2. 次に、最大の一致を見つけます。いくつかのアルゴリズムが存在します。
3. 次に、ノードをマージして戻すと、サイクルカバレッジが得られます。

Answer 2

グラフを一連のサイクルに分解しようとしています。

このリンクは、グラフ内のサイクルを見つけるためのTarjanのアルゴリズムを示しています。

その後、いくつかの検索戦略が必要になります（サイクルのいくつかの選択は、制約を考慮して解決策につながらない場合があります）。