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

Question

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

たとえば、これは私が与えられたグラフです。

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

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

• 入力グラフ上のすべてのノードが含まれます
• すべてのエッジも入力グラフ上にあります
• すべてのノードには、そこから出るエッジとそこに来るエッジが 1 つだけあります (同じエッジであってはならず、ループは許可されず、すべてのノードは少なくとも 1 つの他のノードに接続する必要があります)。

検出できる解決策がない場合。

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

ありがとう！

Answer 1

これはノード サイクル カバレッジの問題です。それは次のように解決できます 二部グラフでの最大一致数.

要するに：

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

Answer 2

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

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

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