algorithm - グラフの不完全な2部一致を見つけるにはどうすればよいですか？

Question

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

編集：もう1つの条件として、エッジにも重みが付けられていると仮定します。エッジの重みの合計が最小化（または最大化）されるようにマッチングしたいと思います。

Answer 1

Hopcroft-Karpアルゴリズムを使用すると、必要な処理を正確に実行できます。

Answer 2

まず、あなたの重みが負ではないと仮定します。

編集したバージョンでは、割り当ての問題について話します。n個のエージェントには、実行する一意のアクションがそれぞれ割り当てられます。各エージェントには、アクションごとに任意の非負のコストがあります。この説明は完全な2部マッチングを目的としていますが、いくつかのトリックを実行できます。側面のバランスをとるために、反対側のすべてに重み0の頂点を追加して、アクションを実行しない/アクションを実行しないことに関連するコストが0であると言うことができます。欠落しているリンクは、すべての実際のコストの合計を超えるコストでモデル化できるため、問題が解決できない場合にのみ選択されます。編集したバージョンでは、ハンガリーのアルゴリズムを使用します。最後に、この問題は「最大加重2部マッチング」とも呼ばれ、アルゴリズムへの別の参照は、2部グラフの最大マッチングの下の2番目の段落にあります。

編集：コストを最小化するのではなく最大化したい場合は、コストを反転させる必要があります。最大コストを見つけて、最大コストから各コストを差し引くだけです。次に、リンクが欠落している場合は、コスト0のリンクを使用する必要はありません。