Bron-Kerboshův algoritmus

Bron-Kerboshův algoritmus  je metoda větví a hranic pro nalezení všech klik (a také maximálních nezávislých množin vrcholů ) neorientovaného grafu . Vyvinutý nizozemskými matematiky Bronem a Kerboschem v roce 1973 je stále jedním z nejúčinnějších algoritmů pro vyhledávání klik.

Algoritmus

Algoritmus využívá skutečnosti, že každý klik v grafu je jeho úplným podgrafem inkluze-maximální . Počínaje jedním vrcholem (tvořícím úplný podgraf) se algoritmus v každém kroku snaží zvětšit již vytvořený úplný podgraf tím, že k němu přidá vrcholy ze sady kandidátů. Vysoká rychlost je zajištěna odříznutím při iteraci nad možnostmi, které nepovedou ke konstrukci kliky, k čemuž se používá přídavná sada, ve které jsou umístěny vrcholy, které již byly použity pro zvětšení kompletního podgrafu.

Algoritmus pracuje se třemi sadami vrcholů grafu:

  1. Množina compsub  je množina obsahující v každém kroku rekurze úplný podgraf pro daný krok. Buduje se rekurzivně.
  2. Množina kandidátů  je množina vrcholů, které mohou zvýšit compsub
  3. Not set  je množina vrcholů, které již byly použity k rozšíření compsub v předchozích krocích algoritmu.

Algoritmus je rekurzivní procedura aplikovaná na tyto tři množiny.

PROCEDURE extend ( kandidáti , ne ): POKUD kandidáti nejsou prázdní A NEobsahují vrchol PŘIPOJENÝ SE VŠEMI vrcholy od kandidátů , PROVEĎTE : 1 Vyberte vertex v z kandidátů a přidejte jej do compsub 2 Vytvořte new_candidates a new_not , odeberte z kandidátů a ne vertexy not CONNECTED to v 3 POKUD new_candidates a new_not jsou prázdné 4 TO compsub - klik 5 ELSE volání prodloužit rekurzivně ( noví_kandidáti , noví_ne ) 6 Odeberte v z compsub a kandidátů a vložte not

Variace

Nalezení maximálních (vzhledem k inkluzi) nezávislých množin vrcholů

Je snadné vidět, že problém kliky a problém nezávislých množin jsou v podstatě ekvivalentní: každý z nich je získán z druhého vytvořením doplňku grafu  - grafu, který obsahuje všechny vrcholy původního grafu, a v doplňku grafu vrcholy jsou spojeny hranou právě tehdy, pokud nebyly spojeny v původním grafu.

Proto lze Bron-Kerboschův algoritmus použít k nalezení maximálních množin vrcholů nezávislých na inkluzi vytvořením doplnění původního grafu nebo změnou podmínky v hlavní smyčce (stop podmínky) a vytvořením nových množin noví_kandidáti a noví_ne :

  1. Podmínka v hlavní smyčce: nesmí obsahovat žádný vrchol NENÍ PŘIPOJENA K ŽÁDNÉMU z vrcholů v množině kandidátů
  2. Chcete-li vytvořit new_candidates a new_not , musíte odstranit z kandidátů a nikoli vrcholy PŘIPOJENÉ k vybranému vrcholu.

Výpočetní složitost

Lineární s ohledem na počet kliknutí v grafu. Tomita, Tanaka a Haruhisa v roce 2006 ukázali, že nejhorší případ algoritmu běží v O ( 3n /3 ), kde n je počet vrcholů v grafu.

Viz také

Literatura