A Bron-Kerbosh algoritmus egy elágazó és kötött módszer egy irányítatlan gráf összes klikkjének (valamint maximális független csúcskészletének) megtalálására . Bron és Kerbosch holland matematikusok fejlesztették ki 1973 -ban, és még mindig az egyik leghatékonyabb klikkkereső algoritmus.
Az algoritmus azt a tényt használja, hogy a gráfban minden kattintás a befogadás-maximális teljes részgráfja . Egyetlen csúcsból kiindulva (egy teljes részgráfot képezve) az algoritmus minden lépésben megpróbálja növelni a már megszerkesztett teljes részgráfot úgy, hogy a jelöltek halmazából csúcsokat ad hozzá. A nagy sebességet úgy biztosítják , hogy levágják azokat az opciókat, amelyek nem vezetnek klikk felépítéséhez, amelyhez egy további halmazt használnak, amelyben olyan csúcsok kerülnek elhelyezésre, amelyeket már felhasználtak a teljes részgráf növelésére.
Az algoritmus három gráfcsúcs-készleten működik:
Az algoritmus egy rekurzív eljárás, amelyet erre a három halmazra alkalmaznak.
ELJÁRÁS kiterjesztése ( jelöltek , nem ): Hacsak a jelöltek nem üresek ÉS NEM tartalmaz olyan csúcsot, amely a jelöltek MINDEN csúcsához CSATLAKOZTAT , VÉGREHAJTJA : 1 Válassza ki a v csúcsot a jelöltek közül , és adja hozzá a compsubhoz. 2 Űrítse ki az új_jelöltek és a new_not űrlapot , távolítsa el a jelöltek közül a nem CSATLAKOZTATOTT csúcsokat a v 3 -hoz, HA a new_candidates és az new_not üresek. 4 TO compsub - klikk 5 ELSE hívás kiterjesztése rekurzívan ( new_candidates , new_not ) 6 Távolítsa el a v-t a compsubból és a jelöltek közül , és ne tegye beKönnyen belátható, hogy a klikkprobléma és a független halmazprobléma lényegében ekvivalens: mindegyiket úgy kapjuk meg a másikból, hogy megszerkesztünk egy gráfkomplementer - egy gráfot, amely tartalmazza az eredeti gráf összes csúcsát, és a gráf komplementerében A csúcsokat akkor és csak akkor kapcsoljuk össze éllel, ha az eredeti gráfban nem voltak összekötve.
Ezért a Bron-Kerbosch algoritmus felhasználható a maximális befogadástól független csúcshalmazok megkeresésére az eredeti gráfhoz hozzáadással, vagy a fő hurokban lévő feltétel megváltoztatásával (stop feltétel) és új halmazok alkotásával new_candidates és new_not :
Lineáris a grafikonon szereplő kattintások számához képest. Tomita, Tanaka és Haruhisa 2006-ban kimutatták, hogy a legrosszabb eset algoritmusa O -ban fut ( 3n /3 ), ahol n a gráf csúcsainak száma.