Кліка (теорія графів) — Вікіпедія

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

Визначення[ред. | ред. код]

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

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

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

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

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

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

Посилання[ред. | ред. код]

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