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

<{ForumPost(poster="Erim", timestamp=2016-08-01 23:48:38)}>
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.
<{/ForumPost}>