graph - ノード数が等しいエッジの 2 分割

Question

標準的な 2 部分割の問題を解決しようとしています。つまり、出力グラフが 2 部グラフになるようなエッジのサブセットを見つけようとしています。私の追加の制約は次のとおりです。

1. 両側の頂点の数は等しくなければなりません。
2. 各頂点にはちょうど 1 つのエッジがあります。

実際、そのようなサブセットが存在するかどうかを知るだけで十分です。構築自体は本当に必要ありません。O(400) ノードに対して繰り返し実行する必要があるため、最適なアルゴリズムは高速である必要があります。

Answer 1

各頂点がちょうど 1 つのエッジに入射する場合は、マッチングが必要なようです。もしそうなら、Edmonds のブロッサム アルゴリズムがその役目を果たします。推奨するアルゴリズムの実装は使用していません。http://www.algorithmic-solutions.com/leda/ledak/index.htmをご覧ください。