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

Erim
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 18. 12. 2014 12:28
Typ studia: Informatika Bc.

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

Příspěvek od Erim »

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.
Odpovědět

Zpět na „I1 Ostatní Teoretická informatika“