A1

12 VI 2009

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

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

Matematyka Dyskretna - Elektronika Kolokwium nr 2. Zestaw A

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

1. (1 pkt.) Podaj indeks chromatyczny (kolorowanie krawędzi) grafów:

K₆ 5" Ki ?    C₆ l    CV J2>

2.    (1 pkt.) Równaniem charakterystycznym pewnego równania rekurencyjego jest r² = r-f 6. Jaką postać

ma jego rozwiązanie ogólne?

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

_P)? Taić

ej q

a) (~ q) =*■ p, S)l    b) ~ (p A q), I Ak

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

5. (1 pkt.) Dla jakich n graf Kn+A&n jest: a) eulerowski.

b) hamiltonowski? {1,2,3,4,5,6} jest:

b) „na"? Q t

6.    (i pkt.) Ile spośród funkcji / : {1,2,3,4,5,6} a) różnowartościowych; <ol

7.    (1 pkt.) Określ wartość logiczną (prawda (P), fałsz (F)) zdań:

a)    każde drzewo mające więcej niż jeden wierzchołek jest grafem dwudzielnym; F⁵

b)    każdy graf dwudzielny jest drzewem; P c) każdy graf dwudzielny jest planarny, P

8.    (1 pkt.) Oblicz wartość funkcji Eulera 0(490).    /    \ /

łSO-M(4-4)(4-£

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.

9.    (3 pkt.) Ile maksymalnie krawędzi można dorysować do poniższego drzewa tak, aby powstały graf był zarówno planarny jak i dwudzielny:

6-ftAF plaiuaRiOi i buubziis.Lmuł ŁAuiu&ftA Tft.ó'jK.q_iTÓo (crtai bt. i), 2-ATFh MOz&kay 0=^    z Asto sou ać do    fliełUtouośt'

K'<    AL

Zrttin HÓ2CKY NAizSyMAuwE OofttsaOAĆ Ai-fFejr. ?0WIZS2Y RVSUWl£.l2. Vou.Alu-jj.iE.    TO NĆHUOlt