Matematika III, 10. cvičení
Pojmy k zopakovaní
• Otevřený a uzavřený tah
• Eulerovský graf
• Problém čínského pošťáka
• Hamiltonovská kružnice
• ./V-rozměrná krychle a důkaz matematickou indukcí
Příklad 194. Rozhodněte, zda lze následující grafy nakreslit jedním (otevřeným) tahem. Pokud ano, grafy tak nakreslete.
Výsledek. Všechny ano.
Příklad 195. Rozhodněte, které grafy lze nakreslit jedním otevřeným či uzavřeným tahem.
Výsledek. První ne, druhý uzavřeným a třetí otevřeným. Příklad 196. Určete, pro která n je Kn eulerovský. Výsledek. Pro všechna lichá n a také pro 2.
Příklad 197. Kolik nejméně hran musíte přidat k tomuto grafu, aby se dal nakreslit jedním uzavřeným tahem?
33
Výsledek. 3 (Nezapomeňte zdůvodnit, že nelze pro menší počet.) Příklad 198. Určete, kolika nejméně tahy můžeme nakreslit tento graf.
Výsledek. 2
Příklad 199. Určete, kolika nejméně tahy můžeme nakreslit tento graf.
Výsledek. 2
Příklad 200. Je možné projít dům, jehož půdorys vidíte na obrázku tak, abychom každými dveřmi prošli právě jednou?
1 < LA A		A A     A 1	
	c		
Příklad 201. Pošťák má projít 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 přitom ušel co nejmenší vzdálenost.
• 2   •  1 1	, 2	2
\ im < 4	2 2 f	i \
i í-1 •-;-•-s-*	2 / ( i	7 1-ť-•
34
Příklad 202. Uveďte příklad dvou grafů 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 203. Dokažte, že dané grafy nejsou hamiltonovské.
Příklad 204. Naleznete hamiltonovskou kružnici v následujícím grafu.
Příklad 205. Nalezněte hamiltonovskou kružnici v následujícím grafu.
Příklad 206. Určete, kolik existuje navzájem neizomorfních hamiltonovských grafů na 4 uzlech. Výsledek. 3
Příklad 207. Uveďte příklad dvou neizomorfních hamiltonovských grafů na 5 uzlech, každý s 6 hranami.
Výsledek. Neexistují.
Příklad 208. Uveďte příklad dvou neizomorfních hamiltonovských grafů na 5 uzlech, každý s nejvýše 6 hranami.
Výsledek. Kružnice na pěti vrcholech a kružnice na pěti vrcholech, do které přidáme jednu hranu. Příklad 209. Uveďte příklad grafu, který
1. je eulerovský i hamiltonovský
2. není eulerovský, ale je hamiltonovský
3. je eulerovský, ale není hamiltonovský
35
4- není eulerovský ani hamiltonovský
Příklad 210. Nechť Km^n je úplný bipartitní graf, který je hamiltonovský. Dokažte, že m = n.
Příklad 211. Dokažte, že každý hamiltonovský graf na n vrcholech, kde n > 3, je vrcholově 2-souvislý.
Příklad 212. Pro každé liché prvočíslo p dokažte, že Kp obsahuje hranově disjunktních hamiltonovských kružnic.
Příklad 213. Dokažte, že n-rozměrná krychle je hamiltonovský graf pro všechna íiěN. Nápověda: Matematická indukce.
Příklad 214. Dokažte, že úplný tripartitní graf (definice v prvním cvičení) Kn-2n:in Je hamiltonovský pro každé n G N.
36