84
правки
Изменения
→Задача о количестве полных подграфов в графе
19 × 3-вершинными кликами (светло-синие и тёмно-синие треугольники) и
2 × 4-вершинными кликами (тёмно-синие зоны). Всего 86 клик.]]
Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество полных подграфов графа <tex>G</tex> (такие подграфы также называются '''кликами''' (англ. ''clique''))[[Основные_определения_теории_графов#Часто используемые графы | клик]].
Наивное решение — перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность — <tex>O(2^N \times N^2)</tex>
