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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм Брона — Кербоша — метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графа. Розробили 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 і се: Перші ne елементів — це елементи множини not, а наступні cene елементів — множини candidates. При такій реалізації, можна використовувати наступні твердження для перевірки умов у рядках 1 та 4:
  3. * ne = ce: множина candidates порожня
  4. * ne = 0: множина not порожня
  5. * се = 0: обидві множини candidates і not порожні
  6. * Для переміщення елементу з candidates в not потрібно збільшити індекс ne (за умови, що в якості вершини-кандидата вибиралася перша вершина з candidates, або вибрана вершина була обміняна з першою)
  7. Алгоритм може бути досить легко реалізований без застосування рекурсії
  8. Для прискорення алгоритму можна використовувати евристики при виборі вершини-кандидата на кроці 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 множину з більшим числом вершин.

С++ реалізація використовуючи стек

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;
} 

Складність алгоритму[ред.ред. код]

Лінійна відносно кількості клік в графі, де

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

Tomita, Tanaka і Haruhisa в 2006 показали, що в гіршому випадку алгоритм працює за O(3n/3).

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Реалізація алгоритму на Java
Реалізація алгоритму на Python

Література[ред.ред. код]

  • 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