# Zkouška 18.1.2005

<{ForumPost(poster="Lovec", timestamp=2005-01-18 17:40:56)}>
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
<{/ForumPost}>