Кліка (теорія графів)

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

Граф з 23 1-вершинними кліками (просто його вершинами), 42 2-вершинними кліками (просто його ребрами), 19 3-вершинними кліками (голубими трикутниками), і 2 4-вершинними кліками (темно-голубі). Шість ребер і 11 трикутників утворюють максимальні кліки. Два темно-голубих 4-вершинних кліки є максимальними і максимумами, і клікове число графа дорівнює 4.

Визначення

Кліка в неорієнтованому графі G = (V, E) це підмножина вершин C ⊆ V така, що для кожних двох вершин в C, існує ребро, що поєднує ці вершини. Це тотожно до виразу, що підграф утворений C — повний (в деяких випадках, термін кліка може бути використаний для підграфа).

Максимальна кліка (англ. maximal clique) — кліка, яка не може бути розширена через додання однієї з суміжних вершин, тобто така, що не є частиною більшої кліки.

Найбільша кліка, або максимум клік (англ. maximum clique), — кліка найбільшого можливого розміру в даному графі. Клікове число ω(G) графа G — кількість вершин в максимумі клік в G.

Протилежністю до кліки є незалежна множина, в сенсі, що кожна кліка відповідає незалежній множині в доповненні графа. Задача покриття графа кліками спрямована на знаходження найменшої кількості клік, які включають кожну вершину графа. Пов'язана концепція це бікліка, повний двочастковий підграф. Двочасткова розмірність графа це найменша кількість біклік необхідних, щоб покрити всі ребра графа.

Див. також

• Клікова ширина
• Кограф

Посилання

• Weisstein, Eric W. Кліка(англ.) на сайті Wolfram MathWorld.
• Weisstein, Eric W. Клікове число(англ.) на сайті Wolfram MathWorld.