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

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

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

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

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

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

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

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

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