完全な一致を持つように2部グラフを修正する

Question

等辺のXとYを持つ2部グラフを与えた場合、追加する必要のある最小限の辺の数を効率的に見つけることができますマッチング？ホールの定理が満たされるまですべての2 ^（| X |）サブセットを反復し、エッジを追加するよりも良い解決策がありますか？

ありがとうございました。

Answer 1

私が質問を正しく理解した場合、いわゆるHungarian methodを使用するか、ネットワークフローの問題としてモデル化することによって、効率的に初期グラフを一致させることができます。カーディナリティマキシマムマッチングが見つかったら、どちらのパーティションにも同数のマッチしないノードが存在しなければなりません。マッチするノードは自由に追加エッジを使用してマッチングできます。すなわち

Mは、元のグラフにおけるカーディナリティ、最大マッチングの基数であり、|X|=|Y|が保持している場合、次いで少なくともM-|X|でエッジがグラフに含まれている完全なマッチングを得るために添加しなければなりません。