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

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

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

Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 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

Реализация

  1. Множество compsub используется как стек, и может быть реализовано с помощью глобального одномерного массива.
  2. Множества candidates и not можно хранить в одномерном массиве используя два индекса ne и се: Первые элементов — это элементы множества not, а следующие ce-ne элементов — множество candidates. При такой реализации, можно использовать следующие утверждения для проверки условий в строках 1 и 4:
    • ne = ce: множество candidates пусто
    • ne = 0: множество not пусто
    • се = 0: оба множества candidates и notпусты
    • Для перемещение элемента из candidates в notнужно увеличить индекс ne (при условии, что в качестве вершины-кандидата выбиралась первая вершина из candidates, или выбранная вершина была обменяна с первой)
  3. Алгоритм может быть достаточно легко реализован без применения рекурсии
  4. Для ускорения алгоритма можно использовать эвристики при выборе вершины-кандидата на шаге 1

С++ имплементация алгоритма (используя массивы как стэк)

list<set<int> >kerbosh(int **&a,int SIZE)
{
   set <int> M,G,K,P;
   list<set<int> > REZULT;
   for (int i=0; i<SIZE;i++)
   {
       K.insert(i);
   }
   int v,Count=0,cnt=0;
   int Stack1[100];
   std::set<int> Stack2[100];
   std::set<int>::iterator theIterator;
   theIterator=K.begin();
   while ((K.size()!=0)||(M.size()!=0))
   {
       if (K.size()!=0)
       {
           theIterator=K.begin();
           v=*theIterator;
           Stack2[++Count]=M;
           Stack2[++Count]=K;
           Stack2[++Count]=P;
           Stack1[++cnt]=v;
           M.insert(v);
           for (int i=0;i<SIZE;i++)
           {
               if (a[v][i])
               {
                   theIterator=K.find(i);
                   if (theIterator!=K.end())
                   {
                       K.erase(theIterator);
                   }
                   theIterator=P.find(i);
                   if (theIterator!=P.end())
                   {
                       P.erase(theIterator);
                   }
               }
           }
           theIterator=K.find(v);
           if (theIterator!=K.end())
           {
               K.erase(theIterator);
           }
       }
       else
       {
           if (P.size()==0)
           {
               REZULT.push_back(M);
           }
           v=Stack1[cnt--];
           P=Stack2[Count--];
           K=Stack2[Count--];
           M=Stack2[Count--];
           theIterator=K.find(v);
           if (theIterator!=K.end())
           {
               K.erase(theIterator);
           }
           P.insert(v);
       }
   }
   return  REZULT;
}

Вариации

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

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

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

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

Нахождение максимальной клики / независимого множества максимального размера (МНМ)

Для того, чтобы алгоритм искал максимальную по размеру клику/МНМ, необходимо:

  1. завести еще одно множество max_comsub (начальное значение — пустое множество)
  2. на шаге 4, когда найдена очередная клика/МНМ, сравнить размер (количество вершин) в comsub и в max_comsub и поместить в max_comsub множество с большим числом вершин.

c++ имплементация используя стэк

list<set<int> >kerbosh(int **&a,int SIZE)
{
   set <int> M,G,K,P;
   list<set<int> > REZULT;
   for (int i=0; i<SIZE;i++)
   {
       K.insert(i);
   }
   int v,Count=0,cnt=0;
   int Stack1[100];
   std::set<int> Stack2[100];
   std::set<int>::iterator theIterator;
   theIterator=K.begin();
   while ((K.size()!=0)||(M.size()!=0))
   {
       if (K.size()!=0)
       {
           theIterator=K.begin();
           v=*theIterator;
           Stack2[++Count]=M;
           Stack2[++Count]=K;
           Stack2[++Count]=P;
           Stack1[++cnt]=v;
           M.insert(v);
           for (int i=0;i<SIZE;i++)
           {
               if (a[v][i])
               {
                   theIterator=K.find(i);
                   if (theIterator!=K.end())
                   {
                       K.erase(theIterator);
                   }
                   theIterator=P.find(i);
                   if (theIterator!=P.end())
                   {
                       P.erase(theIterator);
                   }
               }
           }
           theIterator=K.find(v);
           if (theIterator!=K.end())
           {
               K.erase(theIterator);
           }
       }
       else
       {
           if (P.size()==0)
           {
               REZULT.push_back(M);
           }
           v=Stack1[cnt--];
           P=Stack2[Count--];
           K=Stack2[Count--];
           M=Stack2[Count--];
           theIterator=K.find(v);
           if (theIterator!=K.end())
           {
               K.erase(theIterator);
           }
           P.insert(v);
       }
   }
   return  REZULT;
} 

Сложность алгоритма

Линейна относительно количества клик в графе, а точнее O(nmμ), где

  • n — количество вершин
  • m — количество ребер
  • μ — количество клик

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

Примечания

См. также

Ссылки

Литература


Wikimedia Foundation. 2010.

Нужно сочинение?

Полезное


Смотреть что такое "Алгоритм Брона — Кербоша" в других словарях:

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

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Задача о клике — относится к классу NP полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1] …   Википедия

  • Задача о независимом наборе — Задача о независимом множестве относится к классу NP полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике. Независимый набор из 9 голубых вершин Множество вершин графа называется независимым, если никакие две… …   Википедия

  • Задача о независимом множестве — относится к классу NP полных задач в области теории графов. Эквивалентна задаче о клике. Содержание 1 Определения 2 Максимальное независимое множество в дереве …   Википедия

  • Максимальное независимое множество вершин в дереве — Задача о независимом множестве относится к классу NP полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике. Независимый набор из 9 голубых вершин Множество вершин графа называется независимым, если никакие две… …   Википедия

  • Клика (теория графов) — У этого термина существуют и другие значения, см. Клика. Клика  полный подграф неориентированного графа. Другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и,… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»