[NDMI037] Geometrické reprezentace grafů I (1. 8. 2016)

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 $\cap$ co-CO.

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

Ukažte nějakou třídu průnikových grafů, která není $\chi$-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.