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

NeverNotBluu
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 4. 6. 2018 19:43
Typ studia: Informatika Bc.

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

Příspěvek od NeverNotBluu »

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.
Naposledy upravil(a) NeverNotBluu dne 4. 6. 2018 20:06, celkem upraveno 1 x.
NeverNotBluu
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 4. 6. 2018 19:43
Typ studia: Informatika Bc.

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

Příspěvek od NeverNotBluu »

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

Zpět na „Ostatní“