# Zkouska - Cepek - 21.1.2011

<{ForumPost(poster="Dr.Eddy", timestamp=2011-01-21 11:42:48)}>
1. Nakreslete graf a tabulku zpetne a vystupni funkce podle algoritmu Aho-Corasickova pro slova strom, stroj, postroj, trojka.  
2. Mate mrizku n * n, kde je m cernych bodu a ostatni bile. Navrhnete polynomialni algoritmus, ktery zjisti, jestli existuje prave m cest z cernych bodu do nejakych bilych na okraji mrizky, ktere jsou vrcholove disjunktni. Cerny bod na okraji mrizky potrebuje cestu delky 0. Muzete vyuzit jakykoli algoritmus z prednasky, ale nemusite ho popisovat.  
3. Izomorfismus podgrafu pro grafy G a H je prave tehdy, kdyz existuje v G nejaky indukovany podgraf izomorfni s H. Dokazte, ze tento problem je NP-uplny. Muzete vyuzit znalost NP-uplnych problemu z prednasky.
<{/ForumPost}>