# Zkouška 19.1. Král

<{ForumPost(poster="Buckey", timestamp=2009-01-19 12:55:33)}>
1. Definujte pojem ekvivalence. Rozhodněte zda relace  
     R={ (a, b) z X x X: NSD(a, b) > 1 }  
    je ekvivalence na X = {2,3,...20}, kde NSD(a, b) označuje největšího společného dělitele čísel a a b. Zdůvodněte.  
  
2. Uveďte Eulerovu formuli včetně předpokladů a s její pomocí ukažte, že každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5.  
  
3. Dokažte, že v každém souvislém grafu G na alespoň dvou vrcholech existují dva různé vrcholy u a v takové, že grafy G-u i G-v jsou souvislé.  
  
4. Nechť X je nezáporná náhodná veličina, která není rovna jedné s pravděpodobností jedna, a α kladné reálné číslo. Která z následujících tvrzení vždy platí?

*  P(X > α * **E**X) < 1/α.
*  P(X >= α * **E**X) <= 1/α.
*  P(X > α * **E**X) <= 1/α.
*  P(X >= α * **E**X) < 1/α.

<{/ForumPost}>

<{ForumPost(poster="Jebi", timestamp=2009-01-19 13:16:45)}>
Stejně se ty otázky furt jen opakujou. I tak pošlu i ty svý + kde to jde, tak co asi tak mělo vyjít..  
  
1. Napište definici izomorfismu grafů. Nakreslete všechny neizomorfní grafy s nejvýše třemi vrcholy. Nakreslete také všechny neizomorfní stromy s pěti vrcholy.  
  
2. Zformulujte a dokažte binomickou větu.  
  
3. Nechť Qn = (V, E) (n je přirozené číslo) je graf na množině vrcholů V = {0, 1}^n (tj. vrcholy jsou uspořádané n-tice z nul a jedniček), přičemž {(x1, x2, .., xn), (y1, y2, .., yn)} je hrana právě když se obě n-tice liší pouze v jediné souřadnici. Rozhodněte, pro které n = 1, 2, ... se graf dá nakreslit jedním uzavřeným tahem bez opakování hran. Svou odpověď zdůvodněte.  
  
4. Zformulujte a dokažte Markovovu nerovnost  
  
---  
  
stručný výsledky  
1. Mělo by vyjít 7 grafů + 3 stromy  
3. pro každé sudé n je graf eulerovský
<{/ForumPost}>

<{ForumPost(poster="popelka", timestamp=2009-01-19 14:01:11)}>
Mé otázky:  
1. Definujte tranzitivní relaci na množina X. Určete, které z následujících 3 relací R1, R2, R3 na množině X = {1,2,...} jsou tranzitivní:  
(a) xR1y <==> x <> y  
(b) xR2y <==> x^2 > y  
(c) xR3y <==> x > y^2  
Zdůvodněte.  
2. Uveďte Eulerovu formuli pro rovinné grafy (ve verzi pro nesouvislé rovinné grafy) a dokažte ji.  
3. Nalezněte nesouvislý rovinný graf G = (V,E) takový, že |V|=9 a |E|=3|V|-9 = 18.  
4. Nalezněte příklad čtyř jevů, které jsou po dvou nezávislé, ale nejsou vesměs nezávislé.  
+- řešení:  
1. Ne (např: 1R2, 2R1, 1neR1), ne (např. 5R10, 10R80, 5neR80), ano (vyjde přímým důkazem)  
3. Např. izolovaný vrchol + graf na 8 vrcholech s 18 hranami (max. možný počet hran, jinak btw. rovinná triangulace)  
4. Podobně jako příklad se 3 jevy z přednášky (modrooká blondýna, hnědooká bruneta, modrooký brunet, hnědooký blondýn), ale vzhledem k tomu, že mají být 4, tak je to o něco složitější (já našla obdobu (s jinou omáčkou), ale + jedna vlastnost a celkově na 8 objektech)
<{/ForumPost}>

<{ForumPost(poster="marion", timestamp=2009-01-19 15:41:46)}>
Jaka je uspesnost? Prosli vsichni?
<{/ForumPost}>

<{ForumPost(poster="popelka", timestamp=2009-01-19 16:08:19)}>

 > marion wrote:Jaka je uspesnost? Prosli vsichni?

Já měla dobré otázky, takže v pohodě (1). A co jsem slyšela u ostatních, tak většinou prošli - a nebo je nechal odejít bez známky, ať se to naučí na příště. Ale nevím..
<{/ForumPost}>

<{ForumPost(poster="lamisil", timestamp=2009-01-19 21:41:14)}>
Tak já jsem dneska dostal:  
  
1. Definujte částečné uspořádání na množině X. Která z následujících tří relací R<sub>1</sub>, R<sub>2</sub> a R<sub>3</sub> na množině přirozených čísel {1, 2,...} jsou částečná uspořádání (Zdůvodněte.):  
  
(a)  xR<sub>1</sub>y  <==>  5x je dělitelné y,  
(b)  xR<sub>2</sub>y  <==>  x = y nebo x - y > 3 a  
(c)  xR<sub>3</sub>y  <==>  x/y < 2?  
  
2. Napište a dokažte větu, pomocí níž lze určit, zda je daná posloupnost čísel skóre grafu.  
  
3. Dokažte větu o 4 barvách pro každý rovinný graf bez trojúhelníku. S vyjímkou věty o čtyřech barvách můžete použít jakékoliv tvrzení z přednášek, aniž byste je dokazovali.  
  
4. Určete střední hodnotu počtu hodů mincí do okamžiku, kdy alespoň jednou padl rub a jednou padl líc.
<{/ForumPost}>

<{ForumPost(poster="strup8", timestamp=2009-01-19 21:49:57)}>
1. Definujte třídu ekvivalence. Popište třídy ekvivalence u následujících tří relací ekvivalence:  
(a) X = {1,2,...,100} xRy <=> 7 dělí |x-y|  
(b) X = {1,2,...,100} xRy <=> (x^2 + y^2) mod 2 = 0  
(c) X = V(K10,15), uRv <=> u a v spojuje cesta sudé délky.  
             (K10,15) značí úplný bipartitní graf.)  
  
2. Zformulujte a dokažte binomickou větu.  
  
3. Jaký je maximální počet vrcholů stupně 3 ve stromu na n vrcholech?  
  
4. Nechť X je nezáporná náhodná veličina a a kladné reálné číslo. Která z následujících tvrzení vždy platí?  
  
P(X > aEX) < 1/a  
P(X >= aEX) <= 1/a  
P(X < EX/a) <= 1/a  
P(X <= EX/a) < 1/a
<{/ForumPost}>

<{ForumPost(poster="Srlok", timestamp=2009-01-22 13:57:42)}>

 > strup8 wrote:
 >   
 > 4. Nechť X je nezáporná náhodná veličina a a kladné reálné číslo. Která z následujících tvrzení vždy platí?  
 >   
 > P(X > aEX) < 1/a  
 > P(X >= aEX) <= 1/a  
 > P(X < EX/a) <= 1/a  
 > P(X <= EX/a) < 1/a

Jak se tohle dělá?
<{/ForumPost}>

<{ForumPost(poster="geckon", timestamp=2009-01-22 23:01:26)}>

 > Srlok wrote:
 >  > strup8 wrote:
 >  >   
 >  > 4. Nechť X je nezáporná náhodná veličina a a kladné reálné číslo. Která z následujících tvrzení vždy platí?  
 >  >   
 >  > P(X > aEX) < 1/a  
 >  > P(X >= aEX) <= 1/a  
 >  > P(X < EX/a) <= 1/a  
 >  > P(X <= EX/a) < 1/a
 > 
 > 
 > Jak se tohle dělá?

 Pomocí Markovovy nerovnosti, řekl bych.
<{/ForumPost}>