Matematika III 26. ledna 2011
AJ
(UČO: )
Semestr	1.	2.	3.	4.	E
					
Na každý příklad získáte nezáporný počet bodů. Potřebné minimum (včetně semestru) je 20 bodů.
Na práci máte 90 minut.
1. (5 bodů) Určete maxima a minima funkce z(x,y) = sin x + cos y + cos(x — y) na množině {[x, y] G IR2; 0 < x, y < |}. Hodnoty funkce v bodech nabývání extrémů vyčíslete a zdůvodněte, že se skutečně jedná o absolutní extrém (včetně vyšetření funkce na hranici).
2. (6 bodů) Nechť M značí definiční obor funkce
(a) Zobrazte M v rovině.
(b) Do obrázku M načrtněte vrstevnice funkce g(x,y) = 2x + y a výpočtem určete její největší a nejmenší hodnotu na množině M (tj. zejména určete body, v nichž dojde k dotyku vrstevnice na úrovni c s hranicí množiny M pro nejmenší, resp. největší c).
(c) Pomocí integrálu dvou proměnných vypočtěte obsah množiny M. 3. (5 bodů)
(a) Uveďte Floyd-Warshallův algoritmus pro nalezení nejkratších cest mezi všemi dvojicemi vrcholů a zformulujte vztah, na němž je myšlenka algoritmu založena.
(b) Tento algoritmus použijte na orientovaný graf na obrázku. Jednotlivé mezivýpočty zapisujte do matic. Udržujte zároveň všechny potřebné údaje ke konstrukci nejkratších cest a určete pomocí nich nejkratší cestu z 3 do 1.
Obr. 1: Obrázek k příkladu na hledání minimálních cest.
4. (4 body) Stromy:
(a) Definujte pojmy strom a list a dokažte, že každý strom s alespoň dvěma vrcholy obsahuje alespoň 2 listy.
(b) Udejte příklad (nebo zdůvodněte, že neexistuje) grafu, který má právě 2011 koster (a neobsahuje kružnici C^on)-
(c) Uveďte příklad (nebo zdůvodněte, že neexistuje) stromu na alespoň 3 vrcholech, který není sám cestou a v němž existuje hamiltonovská cesta (tedy cesta procházející každým vrcholem právě jednou).
(d) Uveďte příklad (nebo zdůvodněte, že neexistuje) ohodnoceného grafu, který není stromem a má jednoznačně určenou minimální kostru, přestože ohodnocení není prostá funkce.
Matematika III 26. ledna 2011
BJ
(UČO: )
Semestr	1.	2.	3.	4.	E
					
Na každý příklad získáte nezáporný počet bodů. Potřebné minimum (včetně semestru) je 20 bodů.
Na práci máte 90 minut.
1. (5 bodů) Určete maxima a minima funkce z(x,y) = sin:r-siní/-sin(:r + í/) na množině G IR2; 0 < x,y < 7r}. Hodnoty funkce v bodech nabývání extrémů vyčíslete a zdůvodněte, že se skutečně jedná o absolutní extrémy (včetně vyšetření funkce na hranici).
2. (6 bodů) Nechť M značí definiční obor funkce
f(x, y) = \Jlx — x2 + \/ y — y1 + \/y2 — max{0,:r — 1}.
(a) Zobrazte M v rovině.
(b) Do obrázku M načrtněte vrstevnice funkce g(x,y) = x2 — Ax + y2 a výpočtem určete její největší a nejmenší hodnotu na množině M (tj. zejména určete body, v nichž dojde k dotyku vrstevnice na úrovni c s hranicí množiny M pro nejmenší, resp. největší c).
(c) Vypočtěte integrál j jM x dx dy.
3. (5 bodů)
(a) Uveďte algoritmus upraveného násobení matic pro nalezení nejkratších cest mezi všemi dvojicemi vrcholů a zformulujte vztah, na němž je myšlenka algoritmu založena.
(b) Tento algoritmus použijte na orientovaný graf na obrázku. Jednotlivé mezivýpočty zapisujte do matic. Udržujte zároveň všechny potřebné údaje ke konstrukci nejkratších cest a určete pomocí nich nejkratší cestu ze 4 do 3.
4. (4 body) Hamiltonovské grafy:
(a) Uveďte nějakou podmínku postačující k tomu, aby graf byl hamiltonovský, kterou splňuje nekonečně mnoho po dvou neizomorfních grafů.
(b) Uveďte nějakou nutnou podmínku toho, aby graf byl hamiltonovský, kterou splňuje nekonečně mnoho po dvou neizomorfních grafů.
(c) Uveďte příklad (nebo zdůvodněte, že neexistuje) nerovinného hamiltonovského grafu, který je eulerovský.
(d) Uveďte příklad (nebo zdůvodněte, že neexistuje) hamiltonovského grafu, jehož uzávěrem není úplný graf.
Obr. 1: Obrázek k příkladu na hledání minimálních cest.