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

1 байт добавлено ,  12 лет назад
Нет описания правки
Кликой ([[Клика (теория графов)|clique]]) в неориентированном [[Граф (математика)|графе]] называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер (size) клики - число вершин, содержащихся в ней. Задача разрешения выглядит так: существует ли в заданном графе ''G'' клика размера ''k''? Соответствующая ей оптимизационная задача формулируется следующим образом: в заданном графе ''G'' требуется найти клику максимального размера. Последняя и называется '''задачей о клике'''.
 
NP-полнота данной задачи следует из NP-полноты [[PадачаЗадача о независимом наборе|задачи о независимом наборе]]. Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие [[Независимый набор|независимого набора]] размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
Другое доказательство NP-полноты можно найти в книге "Алгоритмы: построение и анализ" (Т.Кормен, Ч.Лейзерсон, Р.Ривест)
18

правок