WikiSort.ru - Не сортированное

Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик.

Алгоритм

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

Алгоритм оперирует тремя множествами вершин графа:

1. Множество compsub — множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. Строится рекурсивно.
2. Множество candidates — множество вершин, которые могут увеличить compsub
3. Множество not — множество вершин, которые уже использовались для расширения compsub на предыдущих шагах алгоритма.

Алгоритм является рекурсивной процедурой, применяемой к этим трем множествам.

ПРОЦЕДУРА extend (candidates, not):
  ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates, 
  ВЫПОЛНЯТЬ:
  1 Выбираем вершину v из candidates и добавляем её в compsub
  2 Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v
  3 ЕСЛИ new_candidates и new_not пусты
  4 ТО compsub – клика
  5 ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not)
  6 Удаляем v из compsub и candidates, и помещаем в not

Вариации

Вычислительная сложность

Линейна относительно количества клик в графе. Tomita, Tanaka и Haruhisa в 2006 показали, что в худшем случае алгоритм работает за O(3^n/3), где n — количество вершин в графе.

См. также

Имеется викиучебник по теме
«Алгоритм Брона — Кербоша»

• Раскраска графа
• Перебор с возвратом
• Список алгоритмов

Литература

• Bron C., Kerbosh J. (1973), Algorithm 457 — Finding all cliques of an undirected graph, Comm. of ACM, 16, p. 575—577.
• Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi (2006), The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, Vol 363, Issue 1, ISSN:0304-3975, p. 28-42.