Fórum studentů MFF UK

Na termínu jsme byli čtyři, každý dostal dvě otázky a čas si je vypracovat. Když byl někdo připraven, zavolal si zkoušejícího, který po přečtení případně položil doplňující otázky. Zkouška trvala zhruba jednu hodinu.

Nalezněte největší kliku v PC grafech.
Dokažte PER = CO co-CO.

Zadefinujte LexBFS a ukažte jeho použití.
Ukažte nějakou -bounded třídu průnikových grafů.

Ukažte nějakou třídu průnikových grafů, která není -bounded.
Dokažte, že rozpoznávání STRING grafů je rozhodnutelný problém.

Popište PQ-stromy a k čemu se používají.
Nalezněte největší nezávislou množinu v CO grafech.