Přečtěte si Lekci 9 pro potřebné pojmy...

Na jednoduchém neorientovaném grafu honí policajti jednoho zloděje. Zloděj je na jednu stranu nekonečně rychlý, nekonečně chytrý a ví dopředu, co chtějí policajti dělat (čte myšlenky). Na druhou stranu se ale zloděj může pohybovat jen z vrcholu do vrcholu po hranách grafu, za předpokladu, že žádný z průchozích vrcholů není obsazený policajtem. Policajti se dole v grafu bojí pohybovat, a proto se pouze přemísťují vrtulníkem a občas do vybraného vrcholu jednoho policajta spustí. Zloděj je tedy policajty chycen v okamžiku, kdy na jeho vrchol je spuštěn policajt a (za samozřejmého předpokladu, že se zloděj snaží uniknou, jak to jde) všechny sousední vrcholy jsou také obsazené policajty. Cílem zloděje je chycení unikat.

Ve "hře A" jsou následující upřesňující pravidla: policajti zloděje z vrtulníku vidí a jednou spuštěný policajt už musí ve svém vrcholu zůstat do konce hry. Ve "hře B" je upřesnění pravidel trochu jiné: policajti zloděje NEvidí (dokud ho ve vrcholu nechytí), ale zase mohou dříve spuštěného policajta kdykoliv vytáhnout zpět do vrtulníku.

a) Udejte příklad grafu, pro který ve hře B stačí 2 policajti k chycení zloděje, ale ve hře A zloděje (na tomtéž grafu) nechytí ani 10 policajtů. Dokažte.
Každé odevzdané řešení musí tento bod obsahovat, avšak jen tato lehká otázka na bonus nestačí - pokračujte dále.

b) Pro každé k>1 udejte příklad grafu, ve kterém je nejmenší počet policajtů potřebný k chycení zloděje ve hře A i ve hře B stejný, roven k.

c) Nakonec dokažte, že pokud na daném grafu k policajtů vždy chytí zloděje ve hře A, tak stejných k policajtů na stejném grafu stačí k chycení zloděje ve hře B.

...d) Pokud ještě máte sílu dále řešit, podívejte se, co všechno se změní, pokud graf bude orientovaný (a zloděj bude muset respektovat směr šipek).