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

У рачунарству, Брон–Кербош алгоритам је алгоритам за проналажење максималне клике у неусмереном графу. То јест, он наводи све подскупове чворова са две особине и то да сваки пар чворова у једном од наведених подскупова је повезан граном, и ненаведеном подскупу се могу додати додатни чворови све док чувају своју потпуну повезаност. Брон-Кербош алгоритам је креиран од стране Холандских научника Јоеп Кербосцх-а и Цоенраад Брон-а, који су објавили његов опис 1973. године. Мада други алгоритми за решавање проблема клике раде за време које је, у теорији, боље за улазе који имају мало максималних независних скупова, Брон-Кербош алгоритам и његова накнадна побољшања су често ефикаснија у пракси од алтернативних алгоритама. Добро је познат и широко се примењује у апликацијама које припадају области графова као што је рачунарска хемија.

Савремени алгоритам Аккоyунлу (1973), иако је представљен под различитим условима, може се посматрати као исти алгоритму Брон-Кербош, с' обзиром да генерише исту рекурзивну претрагу стабла.

Без пивотирања[уреди | уреди извор]

Основна форма Брон-Кербош алгоритма је рекурзивни бектрек алгоритам који тражи све максималне клике у датом графу Г. Уопштено, за дата три скупа Р, П и X он проналази максималну клику која садржи све чворове из Р, неке чворове из П и ниједан чвор из X. У оквиру рекурзивних позива, П и X су ограничени на чворове који формирају клику када се додају Р, јер су то једини чворови који се могу користити као излаз или за спречавање неких клика да се појаве као излаз.

Рекурзија се покреће, постављањем Р и X на празне скупове и П на скуп чворова графа. При сваком рекурзивном позиву алгоритам узима у обзир чворове из П и то: ако нема таквих чворова, или извештава да је Р максимална клика (ако је X празан), или претражује (бацктрацк-ом). За сваки чвор в изабран из П, врши се рекурзивни позив у ком се в додаје у Р и у ком су П и X ограничени на суседни скуп Н(в) чвора в, који проналази и пријављује све наставке клике у Р који садрже в. Онда премешта в из П у X, и наставља са наредним чвором из П.

Псеудокод:

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

Са пивотирањем[уреди | уреди извор]

Основни облик алгоритма, описан изнад, је неефикасан у случају графова са много немаксималних клика: врши се рекурзивни позив за сваку клику, била максимална или не. Да би се уштедело на времену и омогућило алгоритму да бектрекује брже у деловима претраге који садрже немаксималну клику, Брон и Кербош су представили варијацију алгоритма која садржи пивот чвор у, изабран из П (или чешће из П ∪ X). Било која максимална клика мора да садржи било у или један од његових несуседа, јер у супротном клика може бити увећана додавањем чвора у у њу. Стога, само у или његови несуседи требају бити тестирани као избор за чвор в који се додаје у Р у сваком рекузивном позиву алгоритма.

Псеудокод:

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

Ако је пивот изабран да смањи број рекурзивних позива, уштеда на времену у односу на непивотирајућу верзију алгоритма може бити значајна.

Постављањем чворова у редослед[уреди | уреди извор]

Алтернативни начин побољшања основног алгоритма укључује одбацивање пивотирања на најспољнијем нивоу рекурзије, и уместо тога изабрати редослед рекурзивних позива пажљиво како би се смањила величина скупа чворова кадидата П са сваким рекурзивним позивом.

Дегенерација графа Г је најмањи број д такав да сваки подграф графа Г саџи чвор степена д или мањег степена. Сваки граф има редослед дегенерације, редослед чворова такав да чвор има д или мање суседних чворова који долазе касније у редоследу; редослед дегенерације се може одредити за линеарно време понављањем избора чвора са најмањим степеном међу преосталим чворовима. Ако је редослед чворова в, кроз који Брон-Кербош алгоритам пролази, је редослед дегенерације, онда скуп чворова кандидата П при свком позиву (суседи од в који су касније у редоследу) гарантовано ће бити највише величине д. Скуп одбачених чворова X садржаће све раније суседе од в, и може бити доста већи од д. У рекурзивним позивима алгоритма доле највиши ниво рекурзије, пивотирајућа верзија може се и даље употребљавати.

Псеудокод:

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

Ова варијанта алгоритма је доказано ефикаснија за графове мале дегенерације, и истраживања показују да добро ради у пракси у великим ретким друштвеним мрежама и другим примерима графова из стварног живота.

Анализа најгорег случаја[уреди | уреди извор]

Брон-Кербош алгоритам не зависи од излаза: за разлику од других алгоритама за решавање проблема клике, не ради у полиномијалном времену по генерисаној максималној клики. Међутим је ефикасан у смислу најгорег случаја: резултатима Моон-а и Мосер-а (1965), граф са н чворова има највисе 3^н/3 максималних клика, и временска сложеност најгорег случаја Брон-Кербош алгоритма (са пивотирајућом стратегијом за смањење броја рекурзивних позива у сваком кораку) је О(3^н/3), одговара тој граници.

За ретке графове, мања граница је могућа. У верзији са постављањем редоследа чворова Брон-Кербош алгоритам може имати временску сложеност О(дн3^д/3), где је д дегенерација графа, мера његове разређености. Постоји д-дегенеративни граф са бројем максималних клика (н-д)3^д/3, што је уоквиру границе.

Референце[уреди | уреди извор]

-{

Аккоyунлу, Е. А. (1973), "Тхе енумератион оф маxимал цлиqуес оф ларге грапхс", СИАМ Јоурнал он Цомпутинг 2: 1–6
Цхен, Лингран . "Субструцтуре анд маxимал цоммон субструцтуре сеарцхинг", ин Бултинцк, Патрицк, Цомпутатионал Медицинал Цхемистрy фор Друг Дисцоверy. . ЦРЦ Пресс. 2004. пп. 483– 514.
Брон, Цоен; Кербосцх, Јоеп (1973). „Алгоритхм 457: финдинг алл цлиqуес оф ан ундирецтед грапх”. Цоммун. АЦМ (АЦМ). 16 (9): 575—577.
Цазалс, Ф.; Каранде, C. (2008). „А ноте он тхе проблем оф репортинг маxимал цлиqуес”. Тхеоретицал Цомпутер Сциенце. 407 (1): 564—568. дои:10.1016/ј.тцс.2008.05.010.
Еппстеин, Давид; Лöффлер, Маартен; Страсх, Даррен (2010), "Листинг алл маxимал цлиqуес ин спарсе грапхс ин неар-оптимал тиме", ин Цхеонг, Отфриед; Цхwа, Кyунг-Yонг; Парк, Кунсоо, 21ст Интернатионал Сyмпосиум он Алгоритхмс анд Цомпутатион (ИСААЦ 2010), Јеју, Кореа, Лецтуре Нотес ин Цомпутер Сциенце 6506, Спрингер-Верлаг. стр. 403–414
Еппстеин, Давид; Страсх, Даррен (2011), "Листинг алл маxимал цлиqуес ин ларге спарсе реал-wорлд грапхс", 10тх Интернатионал Сyмпосиум он Еxпериментал Алгоритхмс
„Цлиqуес оф а грапх—вариатионс он тхе Брон–Кербосцх алгоритхм”. Интернатионал Јоурнал оф Параллел Программинг. 5 (3): 209—238.
Коцх, Ина (2001), "Енумератинг алл цоннецтед маxимал цоммон субграпхс ин тwо грапхс", Тхеоретицал Цомпутер Сциенце 250 (1–2): 1–30
Моон, Ј. W.; Мосер, L. (1965), "Он цлиqуес ин грапхс", Исраел Ј. Матх. 3: 23–28
Томита, Етсуји; Танака, Акира; Такахасхи, Харухиса (2006). „Тхе wорст-цасе тиме цомплеxитy фор генератинг алл маxимал цлиqуес анд цомпутатионал еxпериментс”. Тхеоретицал Цомпутер Сциенце. 363 (1): 28—42. дои:10.1016/ј.тцс.2006.06.015.

Спољашње везе[уреди | уреди извор]

Брон-Кербосх алгоритхм имплементатион ин Пyтхон
Финдинг алл цлиqуес оф ан ундирецтед грапх. Семинар нотес бy Мицхаела Регнери, Јануарy 11, 2007.