od popelka » 19. 1. 2009 14:01
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)
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)