# 18.1.2005 Písemka O.Pangrác

<{ForumPost(poster="Anonymous", timestamp=2005-01-18 14:02:07)}>
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...
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2005-01-18 14:02:30)}>
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...
<{/ForumPost}>