#Úloha KLI: maximální klika grafu

##Vstupní data:

• G(V,E) = jednoduchý souvislý neorientovaný neohodnocený graf o n uzlech a m hranách
• n = přirozené číslo představující počet uzlů grafu G, n >= 5
• k = přirozené číslo řádu jednotek představující průměrný stupeň uzlu grafu G, n >= k >= 3
• r = kladné reálné číslo, 0 < r < 1

##Doporučení pro algoritmus generování G: Použijte generátor grafu s volbou typu grafu „-t AD“, který vygeneruje souvislý neorientovaný neohodnocený graf.

##Definice: Klika grafu G je jeho maximální úplný podgraf, t.j. takovy podgraf, ktery není obsažen v žádném větším podgrafu. Velikost kliky je počet jejich vrcholů.

##Úkol: Zjistit, zda graf G obsahuje kliku o velikosti alespoň (rovnou nebo větší) r * n a nalézt největší takovou kliku.

##Výstup algoritmu: Seznam uzlů tvořící kliku, popřípadě konstatování, že klika neexistuje.

##Sekvenční algoritmus: Sekvenční algoritmus typu BB-DFS s hloubkou stavového stromu omezenou na n. Cena řešení, která se maximalizuje, je velikost kliky vzhledem k zadané podmínce. Horní mez ceny řešení není známa. Algoritmus skončí, až prohledá celý stavový prostor.

##Meze:

• Dolní mez je 2, pokud graf obsahuje aspon 1 hranu.
• Horní mez není známá, ale dá se odhadnout takto: pokud G obsahuje kliku o velikosti x, pak musí obsahovat x vrcholů se stupněm větším nebo rovným x-1.

##Paralelní algoritmus: Paralelní algoritmus je typu PBB-DFS-V.