グラフの完全でない二者間マッチングを見つけるにはどうすればよいですか？

Question

つまり、いくつかの頂点が他の頂点に接続されていない可能性があるグラフの2部のマッチングを見つけるにはどうすればよいですか？

EDIT：もう1つの条件は、エッジも加重されていると仮定し、合計エッジウェイトが最小化（または最大化）されるようなマッチングを希望します。

Answer 1

まず、体重が負ではないと仮定します。編集したバージョンで

、あなたはassignment problem話している：N剤にはされている各エージェントは、各アクションの任意の非負のコストを有する場合、それぞれが、独自のアクションを実行するために割り当てられました。この説明は完全な二者間マッチングのためのものですが、あなたはいくつかのトリックを実行することができます。側面のバランスをとるために、ウェイト0の頂点を反対側のすべてに追加して、アクションを取らない/取らないアクションに関連するコストを0にすることができます。不足しているリンクは、すべての真のコストの合計を超えるコストによってモデル化することができるため、問題が解決できない場合にのみ選択されます。編集したバージョンについては、Hungarian Algorithmを使用します。最後に、この問題は「最大重み付き二者間マッチング」とも呼ばれ、アルゴリズムの別の言及はmaximum matchings in bipartite graphsの下の2番目の段落にあります。

EDIT：コストを最小化するのではなく最大化したい場合は、費用を回避する必要があります。最大コストを見つけて、最大コストから各コストを引きます。リンクが見つからない場合は、コスト0のリンクを取ることは望ましくありません。

Answer 2

Hopcroft-Karp algorithmを使用してください。