18.1.2005 Písemka O.Pangrác

Návštěvník

18.1.2005 Písemka O.Pangrác

Příspěvek od Návštěvník »

1. (a) Definujte tranzitivní relaci na nožině X. Určete, které z následujících tří relací R1,R2,R3 na množině X = {1,2,...} jsou tranzitivní
(i) xR1y <=> x (se nerovná) y
(ii) xR2y <=> x^2 > y
(iii) xR3y <=> x > y^2
(Zdůvodněte)

(b) Kolik existuje zobrazení (funkcí) z {1,2,3,5,7} do {4,5,6,7,8}. Kolik z nich je bijekcí? Zdůvodněte.

(c) Napište definici izomorfismu grafů. Nakreslete všechny neizomorfní stromy se čtyřmi vrcholy a všechny neizomorfní stromy s pěti vrcholy. Zdůvodněte.

2. Zformulujte a dokažte Princip inkluze a exkluze.

3. Dokažte větu o 4 barvách pro každý rovinný graf bez trojúhelníku. Můžete použít jakékoliv tvrzení dokázané na přednášce, aniž byste je dokazovli. (Návod: Využijte toho, že rovinný graf bez trojúhelníku nemá "příliš mnoho" hran a proto má vrcholy "malého stupně".)

4. Pro každé "n" rozhodněte, zda existuje v grafu na "n" vrcholech se skóre (3,3,...,3) (n trojek). (Zdůvodněte)

Zjevně kombinace písemek z minulého roku...
Odpovědět

Zpět na „2004“