(DeTtwcvieení
M<B101 -jaro 2012 19. (istopadu 2012
Příklad 1 (Úvodní). Dokažte, že nelze projít koněm přes všechna políčka šachovnice 3x3.
Příklad 2. Rozhodněte, zda jsou následující grafy eulerovské. Pokud nejsou, doplňte je přidáním hran na eulerovské (je-li to možné). Nalezněte eulerovské tahy.
Příklad 3. Rozhodněte, zda je daný graf eulerovský, případně nalezněte eulerovský tah.
Příklad 4. Máme dán graf _řr3)3 bez jedné hrany
1. Je možno graf K33—e nakreslit jedním uzavřeným tahem? Nakreslete nebo zdůvodněte, proč to není možné.
2. Je možno graf K33—e nakreslit jedním otevřeným tahem? Nakreslete nebo zdůvodněte, proč to není možné.
1
3. Je možno graf K33—e nakreslit dvěma otevřenými tahy? Nakreslete nebo zdůvodněte, proč to není možné.
4. Kolik nejméně hran je třeba přidat do grafu _řr3)3 — e, aby jej bylo možno nakreslit jedním otevřeným tahem?
5. Kolik nejméně hran je třeba přidat do grafu        — e, aby jej bylo možno nakreslit jedním uzavřeným tahem?
Příklad 5. Najděte příklad souvislého grafu, který má dva vrcholy lichého stupně a všechny ostatní vrcholy sudého stupně a do kterého
1. stačí přidat jedinou hranu tak, aby byl eulerovský.
2. není možné přidat jedinou hranu tak, aby byl eulerovský.
Příklad 6. Ukažte, že souvislý graf s 2t vrcholy lichého stupně je možno nakreslit t otevřenými eulerovskými tahy.
Příklad 7. Pro každé t G N najděte příklad souvislého grafu, který
1. není souvislý, obsahuje 2t vrcholů lichého stupně a je možno jej nakreslit t otevřenými tahy.
2. je souvislý, obsahuje 2t vrcholů lichého stupně a je možno jej nakreslit t otevřenými tahy, ale není možné přidáním t hran získat eulerovský graf.
3. je souvislý, obsahuje 2t vrcholů lichého stupně a je možno jej nakreslit t otevřenými tahy, a přidáním t hran je možné získat eulerovský graf.
Příklad 8. Nalezněte hamiltonovskou kružnici v následujícím grafu
Příklad 9. Rozhodněte, zda je Petersenův graf eulerovský a zda v něm existuje hamilto-novská cesta.
2
Příklad 10. Může jezdec projít šachovnici (o 64 polích) tak, aby každým polem prošel právě jednou a posledním tahem se vrátil na výchozí pole?
Věta 1 (Dirac). Nechi G = [U, H] je konečný graf, \U\ = n > 3 a st(x) > n — 2 pro každý uzel x G U. Pak je G hamiltonovský.
Věta 2 (Ore). Buď G = [U, H] konečný graf, \U\ > 3. Nechť pro každé dva uzly x,y G U, které nejsou sousední, platí st(x) + st{y) > \U\. Pak je graf [U, H} hamiltonovský.
Příklad 11. Sestrojte příklad hamiltonovského grafu, který splňuje předpoklady Oreho věty, ale nesplňuje předpoklady věty Diracovy.
Příklad 12. Problém čínského pošťáka v hranově ohodnoceném neorientovaném grafu je problémem nalezení nejkratšího uzavřeného sledu, který obsahuje každou hranu v grafu. Nalezněte řešení tohoto problému pro graf na obrázku.
3