Matematyka dyskretna - Lista przygotowawcza do I-go kolokwium

1. Rozwi¡» zale»no±ci rekurencyjne (podaj wzór lub reguª¦ opisuj¡ca n-ty

wyraz bez u»ycia rekurencji):

(a) a

0

= 1, a

n

=

2

a

n

−1

,

(b) a

0

= 0, a

n

=

1

1+a

n

−1

(c) a

0

= 1, a

1

= 3, a

n

=

a

2

n

−1

a

n

−2

, (d) a

1

= 1, a

n

= a

n

−1

+ (

−1)

n+1

n

.

2. Znajd¹ wzóry na ci¡gi zadane równaniami rekurencyjnymi:

(a) a

0

= 2

, a

1

= 5

, a

n+2

= 3a

n+1

− 2a

n

,

(b) a

0

=

−2, a

1

= 6

, a

n+2

= 6a

n+1

− 9a

n

,

(c) a

1

= 2

, a

2

= 5

, a

n

=

−5a

n

−1

− 6a

n

−2

.

3. Na ile sposobów mo»na przej±¢ najkrótsz¡ drog¡ z dolnego lewego rogu

do prawego górnego rogu spaceruj¡c po siatce prostok¡ta o wymiarach

a) 2 na 3, b) 3 na 6, c) 4 na 5. Ile jest dróg omijaj¡cych punkt (2, 3)

dla przypadków b i c ? Narysuj drog¦ odpowiadaj¡c¡ (odpowiednio dla

przypadków a) b) c)) zbiorom {1, 4}, {2, 4, 7}, {1, 5, 6, 8, 9}.
4. Na ile sposobów mo»na przej±¢ najkrótsz¡ drog¡ z dolnego, lewego, przed-

niego rogu do prawego, górnego, tylnego rogu spaceruj¡c po siatce prostopa-

dªo±cianu o wymiarach 3 na 3 na 5 ?
5. Ile jest liczb podzielnych przez

(a) 2, 5, 7 w±ród liczb od 1 do 77 ? (b) 2, 3, 7 w±ród liczb od 23 do 100 ?
6. Ile jest liczb mniejszych od 500 zawieraj¡cych w zapisie cyfr¦ 4 ?
7. Oblicz liczby Stirlinga

{

4

3

}

,

{

4

2

}

,

{

5

3

}

,

{

5

2

}

,

{

6

3

}

.

8. Na ile sposobów mo»na rozmieni¢ kwot¦ 90 zª na banknoty 10 i 20 zª ?

Powtórz to samo zadanie dla kwoty 100 zª i monety 5 zª oraz banknotów 10

i 20 zª ?
9. Narysuj grafy o podanych macierzach s¡siedztwa

A =












0 1 0 1 1
1 0 1 0 1
0 0 0 1 0
0 0 0 1 1
0 0 0 0 0












,

B =




0 1 1
1 0 1
1 1 0




Który z grafów jest skierowany ? Napisz macierz s¡siedztwa grafu "koperta".

10. Zastosuj algorytm Fleury'ego do grafów zaª¡czonych w pliku rysunki.pdf.

Je±li nie istnieje droga Eulera uzasadnij dlaczego i mimo to spróbuj zastoso-

wa¢ algorytm pokazuj¡c na którym kroku algorytm si¦ zaªamie. Dla grafów

dla których istnieje droga Eulera narysuj jedna wybran¦ drog¡ numeruj¡c

kraw¦dzie i ustal w których wierzchoªkach nie bedzie oboj¦tne jak¡ kraw¦d¹

wybierze algorytm.
11. Czy graf o kraw¦dziach {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 5}, {4, 5}

jest hamiltonowski ? Wska» cykl Hamiltona. Z którego z twierdze« po-

danych na wykªadzie mo»na skorzysta¢ ? Uwaga: Napis {a, b} oznacza

kraw¦d¹ (nieskierowan¡) ª¡czac¡ wierzchoªki a i b.

12. Zastosuj wszystkie znane algorytmy kolorowania do grafów zaª¡czonych

w pliku rysunki.pdf. Ustal liczb¦ chromatyczn¡ dla ka»dego z tych grafów.

2