B1

12 VI 2009

Imię i Nazwisko............................................................. Nr indeksu

Grupa ćwiczeniowa: dzień.................................... godzina..............

Matematyka Dyskretna - Elektronika

Kolokwium nr 2. Zestaw B

Część I. W zadaniach 1-8 proszę podać jedynie odpowiedź, którą należy umieścić bezpośrednio pod zadaniem.

1. (/ pkt.) Podaj kod Priifera dla poniższego drzewa:

W hG hi

2.    (1 pkt.) Ile spośród funkcji / : {1,2,3} —* (1,2,3,4,5} jest:

a) malejących; ^ j ^    b) „na”? Q

3.    (1 pkt.) Czy formuła (~ p) => q jest równoważna formule:

a) (~ <?) =* Pi T A-^    b) p=> (~ q), K/|£    c) p V q? T K.

4.    (1 pkt.) Podaj liczbę chromatyczną (kolorowanie wierzchołków) grafów:

c_s Z ^c'3>    7-

5. (1 pkt.) Krawędzie grafu K₅ kolorujemy trzema kolorami. Podaj maksymalną liczbę m taką, że spośród tych krawędzi jest przynajmniej m jednego koloru. ^

6.    (1 pkt.) Znajdź wyraz ogólny ciągu, którego funkcją tworzącą jest f(x) = - — —.

(O** = - cJ-La A crv-CTL (&_Q =-0

7.    (i pkt.) Dla jakich n graf K_n+6>2n jest:

a) eulerowski, ?ĄftZYS.TlA    b) hamiltonowski? -H w Q>

8.    (1 pkt.) Ile rozwiązań w liczbach całkowitych dodatnich ma równanie x\ + z₂ + • • • +17 = 21?

(?)

Część II. W zadaniach 9-12 proszę podać sposób ich rozwiązania oraz odpowiedź, które należy umieścić bezpośrednio pod zadaniem.

LIC2 & A*'.

9.    (3 pkt.) Znajdź liczbę chromatyczną i indeks chromatyczny grafu K₆ bez jednej krawędzi.

j&_r

£dLuP^CAnę. ]0ł2-O

=■ 5“    _

¹ ■-^    XW) = ś