Matematika III A
30. ledna 2008 (UČO: )
Hodnocení:
Bonus Teorie 1. 2. 3. 4.
Na každý příklad získáte nezáporný počet bodů.
Potřebné minimum (včetně bonusu) je 15 bodů.
Na práci máte 90 minut.
Teorie: (6krát 1 bod: tj. správně 1 bod, chybně -1 bod, bez odpovědi 0)
Odpovězte (škrtnutím nehodícího se ano nebo ne na patřičném řádku), zda jsou pravdivá následující
tvrzení (čtěte velmi pozorně!):
(a) ano -- ne Je-li hessián funkce f v daném stacionárním bodě indefinitní, nemůže být tento
bod lokálním extrémem f.
(b) ano -- ne Dva grafy jsou izomorfní, právě když se jejich skóre liší pouze permutací.
(c) ano -- ne Graf K4,4 není rovinný.
(d) ano -- ne Každý tah v grafu je zároveň cestou.
(e) ano -- ne Plyne z existence derivací v libovolném směru funkce f v bodě a i spojitost f
v bodě a?
(f) ano -- ne Množina {[x, y]  E2; x2
+ y2
 1} je uzavřená.
Příklady:
1. (6 bodů) S využitím integrálního počtu určete souřadnice těžiště tělesa určeného podmínkami
0  x  1, 0  y  1, 0  z  1, jestliže hustota tohoto tělesa v bodě [x, y, z] je dána vzorcem
(x, y, z) = x + y + z.
(Tip: výpočtu některých integrálů je možné se pomocí vhodných úvah vyhnout.)
2. (6 bodů) Uvedťe nějaký algoritmus pro nalezení nejkratších cest mezi všemi dvojicemi vrcholů.
Tento algoritmus použijte na orientovaný graf na obrázku 1. Jednotlivé kroky výpočtu
vhodným způsobem zapisujte. Uvedťe, jak se v průběhu výpočtu detekují cykly záporné délky
a odhadněte časovou složitost algoritmu.
3. (6 bodů) Nechť je funkce y = y(x) dána v okolí bodu [1, 1] implicitně rovnicí y3
-2xy+x2
= 0.
Určete Taylorův polynom 2. stupně této funkce v bodě x0 = 1.
4. (6 bodů) Řešte rekurenci
an+1 = an + n(-1)n
(pro n  1), a0 = 1, a1 = 1.
1
2 3
4
54
6
3
0
6
4
-5
2
2
-2
Obr. 1: Obrázek k příkladu na hledání minimálních cest.
Návod k řešení:
Teorie: a) ANO - indefinitnost znamená, že v některém směru se příslušná směrová derivace
zvýší (bude tedy kladná) a v některém sníží (a bude tedy záporná), proto daný stacionární bod
nemůže být lokálním extrémem; b) NE - mnoho příkladů, např. (2,2,2,2,2,2) odpovídá jak C6, tak
C3  C3; c) ANO - jeho podgrafem je K3,3; d) NE - na cestě se nesmějí opakovat ani vrcholy, na
tahu mohou; e) NE - spojitost plyne až z existence diferenciálu (př. viz přednáška); f) ANO
1.
2. Floyd.
3.
4.
Matematika III B
30. ledna 2008 (UČO: )
Hodnocení:
Bonus Teorie 1. 2. 3. 4.
Na každý příklad získáte nezáporný počet bodů.
Potřebné minimum (včetně bonusu) je 15 bodů.
Na práci máte 90 minut.
Teorie: (6krát 1 bod: tj. správně 1 bod, chybně -1 bod, bez odpovědi 0)
Odpovězte (škrtnutím nehodícího se ano nebo ne na patřičném řádku), zda jsou pravdivá následující
tvrzení (čtěte velmi pozorně!):
(a) ano -- ne Plyne z existence derivací v libovolném směru funkce f v bodě a i existence všech
parciálních derivací f v bodě a?
(b) ano -- ne Neexistuje žádný graf, jehož skóre je (1, 1, 1, 1, 1, 1, 1).
(c) ano -- ne Existuje-li limita funkce f : En  R v daném bodě, pak je f v tomto bodě
spojitá.
(d) ano -- ne V dané síti je velikost každého řezu větší než kapacita libovolného toku.
(e) ano -- ne Každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5.
(f) ano -- ne Je-li v grafu G daný vrchol artikulací, pak je nutně některá hrana z něj vycházející
mostem.
1. (8 bodů) S využitím integrálního počtu určete souřadnice těžiště obecného lichoběžníku s vrcholy
o souřadnicích A = [0, 0], B = [b, 0], C = [c, v], D = [d, v]. Předpokládejte přitom, že
0 < d < c < b a 0 < v.
(Pozn: pokud znáte vzorec pro obsah lichoběžníku, nemusíte obsah počítat pomocí integrace,
ale můžete jej spočítat podle tohoto vzorce.)
2. (6 bodů) Najděte s využitím Tarjanova algoritmu1
silně souvislé komponenty v grafu G =
(V, E), kde V = {1, . . ., 11} a množina hran E je dána výčtem
(1, 5) (3, 9) (5, 9) (7, 2) (9, 8) (10, 6)
(2, 1) (4, 6) (5, 10) (7, 11) (9, 10) (11, 8)
(2, 7) (5, 4) (6, 5) (8, 11) (10, 3)
Popište stručně použitý algoritmus. Jednotlivé kroky vhodně zapisujte, nakreslete obrázek.
3. (4 body) Uvedťe Eulerovu formuli pro souvislé rovinné grafy a s jejím využitím dokažte
omezení |E|  3|V | - 6 pro počet hran v závislosti na počtu vrcholů v souvislém rovinném
grafu. Otočte list!
1
Algoritmus probíraný na demonstračním cvičení
4. (6 bodů) Pomocí metody Lagrangeových multiplikátorů nalezněte body, v nichž má funkce
f(x, y) = x2
+ y2
na množině M = {[x, y]  E2; x
a
+ y
b
= 1} vázaný extrém (a, b jsou
libovolné nenulové reálné parametry). Určete funkční hodnotu v těchto bodech a pomocí
hessiánu rozhodněte, jde-li o maximum nebo minimum. Popište rovněž význam výsledku
z geometrického hlediska.
Návod k řešení:
Teorie: a) ANO - parciální derivace jsou spec. případem směrových; b) ANO - součet stupňů
musí být sudý; c) NE - limita musí být rovna funkční hodnotě; d) NE - nerovnost je neostrá; e)
ANO - dokáže se snadno z nerovnosti |E|  3|V | - 6; f) NE.
1.
2. Tarjanův algoritmus: (Podrobněji viz studijní materiály k demonstračním cvičení, kde je k
dispozici i animovaná ukázka. )
* Každý vrchol označujeme dvojicí čísel, z nichž první určuje pořadí příchodu a druhý
pomocné číslo, které se v průběhu aktualizuje a rozhoduje o příslušnosti ke komponentě
(zároveň máme u každého vrcholu odkaz na jeho předchůdce).
* Při prvním příchodu do vrcholu ho označíme dvojicí pořadí, pořadí.
* Pokud existuje hrana do dosud nenavštíveného vrcholu, jdi do něj.
* Pokud existuje hrana do již navštíveného vrcholu, nahraď pomocné číslo stávajícícho
vrcholu pomocným číslem vrcholu, do nějž směřuje hrana (pouze, je-li menší).
* Pokud neexistuje nepoužitá hrana a obě čísla u daného vrcholu jsou stejná, přiřaď
všechny dosud nezařazené vrcholy, které mají pomocné čísla větší nebo rovno číslu
současného vrcholu do téže komponenty. Vrať se do předchůdce a aktualizuj jeho pomocné
číslo číslem vrcholu, z nějž se vracíme (je-li menší).
* Pokud neexistuje nepoužitá hrana a čísla u daného vrcholu jsou různá, vrať se do
předchůdce a aktualizuj jeho pomocné číslo číslem vrcholu, z nějž se vracíme (je-li menší).
* Nejsou-li ještě vyčerpány všechny vrcholy a z právě zpracovaného vrcholu již není, kam
se vrátit, zvol jiný vrchol a pokračuj v algoritmu.
Postup v naší úloze (hrany jsou vybírány v pořadí zápisu v tabulce shora dolů):
11,1, 52,2, 43,3, 64,4, 64,2, 43,2, 52,2, 95,5, 86,6, 117,7, 117,6, 86,6. Nyní uzavřeme komponentu tvořenou
všemi vrcholy s pomocným číslem  6, tj. 8 a 11. Tyto vrcholy a s nimi incidentní hrany již
dále neuvažujeme. Návrat do 95,5, 108,8, 39,9, 39,5, 108,5, 108,4, 95,4, 52,2, 52,2 (v posledním kroku
jsme chtěli jít poslední hranou z 5 ­ do 10, ale tam jsme již byli a ani pomocné číslo neaktualizujeme
­ u 10 je 4 u 5 již je 2). Už nemáme z 5 kam jít a obě čísla jsou stejná, proto
uzavíráme komponentu: 5, 9, 10, 3, 4, 6. Prostřednictvím předchůdců se vracíme do 1, z níž
není úniku a navíc tvoří samostatnou komponentu. Ještě jsme nevyčerpali všechny vrcholy:
210,10, 711,11, 711,10, 210,10 a uzavíráme komponentu 2, 7.
3. Eulerova formule: |V |+|S| = |E|+2. Protože každá stěna sousedí s alespoň 3 hranami a každá
hrana odděluje právě 2 stěny, můžeme dvěma způsoby odhadnout počet incidentních dvojic
(hrana, stěna): 3|S|  2|E|, tj. |S|  2
3
|E| a po dosazení do Eulerovy formule dostaneme
|E| + 2  |V | + 2
3
|E|, z čehož snadno plyne dokazovaná nerovnost. (Pozn. k teorii e): kdyby
měl každý vrchol stupeň aspoň 6, pak je 2|E|  6|V |, což je ve sporu s právě dokázanou
nerovností).
4.