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.
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 [latex]\cap[/latex] co-CO.
Zadefinujte LexBFS a ukažte jeho použití.
Ukažte nějakou [latex]\chi[/latex]-bounded třídu průnikových grafů.
Ukažte nějakou třídu průnikových grafů, která není [latex]\chi[/latex]-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.