Zkouška 19.1. Král

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 > α * EX) < 1/α.

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

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

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

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

2. pro každé sudé n je graf eulerovský

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í:

5. Ne (např: 1R2, 2R1, 1neR1), ne (např. 5R10, 10R80, 5neR80), ano (vyjde přímým důkazem)

6. Např. izolovaný vrchol + graf na 8 vrcholech s 18 hranami (max. možný počet hran, jinak btw. rovinná triangulace)

7. 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)

Jaka je uspesnost? Prosli vsichni?

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..

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₁, R₂ a R₃ na množině přirozených čísel {1, 2,...} jsou částečná uspořádání (Zdůvodněte.):

(a) xR₁y <==> 5x je dělitelné y,
(b) xR₂y <==> x = y nebo x - y > 3 a
(c) xR₃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.

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

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á?

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.