次のように概念化できた問題があります。
n人のセットがあります。そして、白人、ヒスパニック系、アジア系などの民族性を表すm 個のサブセット。これらの人々の任意の組み合わせが与えられた場合、それが多様なグループであるかどうかを確認したいと思います。
多様なグループは、いくつかの要件を満たすグループであり、各要件は「グループ内の少なくともKi人がサブセットSiに属する」という形式です。ここがトリッキーな部分です。1 人の人間は 1 つの要件を満たすためにしか使用できません。のように、複数の要件に彼/彼女を使用することはできません。
例：
与えられた:
ヒスパニックから少なくとも 2 人 = {a,b,c}
アジア人={a,d,e}から少なくとも2人
グループ {a,c,d} は多様なグループですか?
グループ {a,c,d} は、 aをヒスパニック系とアジア系として数えることができないため、多様ではありません。しかし、グループ {a,c,d,e,f} は、2 人のヒスパニック a と c と 2 人のアジア人 d と e を持っているため、多様です。
試み：
これは代入問題の例です。職種は民族性であり、要件に応じていくつでも民族性を指定できます。たとえば、ヒスパニック系が 2 人必要な場合は、ヒスパニック系の仕事を 2 つ配置します。しかし、特定の仕事ができる人はごく一部です。
これはこれまでの私の試みです：
人の集合Pと民族の集合Sを使って 2 部グラフを作成します。人p_iと民族S_iが民族に属している場合、その民族との間にエッジを置きます。ここで、民族性 S_i ごとに k_i 回複製する ( S_{i,1}, S_{i,2}, ... , S_{i,k_i} ) ため、グラフを変更します。それに応じて新しいエッジを追加します。このグラフの最大一致 M を見つけます。
ここで、S_{i,j}を 1 つのS_iにマージすると、多様なグループができます。ただし、最大マッチングは、問題の可能な解決策にすぎません。そして、私の問題は決定問題です。特定のグループが解かどうかを確認したいと思います。