Jméno a příjmení:
Příklad číslo: 1 2 3
Počet bodů:
Skupina D
Příklad 1. Určete obecné řešení rovnice
y - y = 5.
Řešení. Charakteristický polynom je x2
- x s kořeny 1, 0, obecné řešení zhomogenizované rovnice je tedy
c1 + c2ex
, kde c1, c2  R. Partikulární řešení hledáme metodou neurčitých koeficientů ve tvaru ax, a  R,
dostáváme a = -5. Obecné řešení dané rovnice je tvaru c1 + c2ex
- 5x. 2
Příklad 2. Určete počet cest mezi dvěma různými pevně vybranými vrcholy v grafu K7.
Řešení. Spočítáme cesty postupně podle jejich délky. Cesta délky jedna je jedna (hrana spojující dva
vybrané vrcholy). Cest délek dva je pět (vybíráme jeden z pěti zbylých vrcholů, přes který cesta půjde).
Cest délek tři je 5  4 (vybíráme v daném pořadí dva vrcholy, přes které cesta půjde), obdobně cest délky
čtyři je 5  4  3, cest délky pět je 5  4  3  2 a konečně cest délky šest je taktéž 5!. Delší cesty v K7 nejsou. 2
Příklad 3. Označme vrcholy v grafu K7 postupně čísly 1, 2, . . . 7 a každou hranu {i, j}, ohodnoťme číslem
[(i + j) mod 3] + 1. Kolik existuje různých maximálních koster v tomto grafu?
Řešení. Nejdražší hrany s ohodnocením tři tvoří v daném grafu podgraf obsahující všechny vrcholy a mající
dvě komponenty a to dvě kružnice délek tři a čtyři. Pouze z hran s tímto ohodnocením tedy maximální kostru
nesložíme. Bude v ní tedy minimálně jedna levnější hrana. Kostry s právě jednou hranou s ohodnocením 2
pak skutečně existují. Existuje šest hran s ohodnocením 2 propojující dvě zmíněné komponenty. Abychom
dostali kostru, musíme ještě vypustit po jedné hraně z každé z kružnic. To můžeme udělat 34 = 12 způsoby.
Celkem máme 72 různých maximálních koster. 2
1