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

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

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

Див. також

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.