# Kombinatorika a grafy I, Jiří Fiala, 31. 5. 2018

<{ForumPost(poster="NeverNotBluu", timestamp=2018-06-04 19:51:23)}>
1) Napište definici konečné projektivní roviny. Definujte řád konečné projektivní roviny. Určete počet trojic bodů k.p.r. řádu n ležících na stejné přímce.  
  
2) Definujte blokový kód a jeho parametry. Může existovat kód s parametry $(6,2,2)_3$?  
  
3) Zformulujte a dokažte větu o počtu binárních stromů.  
  
4) Definujte hranovou souvislost grafu. Existuje graf, jehož vrcholová souvislost je 4 a hranová 7?  
  
5) Sepište přehledově, co víte o počítání koster grafu.
<{/ForumPost}>

<{ForumPost(poster="NeverNotBluu", timestamp=2018-06-04 20:06:01)}>
**ŘEŠENÍ:**  
  
1) Každá trojice náleží právě jedné přímce, tedy celkový počet spočteme jako #přímek krát  #trojic na jedné přímce, neboli $(n^2+n+1)\cdot \left( \begin{matrix} n+1 \\ 3 \end{matrix} \right) $  
  
2) Příklad takového kódu:  
000000  
110000  
011000  
001100  
000110  
100002  
010002  
001002  
000102  
  
3) Počet stromů odpovídá Catalanovým číslům.  
  
4) Existuje, např. takto:  
Mezi dvě K<sub>8</sub> dáme čtyři body. V každé K<sub>8</sub> vybereme čtyři body a každý spojíme s každým z bodů uprostřed.
<{/ForumPost}>