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

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