Задача о кликовом покрытии

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Задача о кликовом покрытии — вычислительная задача, заключающаяся в определении возможности разбить вершины графа на клик. Является NP-полной; входит в список из 21 NP-полных задач Карпа[1].

Если дано разбиение вершин на множеств, то можно за полиномиальное время определить, что каждое множество образует клику так, что задача принадлежит классу NP. NP-полнота задачи о кликовом покрытии следует из сведения её к задаче раскраски графа: разложение графа на клик соответствует нахождению разложения вершин дополнения на независимых множеств (каждому из этих множеств можно назначить один цвет, что даст -раскраску).

Минимальный размер кликового покрытия графа — наименьшее число , для которого кликовое покрытие существует.

Связанная задача нахождения числа пересечения рассматривает множества клик, включающих все рёбра заданного графа; эта задача также NP-полна.

Примечания

[править | править код]
  1. Карп, 1975, с. 16—38.

Литература

[править | править код]
  • Richard Karp. Proceedings of a Symposium on the Complexity of Computer Computations / R. E. Miller, J. W. Thatcher. — Plenum Press, 1972. — С. 85—103.
    • P. M. Карп. Кибернетический сборник (новая серия) / О. Б. Лупанов. — М.: «Мир», 1975. — С. 16—38.
  • Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5. A1.2: GT19, стр. 194.
    • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М., 1982.