4

アルゴリズム設計の第1章を読みましたが、2部マッチングを独立集合問題に変換する方法について非常に短い説明がありましたが、わかりません。

このプロセスを説明する詳細なマトリエルを知っている人はいますか？ありがとう！

4

1 に答える 1

6

最大二部一致は、二部グラフ内のエッジのセットであり、隣接する 2 つのエッジはありません。最大独立集合は、グラフ内のノード (頂点) の集合であり、隣接する 2 つの頂点はありません。

したがって、2 部グラフのすべてのエッジをノードに変換することで、2 部マッチング問題を独立集合に変換し、元のグラフで共通のエンドポイントを共有する新しく作成されたすべてのノード間にエッジを追加できます。次に、新しいグラフの最大独立集合は、元の問題の最大二部マッチングに対応します。

于 2012-03-29T05:20:28.883 に答える