Есть ли известный алгоритм или метод для нахождения всех полных подграфов в графе? У меня есть неориентированный, невзвешенный график, и мне нужно найти все подграфы внутри него, где каждый node в подграфе связан между собой node в подграфе.
Существует ли для этого существующий алгоритм?
Это называется проблемой clique; это сложно и в NP-полной вообще, и да, есть много алгоритмов для этого.
Если граф имеет дополнительные свойства (например, он двудольный), то проблема становится значительно проще и разрешима в полиномиальное время, но в противном случае она очень сложна и полностью разрешима только для малых графов.
В информатике проблема клики относится к любой из проблем, связанных с поиском конкретных полных подграфов ( "клик" ) в графе, т.е. множеств элементов, в которых каждая пара элементов связана.
Проблемы с кликой включают:
- нахождение максимальной клики (клика с наибольшим числом вершин),
- найти максимальную клику веса в взвешенном графе,
- перечисление всех максимальных клик (клики, которые не могут быть увеличены)
- решение проблемы решения проверки того, содержит ли граф клику, превышающую заданный размер.
Все эти проблемы сложны: проблема решения клики NP-полная (одна из проблем NPP полной сложности Karp 21), проблема нахождения максимальной клики является фиксированным параметром, трудноразрешимым и трудно аппроксимируемым, и перечисление всех максимальных кликам может потребоваться экспоненциальное время, так как существуют графики с экспоненциально многими максимальными кликами. Тем не менее, существуют алгоритмы для этих проблем, которые выполняются в экспоненциальном времени или которые обрабатывают некоторые более специализированные входные графики в полиномиальное время.