Есть ли известный алгоритм или метод для поиска всех полных подграфов в графе? У меня есть неориентированный невзвешенный граф, и мне нужно найти все подграфы в нем, где каждый узел в подграфе связан с каждым другим узлом в подграфе.
Есть ли для этого существующий алгоритм?
Это известно как проблема клики; это сложно и в целом является NP-полным, и да, для этого существует множество алгоритмов.
Если у графа есть дополнительные свойства (например, он двудольный), тогда задача значительно упрощается и решается за полиномиальное время, но в остальном это очень сложно и полностью разрешимо только для небольших графов.
В информатике проблема клики относится к любой из проблем, связанных с поиском определенных полных подграфов (клик) в графе, то есть наборов элементов, в которых каждая пара элементов связана.
К проблемам клики относятся:
- нахождение максимальной клики (клика с наибольшим числом вершин),
- нахождение клики максимального веса во взвешенном графе,
- перечисление всех максимальных клик (клик, которые не могут быть увеличены)
- решение проблемы принятия решения о проверке наличия в графе клики, превышающей заданный размер.
Все эти проблемы сложны: проблема решения клики является NP-полной (одна из 21 NP-полных проблем Карпа), проблема поиска максимальной клики является одновременно труднопреодолимой с фиксированным параметром и трудной для аппроксимации, а перечисление всех максимальных клик может потребовать экспоненциальное время, поскольку существуют графы с экспоненциально большим числом максимальных клик. Тем не менее, есть алгоритмы для этих проблем, которые выполняются в экспоненциальном времени или которые обрабатывают определенные более специализированные входные графы за полиномиальное время.
Что ж, проблема поиска k-вершинного подграфа в графе размера n имеет сложность
O(n^k k^2)
Так как нужно проверить n^k подграфов, и каждый из них имеет k^2 ребра.
То, о чем вы просите, найти все подграфы в графе - это NP-полная проблема, которая объясняется в алгоритме Брон-Кербоша, указанном выше.
