В информатике алгоритм Брона–Кербоша — это алгоритм перечисления для поиска всех максимальных клик в неориентированном графе . То есть он перечисляет все подмножества вершин с двумя свойствами: каждая пара вершин в одном из перечисленных подмножеств соединена ребром, и ни одно перечисленное подмножество не может иметь никаких дополнительных вершин, добавленных к нему, сохраняя при этом его полную связность . Алгоритм Брона–Кербоша был разработан голландскими учеными Конрадом Броном и Йопом Кербошем, которые опубликовали его описание в 1973 году.
Хотя другие алгоритмы для решения проблемы клики имеют время выполнения, которое, в теории, лучше на входах, имеющих несколько максимальных независимых множеств, алгоритм Брона-Кербоша и его последующие усовершенствования часто сообщаются как более эффективные на практике, чем альтернативы. [1] Он хорошо известен и широко используется в прикладных областях графовых алгоритмов, таких как вычислительная химия . [2]
Современный алгоритм Аккоюнлу (1973), хотя и представленный в других терминах, можно рассматривать как тот же самый алгоритм, что и алгоритм Брона–Кербоша, поскольку он генерирует то же самое дерево поиска. [3]
Базовая форма алгоритма Брона–Кербоша — это рекурсивный алгоритм обратного отслеживания , который ищет все максимальные клики в заданном графе G. В более общем смысле, если заданы три непересекающихся множества вершин R , P и X , он находит максимальные клики, которые включают все вершины из R , некоторые вершины из P и ни одной вершины из X. При каждом вызове алгоритма P и X являются непересекающимися множествами, объединение которых состоит из тех вершин, которые образуют клики при добавлении к R. Другими словами, P ∪ X — это множество вершин, которые соединены с каждым элементом R. Когда P и X оба пусты, то больше нет элементов, которые можно добавить к R , поэтому R является максимальной кликой, и алгоритм выводит R.
Рекурсия инициируется установкой R и X в качестве пустого множества , а P в качестве множества вершин графа. В каждом рекурсивном вызове алгоритм по очереди рассматривает вершины в P ; если таких вершин нет, он либо сообщает R как максимальную клику (если X пусто), либо возвращается назад. Для каждой вершины v , выбранной из P , он делает рекурсивный вызов, в котором v добавляется к R и в котором P и X ограничиваются соседним множеством N(v) v , которое находит и сообщает все расширения клик R , содержащие v . Затем он перемещает v из P в X , чтобы исключить ее из рассмотрения в будущих кликах, и продолжает со следующей вершиной в P .
То есть в псевдокоде алгоритм выполняет следующие шаги:
алгоритм BronKerbosch1(R, P, X) — если P и X оба пусты , то R сообщается как максимальная клика для каждой вершины v в P do BronKerbosch1( R ⋃ { v }, P ⋂ N ( v ), X ⋂ N ( v )) P := P \ { v } X := X ⋃ { v }Базовая форма алгоритма, описанная выше, неэффективна в случае графов со многими немаксимальными кликами: она делает рекурсивный вызов для каждой клики, максимальной или нет. Чтобы сэкономить время и позволить алгоритму быстрее возвращаться в ветвях поиска, которые не содержат максимальных клик, Брон и Кербош представили вариант алгоритма, включающий «вершину опоры» u , выбранную из P (или, в более общем смысле, как поняли более поздние исследователи, [4] из P ⋃ X ). Затем соседи этого опорного элемента не проверяются рекурсивно. Любая максимальная клика, потенциально найденная при тестировании соседей u, также будет найдена при тестировании u или одного из ее не-соседей, поскольку по крайней мере один из них всегда будет частью этой максимальной клики. В противном случае только соседи u будут частью этой максимальной клики, что позволит расширить ее, добавив к ней u , что противоречит тому, что эта клика является максимальной. Следовательно, только u и его не-соседи должны быть проверены как варианты выбора для вершины v , которая добавляется к R в каждом рекурсивном вызове алгоритма. В псевдокоде:
алгоритм BronKerbosch2(R, P, X) — если P и X оба пусты , то R выводится как максимальная клика выбрать опорную вершину u в P ⋃ X для каждой вершины v в P \ N( u ) сделать BronKerbosch2( R ⋃ { v }, P ⋂ N( v ), X ⋂ N( v )) P := P \ { v } X := X ⋃ { v }Если опорная точка выбрана для минимизации количества рекурсивных вызовов, выполняемых алгоритмом, экономия времени выполнения по сравнению с версией алгоритма без опорной точки может быть значительной. [5]
Альтернативный метод улучшения базовой формы алгоритма Брона–Кербоша заключается в отказе от поворота на самом внешнем уровне рекурсии и вместо этого тщательном выборе порядка рекурсивных вызовов с целью минимизации размеров множеств P вершин-кандидатов в каждом рекурсивном вызове.
Вырожденность графа G — это наименьшее число d, такое что каждый подграф графа G имеет вершину со степенью d или меньше. Каждый граф имеет порядок вырожденности , порядок вершин такой, что каждая вершина имеет d или меньше соседей , которые идут позже в порядке; порядок вырожденности может быть найден за линейное время путем многократного выбора вершины минимальной степени среди оставшихся вершин. Если порядок вершин v , которые алгоритм Брона-Кербоша перебирает циклами, является порядком вырожденности, то множество P вершин-кандидатов в каждом вызове (соседи v , которые находятся позже в порядке) будет гарантированно иметь размер не более d . Множество X исключенных вершин будет состоять из всех более ранних соседей v и может быть намного больше d . В рекурсивных вызовах алгоритма ниже самого верхнего уровня рекурсии все еще может использоваться версия с поворотом. [6] [7]
В псевдокоде алгоритм выполняет следующие шаги:
алгоритм BronKerbosch3(G) - это P = V( G ) R = X = пусто для каждой вершины v в порядке вырождения G do BronKerbosch2({ v }, P ⋂ N( v ), X ⋂ N( v )) P := P \ { v } X := X ⋃ { v }Этот вариант алгоритма может быть признан эффективным для графов с небольшой вырожденностью [6], а эксперименты показывают, что он также хорошо работает на практике для больших разреженных социальных сетей и других реальных графов [7] .
В показанном примере графа алгоритм изначально вызывается с R = Ø, P = {1,2,3,4,5,6} и X = Ø. Опорная точка u должна быть выбрана как одна из вершин степени три, чтобы минимизировать количество рекурсивных вызовов; например, предположим, что u выбрана как вершина 2. Тогда в P \ N ( u ) остаются три вершины : вершины 2, 4 и 6.
Итерация внутреннего цикла алгоритма для v = 2 делает рекурсивный вызов алгоритма с R = {2}, P = {1,3,5} и X = Ø. В этом рекурсивном вызове один из 1 или 5 будет выбран в качестве опорной точки, и будет два рекурсивных вызова второго уровня, один для вершины 3 и другой для любой вершины, которая не была выбрана в качестве опорной точки. Эти два вызова в конечном итоге сообщат о двух кликах {1,2,5} и {2,3} . После возврата из этих рекурсивных вызовов вершина 2 добавляется к X и удаляется из P.
Итерация внутреннего цикла алгоритма для v = 4 делает рекурсивный вызов алгоритма с R = {4}, P = {3,5,6} и X = Ø (хотя вершина 2 принадлежит множеству X во внешнем вызове алгоритма, она не является соседом v и исключена из подмножества X, переданного в рекурсивный вызов). Этот рекурсивный вызов в конечном итоге сделает три рекурсивных вызова второго уровня алгоритма, которые сообщат о трех кликах {3,4}, {4,5} и {4,6}. Затем вершина 4 добавляется к X и удаляется из P.
В третьей и последней итерации внутреннего цикла алгоритма для v = 6 происходит рекурсивный вызов алгоритма с R = {6}, P = Ø и X = {4}. Поскольку этот рекурсивный вызов имеет P пустым, а X непустым, он немедленно возвращается назад, не сообщая больше ни о каких кликах, поскольку не может быть максимальной клики, которая включает вершину 6 и исключает вершину 4.
Таким образом, дерево вызовов алгоритма выглядит следующим образом:
БронКербош2(Ø, {1,2,3,4,5,6}, Ø) БронКербош2({2}, {1,3,5}, Ø) BronKerbosch2({2,3}, Ø, Ø): вывод {2, 3} БронКербош2({2,5}, {1}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): вывод {1,2,5} БронКербош2({4}, {3,5,6}, Ø) BronKerbosch2({3,4}, Ø, Ø): вывод {3,4} BronKerbosch2({4,5}, Ø, Ø): вывод {4,5} BronKerbosch2({4,6}, Ø, Ø): вывод {4,6} BronKerbosch2({6}, Ø, {4}): нет выходных данныхГраф в примере имеет вырожденность два; один возможный порядок вырожденности — 6,4,3,1,2,5. Если к вершинам применяется версия алгоритма Брона–Кербоша с упорядочением вершин, в этом порядке дерево вызовов выглядит следующим образом:
БронКербош3(Г) БронКербош2({6}, {4}, Ø) BronKerbosch2({6,4}, Ø, Ø): вывод {6,4} БронКербош2({4}, {3,5}, {6}) BronKerbosch2({4,3}, Ø, Ø): вывод {4,3} BronKerbosch2({4,5}, Ø, Ø): вывод {4,5} БронКербош2({3}, {2}, {4}) BronKerbosch2({3,2}, Ø, Ø): вывод {3,2} БронКербош2({1}, {2,5}, Ø) БронКербош2({1,2}, {5}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): вывод {1,2,5} BronKerbosch2({2}, {5}, {1,3}): нет выходных данных BronKerbosch2({5}, Ø, {1,2,4}): нет выходных данныхАлгоритм Брона–Кербоша не является алгоритмом, чувствительным к выходу : в отличие от некоторых других алгоритмов для задачи о клике, он не работает за полиномиальное время на максимальную сгенерированную клику. Однако он эффективен в худшем случае: по результатам Муна и Мозера (1965), любой граф с n вершинами имеет не более 3 n /3 максимальных клик, а худшее время работы алгоритма Брона–Кербоша (со стратегией поворота, которая минимизирует количество рекурсивных вызовов, сделанных на каждом шаге) составляет O(3 n /3 ), что соответствует этой границе. [8]
Для разреженных графов возможны более узкие границы. В частности, версию алгоритма Брона–Кербоша с упорядочением вершин можно заставить работать за время O( dn 3 d /3 ) , где d — вырожденность графа, мера его разреженности. Существуют d -вырожденные графы, для которых общее число максимальных клик равно ( n − d )3 d /3 , поэтому эта граница близка к узкой. [6]