Matematika III, 11. cvičení
Pojmy k zopakování
• Stromy, pěstěné stromy
• Kód pěstěného stromu
• Kostra grafu, minimálni kostra
• Kruskaluv algoritmus, Jarníkův-Primův algoritmus, Borůvkův algoritmus
• ./V-rozměrná krychle a důkaz matematickou indukcí Příklad 215. Určete všechny stromy
1. na čtyřech vrcholech.
2. na šesti vrcholech.
Výsledek. V prvním případě jsou 2, ve druhém jich je 6.
Příklad 216. Dokažte, že graf G je strom právě tehdy, když je souvislý a odebráním libovolné hrany dostaneme nesouvislý graf.
Příklad 217. Dokažte, že graf G je strom právě tehdy, když libovolné dva vrcholy můžeme spojit právě jednou cestou.
Příklad 218. Určete všechny úplné bipartitní grafy, které jsou stromy. Výsledek. K\^n
Příklad 219. Uveďte příklad grafu se dvěma kružnicemi, ze kterého lze odebráním jedné hrany dostat strom.
Výsledek. Neexistuje.
Příklad 220. Nechí strom G obsahuje alespoň jeden vrchol stupně k. Dokažte, že potom G obsahuje alespoň k vrcholů stupně 1.
Příklad 221. Jaký je maximální počet vrcholů binárního stromu o h hladinách? A jaký je maximální počet vrcholů k-árního stromu o h hladinách?
Výsledek. 2h - 1, ^
Příklad 222. Dokažte, že každý strom na n > 1 vrcholech je bipartitní graf.
Příklad 223. Dokažte, že každý alkan je strom.
Nápověda: Alkany jsou tvaru CnH2n+2, dále využijte Eulerův vzorec.
Příklad 224. Nakreslete pěstěný strom s následujícím kódem 00001011010110100010101111.
Příklad 225. Rozhodněte, zda existují stromy s následujícími kódy. V případě, že ano, potom daný strom nakreslete.
1. 00011001111001
2. 000010100111010110010111
37
Příklad 226. Určete kódy následujících pěstěných stromů
Příklad 227. Určete kód tohoto pěstěného stromu
Výsledek. 00000010111001001111100100010110011111 Příklad 228. Určete kód tohoto pěstěného stromu
Příklad 229. Určete počet koster grafu K4 a K5. Výsledek. 16,125
Příklad 230. Určete počet koster grafu C2oio-Výsledek. 2010
38
Příklad 231. Určete počet koster grafu
Výsledek. 121
Příklad 232. Určete počet koster grafu
Výsledek. 29
Příklad 233. Kolik nejméně vrcholů musí mít graf, aby obsahoval dvě hranově disjunktní kostry? Výsledek. 4
Příklad 234. Uveďte příklad grafu, který má právě 5 koster. Výsledek. C5
Příklad 235. Uveďte příklad grafu, který má právě 2010 koster a neobsahuje kružnici C^oio-Nápověda: Rozložte číslo 2010 na součin dvou čísel.
Příklad 236. Uveďte příklad grafu, který má právě 2011 koster a neobsahuje kružnici C^on-Nápověda: 2011 je prvočíslo, hledejte nějaké řešení rovnice m ■ n + m + n = 2011.
Příklad 237. Najděte ohodnocený graf, který má jednoznačně určenou minimální kostru, ale jeho hrany nemají vzájemně různá ohodnocení.
Příklad 238. Pomocí Kruskalova algoritmu najděte minimální kostry následujících grafů a určete, jestli jsou jednoznačně určené.
7
4
6
7
12
39
Příklad 239. Pomocí Jarníkova-Primova algoritmu najděte minimální kostry následujících grafů.
7__, 7
2/	\
	
/   1 \	2 \
14
	2	
		
9^	> -~	
	l/	
r 6		
	Y 3	
ip^		
	9	
Příklad 240. Pomocí Borůvková algoritmu najděte minimální kostry následujících grafů.
7_. 7
4,
11
2/	
	\
7/ \	
/ \	
/    1 \	2 \
14
	2	3^
	► i	
r 6	/ 3	
11^	9	
Příklad 241. Najděte minimální kostry následujícího grafu
1. Kruskalovým algoritmem
2. Jarníkovým-Primovým algoritmem
3. Borůvkovým algoritmem
	3 /	X
6	1	7
10\	l 5	
•—		e—--11
	Y 2	
	2 ,	,   4 N,
	\5	\7
•—	1 \	t     4 \
Příklad 242. Najděte minimální kostry následujícího grafu
1. Kruskalovým algoritmem
2. Jarníkovým algoritmem
3. Borůvkovým algoritmem
16
•-:-i 13 n    4 i	> i 5 ,    10 t	i-ip ►     6 .
17 it—Í-,	3 ■     75 ■	*—4--
40
Příklad 243. U každého tvrzení rozhodněte, zda platí. Své tvrzení dokažte (případně uveďte protipříklad)
1. Pokud má ohodnocený graf na n vrcholech více než n — 1 hran, tak nejdražší hrana grafu urěitě nepatří do minimální kostry.
2. Nejlevnější hrana grafu G urěitě patří do minimální kostry.
3. Pokud je nejlevnější hrana grafu G urěena jednoznačně (ostatní hrany jsou dražší), tak musí být obsažena v každé minimální kostře.
4- Pokud nějaký cyklus v grafu G obsahuje pouze jednu nejlevnější hranu, tak tato hrana patří do minimální kostry.
5. Nejkratší cesta mezi dvěma vrcholy urěitě patří do minimální kostry.
Příklad 244. Nechi G je neorientovaný ohodnocený graf, H C G jeho podgraf a T minimální kostra G. Ukažte, že T D H je obsaženo v nějaké minimální kostře H.
41