В информатике , то алгоритм Брон-Kerbosch является алгоритмом перебора для нахождения всех максимальных клик в неориентированном графе . То есть он перечисляет все подмножества вершин с двумя свойствами, что каждая пара вершин в одном из перечисленных подмножеств связана ребром, и ни одно из перечисленных подмножеств не может иметь никаких дополнительных вершин, добавленных к нему, при сохранении его полной связности . Алгоритм Брона – Кербоша был разработан голландскими учеными Коэнрадом Броном и Джоэпом Кербошем , которые опубликовали его описание в 1973 году.
Хотя другие алгоритмы для решения проблемы клики имеют время выполнения, которое теоретически лучше для входных данных, которые имеют несколько максимальных независимых наборов, алгоритм Брон-Кербоша и последующие его усовершенствования часто сообщаются как более эффективные на практике, чем альтернативы. [1] Он хорошо известен и широко используется в таких прикладных областях алгоритмов графов , как вычислительная химия . [2]
Современный алгоритм Аккоюнлу (1973) , хотя и представлен в разных терминах, можно рассматривать как идентичный алгоритму Брона – Кербоша, поскольку он генерирует то же дерево поиска. [3]
Без поворота
Основная форма алгоритма Брон-Kerbosch является рекурсивным возвратами алгоритм , который ищет все максимальные клики в данной графе G . В целом, учитывая три непересекающихся множества вершин R , P и X , он находит максимальные клики , которые включают в себя все вершины в R , некоторые из вершин в Р , и ни одна из вершин X . В каждом вызове алгоритма, Р и Х непересекающиеся множества, объединение которых состоит из тех вершин , которые образуют клики при добавлении к R . Другими словами, Р ∪ X есть множество вершин , которые соединены с каждым элементом R . Когда P и X оба пусты, больше нет элементов, которые можно добавить к R , поэтому R является максимальной кликой, и алгоритм выводит R.
Рекурсия инициируется установкой R и X как пустое множество, а P как набор вершин графа. В каждом рекурсивном вызове алгоритм по очереди рассматривает вершины в P ; если таких вершин нет, он либо сообщает R как максимальную клику (если X пусто), либо выполняет возврат. Для каждой вершины V , выбранный из Р , это делает рекурсивный вызов , в котором V добавляется к R , и в которой Р и Х имеют ограниченный к набору соседей 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 и его не-соседи должны быть проверены как варианты выбора для вершины v, которая добавляется к R при каждом рекурсивном вызове алгоритма. В псевдокоде:
алгоритм BronKerbosch2 (R, P, X) : если P и X оба пусты, то сообщает R как максимальную клику выберите опорную вершину u в P ⋃ X для каждой вершины v в P \ N ( u ) do BronKerbosch2 ( R ⋃ { v }, P ⋂ N ( v ), X ⋂ N ( v )) P : = P \ { v } X : = X ⋃ { v }
Если точка поворота выбрана так, чтобы минимизировать количество рекурсивных вызовов, выполняемых алгоритмом, экономия времени выполнения по сравнению с версией алгоритма без поворота может быть значительной. [5]
С порядком вершин
Альтернативный метод улучшения базовой формы алгоритма Брона-Кербоша включает отказ от поворота на самом внешнем уровне рекурсии и вместо этого тщательный выбор порядка рекурсивных вызовов, чтобы минимизировать размеры наборов P вершин-кандидатов в каждой рекурсивной вызов.
Вырождение графа G является наименьшим числом d таким образом, что каждый подграф из G имеет вершину с степени г или меньше. Каждый граф имеет порядок вырождения , такой порядок вершин, что каждая вершина имеет 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.
Таким образом, дерево вызовов алгоритма выглядит так:
BronKerbosch2 (Ø, {1,2,3,4,5,6}, Ø) BronKerbosch2 ({2}, {1,3,5}, Ø) BronKerbosch2 ({2,3}, Ø, Ø): выход {2, 3} BronKerbosch2 ({2,5}, {1}, Ø) BronKerbosch2 ({1,2,5}, Ø, Ø): выход {1,2,5} BronKerbosch2 ({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 (G) BronKerbosch2 ({6}, {4}, Ø) BronKerbosch2 ({6,4}, Ø, Ø): выход {6,4} BronKerbosch2 ({4}, {3,5}, {6}) BronKerbosch2 ({4,3}, Ø, Ø): выход {4,3} BronKerbosch2 ({4,5}, Ø, Ø): выход {4,5} BronKerbosch2 ({3}, {2}, {4}) BronKerbosch2 ({3,2}, Ø, Ø): выход {3,2} BronKerbosch2 ({1}, {2,5}, Ø) BronKerbosch2 ({1,2}, {5}, Ø) BronKerbosch2 ({1,2,5}, Ø, Ø): выход {1,2,5} BronKerbosch2 ({2}, {5}, {1,3}): нет вывода BronKerbosch2 ({5}, Ø, {1,2,4}): нет вывода
Анализ наихудшего случая
Алгоритм Брона – Кербоша не является алгоритмом, чувствительным к выходным данным : в отличие от некоторых других алгоритмов для задачи о клике, он не выполняется за полиномиальное время на сгенерированную максимальную клику. Однако он эффективен в худшем случае: согласно результату Moon & Moser (1965) , любой n- вершинный граф имеет не более 3 n / 3 максимальных клик, а время работы алгоритма Брон-Кербоша в худшем случае алгоритм (со стратегией поворота, которая минимизирует количество рекурсивных вызовов, выполняемых на каждом шаге) составляет O (3 n / 3 ), что соответствует этой границе. [8]
Для разреженных графов возможны более жесткие границы. В частности, версию алгоритма Брона – Кербоша с упорядочением вершин можно заставить работать за время O ( dn 3 d / 3 ) , где d - вырожденность графа, мера его разреженности. Существуют d -вырожденные графы, для которых общее количество максимальных клик равно ( n - d ) 3 d / 3 , так что эта оценка близка к точной. [6]
Заметки
- ^ Cazals & Karande (2008) .
- ^ Чен (2004) .
- ^ Джонстон (1976) .
- ^ Томита, Танака и Такахаши (2006) ; Казальс и Каранде (2008) .
- ^ Джонстон (1976) ; Кох (2001) ; Казальс и Каранде (2008) .
- ^ а б в Эппштейн, Лёффлер и Страш (2010) .
- ^ Б Эпштайна & Strash (2011) .
- Перейти ↑ Tomita, Tanaka & Takahashi (2006) .
Рекомендации
- Аккоюнлу, EA (1973), "Перечисление максимальных клик больших графов", SIAM журнал по вычислениям , 2 : 1-6, DOI : 10,1137 / 0202001.
- Чен, Лингран (2004), «Поиск субструктуры и максимальной общей субструктуры», в Bultinck, Patrick (ed.), Computational Medicinal Chemistry for Drug Discovery , CRC Press, pp. 483–514, ISBN 978-0-8247-4774-9.
- Брон, Коэн; Кербош, Джоп (1973), "Алгоритм 457: поиск всех клик неориентированного графа", Commun. АСМ , АСМ, 16 (9): 575-577, DOI : 10,1145 / 362342,362367.
- Cazals, F .; Karande, C. (2008), "Замечание о проблеме отчетности максимальных клик" (PDF) , теоретическая информатика , 407 (1): 564-568, DOI : 10.1016 / j.tcs.2008.05.010[ постоянная мертвая ссылка ] .
- Эпштейн, Дэвид ; Лёффлер, Маартен; Страш, Даррен (2010), «Перечисление всех максимальных клик в разреженных графах за почти оптимальное время», в Cheong, Otfried; Чва, Кён-Ён; Парк, Кунсу (ред.), 21-й Международный симпозиум по алгоритмам и вычислениям (ISAAC 2010), Чеджу, Корея , Lecture Notes in Computer Science, 6506 , Springer-Verlag, стр. 403–414, arXiv : 1006.5440 , doi : 10.1007 / 978-3-642-17517-6_36.
- Эпштейн, Дэвид ; Страш, Даррен (2011), «Список всех максимальных клик в больших разреженных графах реального мира», 10-й Международный симпозиум по экспериментальным алгоритмам , arXiv : 1103.0318 , Bibcode : 2011arXiv1103.0318E.
- Джонстон, НС (1976), "Клик графа-вариаций на алгоритме Брон-Kerbosch", Международный журнал параллельного программирования , 5 (3): 209-238, DOI : 10.1007 / BF00991836.
- Кох, Ина (2001), «Перечисление всех связанных максимальных общих подграфов в двух графах», Теоретическая информатика , 250 (1-2): 1-30, DOI : 10.1016 / S0304-3975 (00) 00286-3.
- Луна, JW; Мозер, Л. (1965), «О кликах в графах», Israel J. Math. , 3 : 23-28, DOI : 10.1007 / BF02760024 , МР 0182577.
- Томита, Эцудзи; Танака, Акира; Такахаши, Харухиса (2006), «Наихудшая временная сложность для генерации всех максимальных клик и вычислительных экспериментов», Теоретическая информатика , 363 (1): 28–42, DOI : 10.1016 / j.tcs.2006.06.015.
Внешние ссылки
- Обзор алгоритма Брон-Кербоша и его вариаций Алессио Конте
- Реализация алгоритма Брон-Кербоша, визуализированная в Javascript
- Реализация алгоритма Брон-Кербоша на Python
- Алгоритм Брон-Кербоша с реализацией порядка вершин в Python
- Реализация алгоритма Брон-Кербоша на C ++
- Реализация алгоритма Брон-Кербоша на C ++ 11 с модульными тестами
- Реализация на C ++ алгоритмов, представленных Дарреном Страшем в Eppstein, Strash (2011)
- Нахождение всех клик неориентированного графа . Заметки о семинаре Микаэлы Регнери, 11 января 2007 г.
- Брон-Кербош, реализация алгоритмов на PHP, библиотека с композитором, установленная Серджио Самбрано