Найти все полные подграфы в графе

Question

Есть ли известный алгоритм или метод, чтобы найти все полные подграфы в графе? У меня есть неориентированный невзвешенный граф, и мне нужно найти все подграфы в нем, где каждый узел в подграфе связан с каждым другим узлом в подграфе.

Существует ли алгоритм для этого?

Answer 1

Это известно как проблема клики ; это сложно и вообще в NP-полной комплектации, и да, для этого есть много алгоритмов.

Если граф обладает дополнительными свойствами (например, он является двудольным), то задача становится значительно проще и разрешима за полиномиальное время, но в остальном она очень сложна и полностью разрешима только для небольших графов.

Из Википедии

В информатике проблема клика относится к любой из проблем, связанных с поиском конкретных полных подграфов («клик») в графе, то есть наборов элементов, с которыми связана каждая пара элементов.

Клик проблемы включают в себя:

• нахождение максимальной клики (клика с наибольшим количеством вершин),
• поиск максимальной весовой клики на взвешенном графике,
• список всех максимальных кликов (кликов, которые нельзя увеличить)
• решение проблемы решения вопроса о том, содержит ли граф клику, превышающую заданный размер.

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

Смотри также

• Алгоритм Брон-Кербоша

Answer 2

Что ж, проблема поиска подграфа k-вершины в графе размера n имеет сложность

O (n ^ k k ^ 2)

Поскольку необходимо проверить n^k подграфов, каждый из которых имеет k^2 ребер.

То, что вы просите, найти все подграфы в графе, является NP-полной задачей и объясняется в алгоритме Брон-Кербоша, указанном выше.