Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Алгоритм Брона — Кербоша — метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графу. Розробили 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
Реалізація
- Множина compsub використовується як стек, і може бути реалізована за допомогою глобального одновимірного масиву.
- Множини candidates і not можна зберігати в одновимірному масиві, використовуючи два індекси ne і се: Перші ne елементів — це елементи множини not, а наступні ce−ne елементів — множини candidates. При такій реалізації, можна використовувати наступні твердження для перевірки умов у рядках 1 та 4:
- * ne = ce: множина candidates порожня
- * ne = 0: множина not порожня
- * се = 0: обидві множини candidates і not порожні
- * Для переміщення елементу з candidates в not потрібно збільшити індекс ne (за умови, що як вершина-кандидат вибиралася перша вершина з candidates, або вибрана вершина була обміняна з першою)
- Алгоритм може бути досить легко реалізований без застосування рекурсії
- Для прискорення алгоритму можна використовувати евристики при виборі вершини-кандидата на кроці 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:
- Умова в основному циклі: not не повинно містити жодної вершини, НЕ З'ЄДНАНОЇ З ЖОДНОЮ з вершин у множині candidates
- Для формування new_candidates і new_not, необхідно видаляти з candidates і not вершини, З'ЄДНАНІ з обраною вершиною.
Знаходження максимальної кліки / незалежної множини максимального розміру (МНМ)
Для того, щоб алгоритм шукав максимальну за розміром кліку / МНМ, необхідно:
- Завести ще одну множину max_comsub(початкове значення — порожня множина)
- У кроці 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).
Див. також
Література
- 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
Посилання
Реалізація алгоритму на Java [ 26 січня 2011 у Wayback Machine.]
Реалізація алгоритму на Python [ 29 жовтня 2013 у Wayback Machine.]
Реалізація алгоритму на C++11 з модульними тестами [ 12 лютого 2017 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Brona Kerbosha metod gilok i mezh dlya poshuku vsih klik a takozh maksimalnih za vklyuchennyam nezalezhnih mnozhin vershin neoriyentovanogo grafu Rozrobili 1973 roku gollandski matematiki Bronnij i Kerbosh Dosi ce odin iz najefektivnishih algoritmiv poshuku klik AlgoritmAlgoritm vikoristovuye toj fakt sho bud yaka klika v grafi ye jogo maksimalnim za vklyuchennyam povnim pidgrafom Pochinayuchi z odinichnoyi vershini sho utvoryuye povnij pidgraf algoritm na kozhnomu kroci namagayetsya zbilshiti vzhe pobudovanij povnij pidgraf dodayuchi v nogo vershini z mnozhini kandidativ Visoka shvidkist zabezpechuyetsya vidtinannyam pri perebori variantiv yaki garantovano ne privedut do pobudovi kliki dlya chogo vikoristovuyetsya dodatkova mnozhina v yaku pomishayutsya vershini yaki vzhe buli vikoristani dlya zbilshennya povnogo pidgrafu Algoritm operuye troma mnozhinami vershin grafu Mnozhina compsub mnozhina sho mistit na kozhnomu kroci rekursiyi povnij pidgraf dlya danogo kroku Buduyetsya rekursivno Mnozhina candidates mnozhina vershin yaki mozhut zbilshiti compsub Mnozhina not mnozhina vershin yaki vzhe vikoristovuvalisya dlya rozshirennya compsub na poperednih krokah algoritmu Algoritm ye rekursivnoyu proceduroyu sho zastosovuyetsya do cih troh mnozhinam PROCEDURA extend candidates not POKI candidates NE porozhno I not NE mistit vershini z yednanoyi z usima vershinami z candidates VIKONUVATI 1 Vibirayemo vershinu v z candidates i dodayemo yiyi v compsub 2 Formuyemo new candidates i new not vidalyayuchi z candidates i not vershini ne Z YeDNANI z v 3 YaKShO new candidates i new not porozhni 4 TO compsub klika 5 INAKShE rekursivno viklikayemo extend new candidates new not 6 Vidalyayemo v z compsub i candidates i pomishayemo v not Realizaciya Mnozhina compsub vikoristovuyetsya yak stek i mozhe buti realizovana za dopomogoyu globalnogo odnovimirnogo masivu Mnozhini candidates i not mozhna zberigati v odnovimirnomu masivi vikoristovuyuchi dva indeksi ne i se Pershi ne elementiv ce elementi mnozhini not a nastupni ce ne elementiv mnozhini candidates Pri takij realizaciyi mozhna vikoristovuvati nastupni tverdzhennya dlya perevirki umov u ryadkah 1 ta 4 ne ce mnozhina candidates porozhnya ne 0 mnozhina not porozhnya se 0 obidvi mnozhini candidates i not porozhni Dlya peremishennya elementu z candidates v not potribno zbilshiti indeks ne za umovi sho yak vershina kandidat vibiralasya persha vershina z candidates abo vibrana vershina bula obminyana z pershoyu Algoritm mozhe buti dosit legko realizovanij bez zastosuvannya rekursiyi Dlya priskorennya algoritmu mozhna vikoristovuvati evristiki pri vibori vershini kandidata na kroci 1 S realizaciya algoritmu vikoristovuyuchi masivi yak stek list lt set lt int gt gt kerbosh int amp a int SIZE set lt int gt M G K P list lt set lt int gt gt REZULT for int i 0 i lt SIZE i K insert i int v Count 0 cnt 0 int Stack1 100 std set lt int gt Stack2 100 std set lt int gt 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 lt 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 VariaciyiZnahodzhennya maksimalnih po vklyuchennyu nezalezhnih mnozhin vershin Nevazhko pobachiti sho zadacha pro kliku i zadacha pro nezalezhni mnozhini po suti ekvivalentni kozhna z nih vihodit z inshoyi shlyahom pobudovi dopovnennya grafu takogo grafu v yakomu ye vsi vershini vihidnogo grafu prichomu v dopovnenni grafu vershini z yednani rebrom todi i tilki todi yaksho voni ne buli z yednani u vihidnomu grafi Tomu algoritm Brona Kerbosha mozhna vikoristovuvati dlya znahodzhennya maksimalnih po vklyuchennyu nezalezhnih mnozhin vershin yaksho pobuduvati dopovnennya do vihidnogo grafu abo zminivshi umovu dlya osnovnogo ciklu umovu zavershennya ta formuvannya novih mnozhin new candidates i new not Umova v osnovnomu cikli not ne povinno mistiti zhodnoyi vershini NE Z YeDNANOYi Z ZhODNOYu z vershin u mnozhini candidates Dlya formuvannya new candidates i new not neobhidno vidalyati z candidates i not vershini Z YeDNANI z obranoyu vershinoyu Znahodzhennya maksimalnoyi kliki nezalezhnoyi mnozhini maksimalnogo rozmiru MNM Dlya togo shob algoritm shukav maksimalnu za rozmirom kliku MNM neobhidno Zavesti she odnu mnozhinu max comsub pochatkove znachennya porozhnya mnozhina U kroci 4 koli znajdena chergova klika MNM porivnyati rozmir kilkist vershin v comsubi v max comsubi pomistiti v max comsub mnozhinu z bilshim chislom vershin S realizaciya vikoristovuyuchi stek list lt set lt int gt gt kerbosh int amp a int SIZE set lt int gt M G K P list lt set lt int gt gt REZULT for int i 0 i lt SIZE i K insert i int v Count 0 cnt 0 int Stack1 100 std set lt int gt Stack2 100 std set lt int gt 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 lt 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 Skladnist algoritmuLinijna vidnosno kilkosti klik v grafi de n kilkist vershin m kilkist reber m kilkist klik Tomita Tanaka i Haruhisa v 2006 pokazali sho v girshomu vipadku algoritm pracyuye za O 3n 3 Div takozhHromatichne chislo Spisok algoritmiv Algoritmi na grafahLiteraturaBron 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 42PosilannyaRealizaciya algoritmu na Java 26 sichnya 2011 u Wayback Machine Realizaciya algoritmu na Python 29 zhovtnya 2013 u Wayback Machine Realizaciya algoritmu na C 11 z modulnimi testami 12 lyutogo 2017 u Wayback Machine