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

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.

Ř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₈ dáme čtyři body. V každé K₈ vybereme čtyři body a každý spojíme s každým z bodů uprostřed.