非バイパスマッチングアルゴリズム

Question

私は、多くの基準に応じて人々にマッチさせる特定のアルゴリズムを見つけようとしています。それらのすべてが同じセット内にあり、エッジは共通の頂点を持つことはできません。基本的にはデートのウェブサイトのように私が言ったように：唯一のセット、そうではないバイpartite。

研究にもかかわらず、私はこのアルゴリズムを見つけることができませんでしたが、ほとんどすべてが二者についてです、または共通の頂点を許可しています。私は特に完璧なマッチングを探しています（遅くなる可能性があります）。

アルゴリズムはFord Furkersonアルゴリズムに基づいていると思われますが（通常は二者間一致のためです）、まだそれをどのように適用するかはわかりません。あなたは手がかりを持っていますか？ありがとう

Answer 1

Blossom algorithmを使用して、非二部グラフで最大一致を見つけることができます（これは非常に複雑ですのでここでは説明しません）。

最大限のマッチングが完了したら、完全であるかどうかをチェックするのは非常に簡単です（グラフの頂点の数とサイズを比較するだけです）。