Bron-Kerbosh algoritme

Bron-Kerbosh-algoritmen  er en gren-og-bundet metode til at finde alle kliker (såvel som maksimale uafhængige sæt af hjørner ) af en urettet graf . Udviklet af de hollandske matematikere Bron og Kerbosch i 1973, er det stadig en af ​​de mest effektive klikesøgealgoritmer.

Algoritme

Algoritmen bruger det faktum, at hver klik i en graf er dens inklusionsmaksimale komplette undergraf . Startende fra et enkelt toppunkt (der danner en komplet undergraf), forsøger algoritmen ved hvert trin at øge den allerede konstruerede komplette undergraf ved at tilføje toppunkter fra sættet af kandidater til den. Høj hastighed sikres ved at skære fra, når der gentages over muligheder, der ikke vil føre til konstruktionen af ​​en klike, hvortil der bruges et ekstra sæt, hvor der placeres spidser, der allerede er blevet brugt til at øge hele subgrafen.

Algoritmen fungerer på tre sæt grafhjørnepunkter:

  1. Set compsub  er det sæt, der ved hvert trin af rekursionen indeholder den komplette subgraf for det givne trin. Det bygger rekursivt.
  2. Sættet af kandidater  er det sæt af hjørner, der kan øge compsub
  3. Det ikke - sæt  er det sæt af hjørner, der allerede er blevet brugt til at udvide compsub i de foregående trin i algoritmen.

Algoritmen er en rekursiv procedure anvendt på disse tre sæt.

PROCEDURE forlænge ( kandidater , ikke ) : MEDMINDRE kandidater er tomme OG IKKE indeholder et toppunkt FORBUNDET TIL ALLE knudepunkter fra kandidater , UDFØR : 1 Vælg toppunkt v fra kandidater og tilføj det til compsub 2 Form new_candidates og new_not , fjern fra kandidater og ikke toppunkter, der ikke er FORBUNDET til v 3 , HVIS new_candidates og new_not er tomme 4 TO compsub - klike 5 ELSE kalder forlænge rekursivt ( new_candidates , new_not ) 6 Fjern v fra compsub og kandidater , og indsæt ikke

Variationer

Find maksimale (med hensyn til inklusion) uafhængige sæt af hjørner

Det er let at se, at klikeproblemet og det uafhængige sætproblem i det væsentlige er ækvivalente: hver af dem opnås fra den anden ved at konstruere et grafkomplement  - en graf, der indeholder alle hjørnerne af den oprindelige graf, og i grafens komplement hjørner er forbundet med en kant, hvis og kun hvis de ikke var forbundet i den oprindelige graf.

Derfor kan Bron-Kerbosch-algoritmen bruges til at finde de maksimale inklusionsuafhængige sæt af toppunkter ved at konstruere en tilføjelse til den originale graf, eller ved at ændre betingelsen i hovedløkken (stopbetingelse) og danne nye sæt new_candidates og new_not :

  1. Betingelse i hovedsløjfen: ikke må ikke indeholde nogen top, IKKE FORBUNDET TIL NOGEN af toppunkterne i sættet af kandidater
  2. For at danne nye_kandidater og ny_ikke skal du fjerne fra kandidater og ikke de knudepunkter, der er FORBUNDET til det valgte vertex.

Beregningsmæssig kompleksitet

Lineær i forhold til antallet af klik i grafen. Tomita, Tanaka og Haruhisa i 2006 viste, at worst-case-algoritmen kører i O ( 3n /3 ), hvor n er antallet af hjørner i grafen.

Se også

Litteratur