WikiSort.ru - Не сортированное

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

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

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

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

Примечания

Литература

• 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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.