Zadania z matematyki dyskretnej Zad.1. Stosuj¡c zasad¦ indukcji matematycznej wykaza¢, »e dla dowolnego n ∈ N liczba 26n+1 + 32n+2 jest podzielna przez 11.

Zad.2. Wyznaczy¢ liczb¦ wszystkich dróg dªugo±ci 3 w grae P2 × P3.

Zad.3. Korzystaj¡c z arytmetyki boolowskiej, wyznaczy¢ wszystkie maksymalne zbiory niezale»ne grafu G, którego model geometryczny jest nast¦puj¡cy: G :

ar

rb

cr

@

@

@

r

r

r

@

f

e

d

Zad.4. Niech h6, 1, 1, 1, 2, 3, 2, 9i b¦dzie kodem Prüfera drzewa T . Narysowa¢ model geometryczny tego drzewa. Poda¢

przykªad:

a) najmniejszego zbioru dominuj¡cego tego drzewa, b) takiego minimalnego zbioru dominuj¡cego tego drzewa, który nie jest zbiorem niezale»nym tego drzewa, c) maksymalnego skojarzenia drzewa T .

Zad.5. Wyznaczy¢:

a) |E(Wn × Pm)|, gdzie n > 4, m > 2, b) χ(Km,n), gdzie m, n > 1, c) |E(T )|, gdzie T jest n-wierzchoªkowym drzewem, n > 2.

Zad.6. Rozwi¡za¢ równanie rekurencyjne a0 = −1, a1 = 1, a2 = 2, an = −2an−1 + 5an−2 + 6an−3 dla n > 3.

1