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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

См. также

Литература

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