Matematyka Dyskretna

Zestaw zada´n przygotowawczych do egzaminu.

1. Ile rozwia

,

za´n ma r´ownanie w liczbach caÃlkowitych dodatnich nieparzystych

podzielnych przez 3.

x

1

+ x

2

+ x

3

+ x

4

+ x

5

= 6015

2. 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.

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

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

4. Rozwia

,

za´c r´ownanie rekurencyjne:

a

n

= 3a

n−1

− 3n

2

+ 4n, n ≥ 1, a

0

= 1.

5. 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.

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

7. Gracz losuje 7 kart z 52. Obliczy´c prawdopodobi´nstwo, ˙ze otrzyma

conajmniej jednego asa, conajmniej jednego kr´ola i conjamniej jedna

,

dame

,

?

8. Czy poni´zsze grafy sa

,

hamiltonowskie, eulerowskie, semi-eulerowskie,

dwudzielne?

9. Wyznaczy´c χ

e

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