<<
>>

Задача

Напомним, что вершинным покрытием в графе G = (V, E) называется такое множе- ство S ίΞ V, что по крайней мере один конец каждого ребра принадлежит S. В вер- сии задачи, которая рассматривается здесь, каждой вершине i V назначается вес w. > 0, а вес множества вершин S обозначается w(S) = ∑»*· Требуется найти вершинное покрытие S, для которого значение w(S) минимально. В стандартной версии задачи о вершинном покрытии все веса равны 1, и требуется принять ре- шение о том, существует ли вершинное покрытие с весом не более к.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи