zkouska 16.1.07 skupina D

[studentdiskretky]

1. Urcete pocet ekvivalenci na dane mnozine s n prvky.
2. Dokazte, ze relace "≤" (tady to znamena kroucene mensi nebo rovno) na mnozine {2,3,4,5,6,7} je castecne usporadani, jestlize a≤b (opet kroucene mensi nebo rovno) prave kdyz a je delitelem b. Urcete minimalni a maximalni prvky tohoto castecneho usporadani. Kolik ma toto usporadani linearnich rozsireni?
3. Je pravda, ze pokud zobrazeni gºf je vzajemne jednoznacne, pak take f je vzajemne jednoznacne? Dokazte nebo vyvratte.
4. Kolik je takovych slov delky n, ktera nepouzivaji zadne pismeno vice nez jednou, jestlize abeceda ma k pismen?
5. Formulujte a dokazte vetu o monotonni posloupnosti.
6. Strom lze ekvivalentne popsat jako "jednoznacne souvisly graf". Formulujte a dokazte.
7. Automorfismus grafu G je isomorfismus G s G. Urcete pocet automorfismu kruznice C(n).

Kazdy priklad za tri body. Good luck