Задача о клике: различия между версиями

28 байт добавлено ,  12 лет назад
м
Нет описания правки
м
 
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]]
'''Кликой''' в неориентированном [[Граф (математика)|графе]] называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это ''полный подграф'' первоначального графа''. Размер клики определяется этокак число вершин, содержащихся в ней. Задача разрешения выглядит так: существует ли в заданном графе ''G'' клика размера ''k''? Соответствующая ей оптимизационная задача формулируется следующим образом: в заданном графе ''G'' требуется найти клику максимального размера. Это и есть '''задача о клике'''.
 
NP-полнота данной задачи следует из NP-полноты [[Задача о независимом наборемножестве|задачи о независимом наборемножестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого наборамножестве размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
Другое доказательство NP-полноты можно найти в книге "Алгоритмы: построение и анализ" (Т.Кормен, Ч.Лейзерсон, Р.Ривест)