Matematika III, 11. cvičení
Pojmy k zopakování
• Stromy, pěstěné stromy
• Kod pěstěného stromu
• Kostra grafu, minimálni kostra
• Kruskaluv algoritmus, Jarnikův-Primův algoritmus, Boruvkuv algoritmus
• N-rozmérni krychle a dukaz matematickou indukci Příklad 217. Určete všechny stromy
1. na čtyřech vrcholech.
2. na Šesti vrcholech.
Výsledek. V prvnim pripadé jsou 2, ve druhém jich je 6.
Příklad 218. Dokažte, ze graf G je strom prave tehdy, kdyz je souvislý a odebrýným libovolné hrany dostaneme nesouvislý graf.
Příklad 219. Dokazte, že graf G je strom préve tehdy, když libovolné dva vrcholy můžeme spojit praýve jednou cestou.
Příklad 220. Urcete všechny éplne bipartitné grafy, které jsou stromy. Výsledek. K\,n
Příklad 221. Uveďte príklad grafu se dvěma kružnicemi, ze kterého lze odebréném jedné hrany dostat strom.
Vésledek. Nééxistujé.
Příklad 222. Necht strom G obsahuje alespoň jeden vrchol stupne k. Dokazte, že potom G obsahuje alespoň k vrcholů stupně 1.
Příklad 223. Jaky je maximalné pocet vrcholů binarného stromu o h hladinach? A jaky je maximélnépocet vrcholů k-arného stromu o h hladinach?
Vésledek. 2h - 1, ^
Příklad 224. Dokazte, ze kažďé strom na n> 1 vrcholech je bipartitné graf.
Příklad 225. Dokazte, ze kazdé alkan je strom.
Napoveda: Alkany jsou tvaru CnH2n+2, dale vyuzijte Eulerův vzorec.
Příklad 226. Nakreslete pěstěné strom s nasledujécém kédem 00001011010110100010101111.
Příklad 227. Rozhodnete, zda existuji stromy s nasledujécémi kédy. V prépade, ze ano, potom danéy strom nakreslete.
1. 00011001111001
2. 000010100111010110010111
37
Příklad 228. Určete kódy následujících pěstěných stromů
Příklad 229. Určete kód tohoto pěstěného stromu
Výsledek. 00000010111001001111100100010110011111 Příklad 230. Určete kod tohoto pěstěného stromu
Příklad 231. Určete počet koster grafu K4 a K5. Výsledek. 16,125
Příklad 232. Určete počet koster grafu C2010. Výsledek. 2010
38
Příklad 233. Určete počet koster grafu
Výsledek. 25
Příklad 234. Určete počet koster grafu
Výsledek. 29
Příklad 235. Kolik nejméně vrcholu musí mít graf, aby obsahoval dve hranově disjunktní kostry? Výsledek. 4
Příklad 236. Uveďte príklad grafu, ktery ma pravě 5 koster. Výsledek. C5
Příklad 237. Uved'te príklad grafu, ktery mí pravě 2010 koster a neobsahuje kružnici C2010. Napoveda: Rozložte číslo 2010 na součin dvou čísel.
Příklad 238. Uved'te príklad grafu, ktery mí príve 2011 koster a neobsahuje kručnici C2011. Nípoveda: 2011 je prvočíslo, hledejte nejake česení rovnice m • n + m + n = 2011.
Příklad 239. Najdete ohodnocení graf, kterí ma jednoznačně určenou minimalní kostru, ale jeho hrany nemajíí vzíajemnče rluznía ohodnoceníí.
Příklad 240. Pomocí Kruskalova algoritmu najdete minimalní kostry nasledujících grafu a určcete, jestli jsou jednoznačcnče určceníe.
39
Příklad 241. Pomocí Jarníkova-Prímova algoritmu najděte minimální kostry následujících grafů.
1__, 7
Příklad 242. Pomocí Borůvková algoritmu najděte minimální kostry následujících grafů.
Příklad 243. Najdete mínímalní kostry nasledujícího grafu
1. Kruskalovím algoritmem
2. Jarníkovým-Prímovým algoritmem
3. Borůvkovým algoritmem
Příklad 244. Najdete minimalní kostry nasledujícího grafu
1. Kruskalovím algoritmem
2. Jarníkovým-Primovým algoritmem
3. Borůuvkovíym algoritmem
13 i.    4 «	i    10 t	.     6 t
17 «^-«		^-t--«
11
40
Příklad 245. 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čite nepatrí do minimainí koštry.
2. Nejlevnejší hrana grafu G urcite patrí do minimainí koštry.
3. Pokud je nejlevnejší hrana grafu G urcena jednoznacne (ostatní hrany jšou dražší), tak muší bít obsažena v každe minimalní koštre.
4. Pokud nejakí cykluš v grafu G obšahuje pouze jednu nejlevnejší hranu, tak tato hrana patrí do minimalní koštry.
5. Nejkratší cešta mezi dvema vrcholy urcite patrí do minimalní koštry.
Příklad 246. Necht, G je neorientovaný ohodnocení graf, H C G jeho podgraf a T minimílní koštra G. Ukažte, ze T n H je obšazeno v nejake minimílní koštre H.
41