algorithm - 非接続グラフでの最大二部一致

Question

グラフに複数のコンポーネントがある場合、最大の二部一致をどのように見つけますか? 各コンポーネントは 2 つの方法で色付けできます。最大一致ルーチンを実行するために、2 つのセット X と Y をどのように決定しますか?

Answer 1

グラフに複数の異なる連結成分がある場合、それらの各成分で最大の一致を見つけ、それらの結合を返すだけで、グラフで最大の一致を見つけることができます。

セット X と Y を決定する方法については、特定のグラフが 2 部グラフであるかどうかを検出し、2 部グラフである場合はノードにラベルを割り当ててこれら 2 つのグループを復元するための多くのアルゴリズムが存在します。これは、変更された DFS または BFS を使用してかなり簡単に行うことができます。したがって、問題のアルゴリズムは次のようになります。

1. グラフ全体で DFS を実行して、グラフを連結要素に分割します。
2. これらの各コンポーネントについて:
   1. それらのコンポーネントで DFS を実行して、グループ X および Y にあるノードを回復します。
   2. 最大二部マッチング アルゴリズムを使用して、そのコンポーネント内の最大マッチングを見つけます。
3. すべての結果を組み合わせて、全体的な答えを取得します。

お役に立てれば！

Answer 2

エッジの観点から一致を見ないでください。エッジのセットとして見てください。この観点から、サブ結果をどのように結合しても、後で問題がないことが明確になります。

1. グラフを連結成分に分離する

2. 選択したアルゴリズムを使用して、各グラフ コンポーネントの最大一致を見つけます。

3. 見つかった一致の結合は、グラフ全体の最大一致です。

Answer 3

非接続グラフについてはわかりませんが、私が持っているような完全なグラフがある場合、これは興味深いかもしれません: http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html . 修正された Floyd-Warshall アルゴリズムを使用して、最大一致を見つけます。これとハンガリーのアルゴリズムの違いについてはわかりません。