od Lovec » 18. 1. 2005 17:40
Zadání:
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)
Je to uplně stejné zadání jako u Pangráce.
Uff, sice za 3 ale je to za mnou. Analyza rulez
Zadání:
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)
Je to uplně stejné zadání jako u Pangráce.
Uff, sice za 3 ale je to za mnou. Analyza rulez