Matematika III, 10. cvičení
Pojmy k zopakování
• Otevřený a uzavřený tah
• Eulerovský graf
• Probiem čínskeho pošt'aka
• Hamiltonovska kružnice
• N-rozmerna křýchle a důkaz matematickou indukcí
Příklad 195. Rozhodněte, zda lze následující grafy nakreslit jedním (tevrenym) tahem. Pokud ano, grafy tak nakreslete.
Výsledek. Všechny ano.
Příklad 196. Rozhodnete, které grafy lze nakreslit jedním otevřeným či uzavřeným tahem.
Výsledek. První ne, druhý a tretí uzavreným. Příklad 197. Určete, pro ktera n je Kn eulerovský. Výsledek. Pro všechna lichý n a take pro 2.
Příklad 198. Kolik nejméne hran musíte pridat k tomuto grafu, aby se dal nakreslit jedním uzavreným tahem?
33
Výsledek. 3 (Nezapomeňte zdůvodnit, že nelze pro menší počet.) Příklad 199. Určete, kolika nejméně tahy můžeme nakreslit tento graf.
Výsledek. 2
Příklad 200. Určete, kolika nejméně tahy můžeme nakreslit tento graf.
Výsledek. 2
Příklad 201. Je možné projét dům, jehož půdorys vidíte na obmzku tak, abychom každými dvečmi prošli pravě jednou?
Příklad 202. Pošt'ék ma projit všechny hrany nasledujécého grafu. Určete, kudy ma jít, aby se vrátil do stejného místa, ze kterého vysel a aby pritom ušel co nejmensí vzdalenost.
34
Příklad 203. Pošťák má projit všechny hrany následujícího grafu. Určete, kudy má jít, aby se vrátil do stejného místa, ze kterého vyšel a aby pritom ušel co nejmenSí vzdálenost.
(1-•---1	2	K-1 1 \ 3 \
•-•-=-<	2 /	\-1
Příklad 204. Uveďte príklad dvou grafu se stejným skórem, jednoho, která bude hamiltonovská, druhého, kterí hamiltonovskí nebude.
Vísledek. Například (2,2, 2, 3,3).
Příklad 205. DokaZte, Ze dane grafy nejsou hamiltonovske.
Příklad 206. Naleznete hamiltonovskou kruZnici v nasledujícím grafu.
Příklad 207. Naleznete hamiltonovskou kruZnici v nasledujícím grafu.
Příklad 208. Určete, kolik existuje navzíjem neizomorfních hamiltonovskych grafu na 4 uzlech. Vísledek. 3
Příklad 209. Uveďte príklad dvou neizomorfních hamiltonovskych grafu na 5 uzlech, kašdy s 6 hranami.
35
Výsledek. Neexistují.
Příklad 210. Uveďte přiklad dvou neizomorfních hamiltonovských grafu na 5 uzlech, každý s nejvýše 6 hranami.
Výsledek. Kružnice na peti vrcholech a kružnice na peti vrcholech, do které přidáme jednu hranu. Příklad 211. Uveďte přiklad grafu, který
1. je eulerovský i hamiltonovský
2. neni eulerovský, ale je hamiltonovský
3. je eulerovský, ale neni hamiltonovský
4. neni eulerovský ani hamiltonovský
Příklad 212. Necht' Km,n je uuplnýj bipartitní graf, který je hamiltonovský. Dokažte, že m = n.
Příklad 213. Dokažte, že každý hamiltonovský graf na n vrcholech, kde n > 3, je vrcholově 2-souvislý.
Příklad 214. Pro každé liché prvočíslo p dokažte, že Kp obsahuje 2-1 hranove disjunktních hamiltonovskýých kruznic.
Příklad 215. Dokažte, že n-rozmerný krýchle je hamiltonovský graf pro všechna n G N. Napoveda: Matematicka indukce.
Příklad 216. Dokažte, že uuplnýý tripartitný, graf (definice v prvním cvicení) Kn^2n;in je hamiltonovský pro každe n G N.
36