Задача о вершинном покрытии

Материал из WEGA

Задача о вершинном покрытии (Vertex covering problem) — одна из основных [math]\displaystyle{ \mathcal NP }[/math]-полных задач. Формулируется следующим образом.

У с л о в и е. Дан неориентированный граф [math]\displaystyle{ G=(V,E) }[/math] и положительное целое число [math]\displaystyle{ k }[/math],[math]\displaystyle{ k\leq\mid V\mid }[/math].

В о п р о с. Имеется ли [math]\displaystyle{ k }[/math]-вершинное покрытие в [math]\displaystyle{ G }[/math], т.е. существует ли такое [math]\displaystyle{ V'\subseteq V }[/math], что [math]\displaystyle{ \mid V'\mid =k }[/math] и для каждого ребра [math]\displaystyle{ \{ u,v\} }[/math] графа хотя бы одна из вершин [math]\displaystyle{ u }[/math] или [math]\displaystyle{ v }[/math] принадлежит [math]\displaystyle{ V^\prime }[/math]?

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.