学級試験で問題が出題されました。ある図書館では、各メンバーが 4 冊の本をリクエストし、各本は 2 人のメンバーのみによってリクエストされました。この情報は、二部グラフ G = ( X + Y , E ) の形式で与えられます。
X : すべてのメンバーのセット Y : すべてのブックのセット エッジ E = エッジのセット (x,y) ここで、x はブック y に対して要求されたメンバーです。私たちは、司書が各メンバーに最大 2 冊の本を与えて、最大のメンバーが満足できるようにする方法を見つけなければなりません。
私は2つのアプローチを思い付きました：
- 2 つの新しい頂点 s(ソース) と t(デスティネーション) を導入します。s から X のすべてのメンバーに容量 2 でエッジを導入します。すべてのエッジ E は容量 1 を持ち、新しいエッジ Y から t は容量 1 を持ちます。ここで最大フロー アルゴリズムを適用して、最大の一致を見つけます。最大マッチングが必要なソリューションです。
- もう 1 つの方法は、同じエッジを導入することによって上記と同じアルゴリズムに従うことですが、各エッジの容量は 1 です。次に、最大一致を見つけます。このマッチングは、最大会員数に1冊の本をプレゼントします。一致した書籍を削除し、上記のアルゴリズムを再度適用します。一致した本と 2 冊の本を持っているメンバーを再度削除し、X と Y の間にエッジがなくなるまでアルゴリズムを適用します。達成されたソリューションは、必要なソリューションです。
アルゴリズムを超えましたが、どちらが正しいか、どれも正しくないかわかりません。他のアルゴリズムがある場合は、ここで提案してください。