Задача про кліку

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Задача про кліку відноситься до класу NP-повних задач в області теорії графів. Вперше вона була сформульована у 1972 році Річардом Карпом.[1]

Граф з клікою розміру 3.

Клікою в неорієнтованому графі називається підмножина вершин, кожні дві з яких з'єднані ребром графа. Іншими словами, це повний підграф первісного графа. Розмір кліки визначається як число вершин в ній. Задача про кліку існує у двох варіантах: у задачі розпізнавання потрібно визначити, чи існує в заданому графі G кліка розміру k, тоді як в обчислювальному варіанті потрібно знайти в заданому графі G кліку максимального розміру або всі максимальні кліки (такі, що не можна збільшити).

Історія[ред.ред. код]

Хоча повні підграфи довгий час вивчалися в математиці[2], термін «кліка» і задача алгоритмічно оголошеного кліка обидва походять із соціальних наук, де повні підграфи використовувались як модель соціальних кліків, груп людей, які всі знають один одного. Термінологія «кліка» походить від Люса та Перрі (1949), та перший алгоритм рішення задачі про кліку винайшли Харарі та Росс (1957), для соціологічних досліджень.

Після роботи Харарі і Росса, багато інших авторів розробили алгоритми для розв'язання різних версій задачі про кліку. У 1970-х, дослідники почали вивчати ці алгоритми з точки зору найгіршого аналізу; див., наприклад, Тарьян та Трояновськи (1977), перші роботи про вирішення найгіршого максимального кліку. Крім того, у 1970-х роках, починаючи з роботи Кука (1971) і Карпа (1972), дослідники почали знаходити математичне обгрунтування для сприйманої складності кліку проблеми в теорії NP-повноти і пов'язаних незговірливих результатів. У 1990-ті роки, був написаний цикл робіт, починаючи з Фейга і співавт. (1991) і повідомив у той час пресі[3] про те, що неможливо вирішити цю задачу максимально точно та ефективно.

NP-Повнота[ред.ред. код]

NP-повнота задачі про кліку випливає з NP-повноти завдання про незалежну множину (вершин). Легко показати, що необхідною і достатньою умовою для існування кліки розміру k є наявність незалежної множини розміру не менше k в доповненні графа. Це очевидно, оскільки повнота підграфа означає, що його доповнення не містить жодного ребра.

Інший доказ NP-повноти можна знайти в книзі «Алгоритми: побудова й аналіз».[4]

Алгоритми[ред.ред. код]

Як і для інших NP-повних задач, ефективного алгоритму для пошуку кліки заданого розміру на даний момент не знайдено. Повний перебір всіх можливих підграфів розміру k з перевіркою того, чи є хоча б один з них повним,- неефективний, оскільки повне число таких підграфів в графі з v вершинами збігається біноміальним коефіцієнтом {v \choose k} = \frac{v!}{k!(v-k)!}.

Інший алгоритм працює так: дві кліки розміру n і m «склеюються» у велику кліку розміру (n + m), причому клікою розміру 1 покладається окрема вершина графу. Алгоритм завершується, як тільки жодного злиття більше здійснити не можна. Час роботи даного алгоритму є лінійним, проте він є евристичним, оскільки не завжди призводить до знаходження кліки максимального розміру. Як приклад невдалого завершення можна навести випадок, коли вершини, що належать максимальній кліці, виявляються розділені й перебувають у кліках меншого розміру, причому останні вже не можуть бути «склеєними» між собою.

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Karp, Richard(1972). "Reducibility Among Combinatorial Problems". Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press.
  2. Complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of Ramsey theory by Erdős & Szekeres (1935).
  3. Kolata, Gina (June 26, 1990), «In a Frenzy, Math Enters Age of Electronic Mail», New York Times, http://www.nytimes.com/1990/06/26/science/in-a-frenzy-math-enters-age-of-electronic-mail.html .
  4. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

Література[ред.ред. код]