Bron–Kerboš algoritam

U računarstvu, Bron–Kerboš algoritam je algoritam za pronalaženje maksimalne klike u neusmerenom grafu. To jest, on navodi sve podskupove čvorova sa dve osobine i to da svaki par čvorova u jednom od navedenih podskupova je povezan granom, i nenavedenom podskupu se mogu dodati dodatni čvorovi sve dok čuvaju svoju potpunu povezanost. Bron-Kerboš algoritam je kreiran od strane Holandskih naučnika Joep Kerbosch-a i Coenraad Bron-a, koji su objavili njegov opis 1973. godine. Mada drugi algoritmi za rešavanje problema klike rade za vreme koje je, u teoriji, bolje za ulaze koji imaju malo maksimalnih nezavisnih skupova, Bron-Kerboš algoritam i njegova naknadna poboljšanja su često efikasnija u praksi od alternativnih algoritama. Dobro je poznat i široko se primenjuje u aplikacijama koje pripadaju oblasti grafova kao što je računarska hemija.

Savremeni algoritam Akkoyunlu (1973), iako je predstavljen pod različitim uslovima, može se posmatrati kao isti algoritmu Bron-Kerboš, s' obzirom da generiše istu rekurzivnu pretragu stabla.

Bez pivotiranja[uredi | uredi izvor]

Osnovna forma Bron-Kerboš algoritma je rekurzivni bektrek algoritam koji traži sve maksimalne klike u datom grafu G. Uopšteno, za data tri skupa R, P i X on pronalazi maksimalnu kliku koja sadrži sve čvorove iz R, neke čvorove iz P i nijedan čvor iz X. U okviru rekurzivnih poziva, P i X su ograničeni na čvorove koji formiraju kliku kada se dodaju R, jer su to jedini čvorovi koji se mogu koristiti kao izlaz ili za sprečavanje nekih klika da se pojave kao izlaz.

Rekurzija se pokreće, postavljanjem R i X na prazne skupove i P na skup čvorova grafa. Pri svakom rekurzivnom pozivu algoritam uzima u obzir čvorove iz P i to: ako nema takvih čvorova, ili izveštava da je R maksimalna klika (ako je X prazan), ili pretražuje (backtrack-om). Za svaki čvor v izabran iz P, vrši se rekurzivni poziv u kom se v dodaje u R i u kom su P i X ograničeni na susedni skup N(v) čvora v, koji pronalazi i prijavljuje sve nastavke klike u R koji sadrže v. Onda premešta v iz P u X, i nastavlja sa narednim čvorom iz P.

Pseudokod:

Bron-Kerbosch(R,P,X)
     if P i X prazni
        return R je maksimalna klika;
     for svaki cvor v iz P do
        Bron-Kerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v));
        P:= P \ {v};
        X:= X ∪ {v};

Sa pivotiranjem[uredi | uredi izvor]

Osnovni oblik algoritma, opisan iznad, je neefikasan u slučaju grafova sa mnogo nemaksimalnih klika: vrši se rekurzivni poziv za svaku kliku, bila maksimalna ili ne. Da bi se uštedelo na vremenu i omogućilo algoritmu da bektrekuje brže u delovima pretrage koji sadrže nemaksimalnu kliku, Bron i Kerboš su predstavili varijaciju algoritma koja sadrži pivot čvor u, izabran iz P (ili češće iz P ∪ X). Bilo koja maksimalna klika mora da sadrži bilo u ili jedan od njegovih nesuseda, jer u suprotnom klika može biti uvećana dodavanjem čvora u u nju. Stoga, samo u ili njegovi nesusedi trebaju biti testirani kao izbor za čvor v koji se dodaje u R u svakom rekuzivnom pozivu algoritma.

Pseudokod:

 BronKerbosch(R,P,X)
        if P i X prazni
            return R je maksimalna klika;
        izaberi pivot cvor u iz P ∪ X;
        for svaki cvor v iz P \ N(u) do
            BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v));
            P:= P \ {v};
            X:= X ∪ {v};

Ako je pivot izabran da smanji broj rekurzivnih poziva, ušteda na vremenu u odnosu na nepivotirajuću verziju algoritma može biti značajna.

Postavljanjem čvorova u redosled[uredi | uredi izvor]

Alternativni način poboljšanja osnovnog algoritma uključuje odbacivanje pivotiranja na najspoljnijem nivou rekurzije, i umesto toga izabrati redosled rekurzivnih poziva pažljivo kako bi se smanjila veličina skupa čvorova kadidata P sa svakim rekurzivnim pozivom.

Degeneracija grafa G je najmanji broj d takav da svaki podgraf grafa G sadži čvor stepena d ili manjeg stepena. Svaki graf ima redosled degeneracije, redosled čvorova takav da čvor ima d ili manje susednih čvorova koji dolaze kasnije u redosledu; redosled degeneracije se može odrediti za linearno vreme ponavljanjem izbora čvora sa najmanjim stepenom među preostalim čvorovima. Ako je redosled čvorova v, kroz koji Bron-Kerboš algoritam prolazi, je redosled degeneracije, onda skup čvorova kandidata P pri svkom pozivu (susedi od v koji su kasnije u redosledu) garantovano će biti najviše veličine d. Skup odbačenih čvorova X sadržaće sve ranije susede od v, i može biti dosta veći od d. U rekurzivnim pozivima algoritma dole najviši nivo rekurzije, pivotirajuća verzija može se i dalje upotrebljavati.

Pseudokod:

Bron-Kerbosch(G)
     P = V(G);
     R = X = prazan skup;
     for svako cvor v u redosledu degeneracije grafa G do 
        Bron-Kerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v));
        P:= P \ {v};
        X:= X ∪ {v};

Ova varijanta algoritma je dokazano efikasnija za grafove male degeneracije, i istraživanja pokazuju da dobro radi u praksi u velikim retkim društvenim mrežama i drugim primerima grafova iz stvarnog života.

Analiza najgoreg slučaja[uredi | uredi izvor]

Bron-Kerboš algoritam ne zavisi od izlaza: za razliku od drugih algoritama za rešavanje problema klike, ne radi u polinomijalnom vremenu po generisanoj maksimalnoj kliki. Međutim je efikasan u smislu najgoreg slučaja: rezultatima Moon-a i Moser-a (1965), graf sa n čvorova ima najvise 3^n/3 maksimalnih klika, i vremenska složenost najgoreg slučaja Bron-Kerboš algoritma (sa pivotirajućom strategijom za smanjenje broja rekurzivnih poziva u svakom koraku) je O(3^n/3), odgovara toj granici.

Za retke grafove, manja granica je moguća. U verziji sa postavljanjem redosleda čvorova Bron-Kerboš algoritam može imati vremensku složenost O(dn3^d/3), gde je d degeneracija grafa, mera njegove razređenosti. Postoji d-degenerativni graf sa brojem maksimalnih klika (n-d)3^d/3, što je uokviru granice.

Reference[uredi | uredi izvor]

-{

Akkoyunlu, E. A. (1973), "The enumeration of maximal cliques of large graphs", SIAM Journal on Computing 2: 1–6
Chen, Lingran . "Substructure and maximal common substructure searching", in Bultinck, Patrick, Computational Medicinal Chemistry for Drug Discovery. . CRC Press. 2004. pp. 483– 514.
Bron, Coen; Kerbosch, Joep (1973). „Algorithm 457: finding all cliques of an undirected graph”. Commun. ACM (ACM). 16 (9): 575—577.
Cazals, F.; Karande, C. (2008). „A note on the problem of reporting maximal cliques”. Theoretical Computer Science. 407 (1): 564—568. doi:10.1016/j.tcs.2008.05.010.
Eppstein, David; Löffler, Maarten; Strash, Darren (2010), "Listing all maximal cliques in sparse graphs in near-optimal time", in Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo, 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, Lecture Notes in Computer Science 6506, Springer-Verlag. стр. 403–414
Eppstein, David; Strash, Darren (2011), "Listing all maximal cliques in large sparse real-world graphs", 10th International Symposium on Experimental Algorithms
„Cliques of a graph—variations on the Bron–Kerbosch algorithm”. International Journal of Parallel Programming. 5 (3): 209—238.
Koch, Ina (2001), "Enumerating all connected maximal common subgraphs in two graphs", Theoretical Computer Science 250 (1–2): 1–30
Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel J. Math. 3: 23–28
Tomita, Etsuji; Tanaka, Akira; Takahashi, Haruhisa (2006). „The worst-case time complexity for generating all maximal cliques and computational experiments”. Theoretical Computer Science. 363 (1): 28—42. doi:10.1016/j.tcs.2006.06.015.

Spoljašnje veze[uredi | uredi izvor]

Bron-Kerbosh algorithm implementation in Python
Finding all cliques of an undirected graph. Seminar notes by Michaela Regneri, January 11, 2007.