Задать вопрос
Lite_stream
@Lite_stream

Есть ли у этой задачи название?

Дан двудольный граф, состоящий из L и R долей. Требуется выбрать минимальное количество вершин из R, так, чтобы для каждой вершины из L было хотя бы одно ребро, соединяющее её с какой-то выбранной вершиной из R.

Задача слегка напоминает минимальное вершинное покрытие, только тут можно выбирать вершины только из 1-й доли.
  • Вопрос задан
  • 178 просмотров
Подписаться 1 Простой Комментировать
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Если вам можно брать вершины только из одной доли, то это задача set cover (покрытие множества). Каждая вершина в R задает множество в L и вам надо взять минимальное их количество, чтобы все L было покрыто. Это NP-сложная задача и у нее есть только медленные решения, вроде перебора. Еще можно свести ее к задаче целочисленного линейного программирования и решать каким-нибудь солвером.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы