Электромонтаж Ремонт и отделка Укладка напольных покрытий, теплые полы Тепловодоснабжение

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

13.03.2022

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

Алгоритм

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

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

  • Множество compsub — множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. Строится рекурсивно.
  • Множество candidates — множество вершин, которые могут увеличить compsub
  • Множество 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

    Вариации

    Нахождение максимальных (по включению) независимых множеств вершин

    Нетрудно видеть, что задача о клике и задача о независимом множестве по сути эквивалентны: каждая из них получается из другой, путём построения дополнения графа — такого графа, в котором есть все вершины исходного графа, причем в дополнении графа вершины соединены ребром тогда и только тогда, если они не были соединены в исходном графе.

    Поэтому алгоритм Брона — Кербоша можно использовать для нахождения максимальных по включению независимых множеств вершин, если построить дополнение к исходному графу, либо изменив условие в основном цикле (условие остановки) и формирование новых множеств new_candidates и new_not:

  • Условие в основном цикле: not не должно содержать ни одной вершины, НЕ СОЕДИНЕННОЙ НИ С ОДНОЙ из вершин во множестве candidates
  • Для формирования new_candidates и new_not, необходимо удалять из candidates и not вершины, СОЕДИНЕННЫЕ с выбранной вершиной.
  • Вычислительная сложность

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


    Имя:*
    E-Mail:
    Комментарий: