Matematyka Dyskretna

Zestaw zada´n przygotowawczych do egzaminu.

1. Wyznaczy´c drzewa o kodach Prufera [5, 4, 3, 5, 4, 3], [3, 3, 3, 2, 1, 1, 4].

Odpowied´z sprawdzi´c wyznaczaja

,

c kody dla tych drzew.

2. Czy ka˙zdy graf sp´ojny o 18 wierzchoÃlkach stopnia 1, 2 wierzchoÃlkach

stopnia 8, 2 wirzchoÃlkach stopnia 4 jest drzewem?

3. Rozwia

,

za´c r´ownanie rekurencyjne:

a

n

= 3a

n−1

− 3n

2

+ 4n, n ≥ 1, a

0

= 1.

4. Rozwia

,

za´c r´ownanie rekurencyjne:

a

n+2

+ 4a

n

+ 2

n+3

cos(

nπ

2

) = 0, n ≥ 1, a

0

= a

1

= 0.

5. Dla jakich warto´sci parametr´ow i, j prostoka

,

t Ãlaci´nski











1 i 3 4
2 3 4 j
3 4 6 5
4 1 2 3











mo˙zna rozszerzy´c do kwadratu Ãlaci´nskiego 6 × 6. Pokaza´c rozszerzenie
wykorzystuja

,

c algorytm przyje

,

ciowy.

6. Wyznaczy´c tabelki dziaÃla´n ciaÃla Z

5

. Na tej podstawie wyznaczy´c 4

wzajemnie ortogonalne kwadraty Ãlaci´nskie 5 × 5.

7. Wyznaczy´c tabelki dziaÃla´n ciaÃla GF (9). Na tej podstawie wyznaczy´c

8 wzjemnie ortogonalnych kwadrat´ow Ãlaci´nskich 9 × 9.

8. Ile jest graf´ow izomorficznych z grafami A, B, C?

9. Czy poni´zsze grafy sa

,

hamiltonowskie, eulerowskie, semi-eulerowskie,

dwudzielne?

10. Wyznaczy´c χ

e

(G) i χ(G) dla poni˙zszych graf´ow: