Алгоритм двудольного графа

Question

Рассмотрим следующий вопрос относительно теории графов:

Пусть G двудольный граф.Чтобы сделать задачу более конкретной, предположим, что G - это несвязное объединение двух множеств, скажем, I и S. Предположим,

• I представляет лиц с именами 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,
• и т. Д.

[в данном примере данные даются случайным образом].

Мы стремимся создать команду, состоящую из минимум человек I таким образом, что каждый навык в S будет представлен в команде, то есть для каждого навыка s в S , существует член команды, обладающий навыком s .

У этой проблемы есть имя?Известен ли эффективный алгоритм его решения?

Answer 1

Похоже на задание проблемы покрытия
Группы элементов из l создают подмножество s

Answer 2

Ваша проблема - проблема минимального набора покрытия:

Купите Х предметов из М из N лотов, где М - минимальное количество лотов, необходимое для получения всех Х предметов.

В вашем примере навыки - это предметы, а студенты - много.

http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml

Проблема NP-трудна. Эффективный способ решения этой проблемы - использование алгоритма аппроксимации жадных множеств.