グラフ理論に関連する次の質問を考えてみましょう。
Gを2部グラフとします。問題をより具体的にするために、Gが2つの集合の非交和であると仮定します。たとえば、IとSを仮定します。
- 私は名前が1、2、3、4、5、6、7、8、9、10の個人を表します
- Sは、名前がa、b、c、d、e、f、g、hのスキルを表します。
したがって、各個人にはいくつかのスキルがあります。たとえば、
- 個人1はスキルb、d、g、hを持っています。
- 個人2には、スキルa、f、およびhがあります。
- 等
[この例では、データはランダムに与えられます]。
Sのすべてのスキルがチームに表されるように、つまりSのスキルごとに、そのスキルを持つチームのメンバーが存在するように、Iの最小数の個人で構成されるチームを構築することを目指しています。 s。
この問題には名前がありますか？それを解決するための効率的なアルゴリズムは知られていますか？