Egzamin z matematyki dyskretnej 22 czerwiec 2004

Imię:

Nazwisko:

Grupa:

Numer Indeksu:

Rezygnuje z zadania nr:

Uwagi:

1. Czas rozwiązywania 130 minut.

2. Należy rozwiązać 8 z 9 zadań. Zadanie z którego rozwiązujący rezygnuje należy wymienić powyżej w nagłówku (w przeciwnym razie losowo wybrane zadanie zostanie odrzucone przez sprawdzającego). Można zrezygnować wyłącznie z zadania za 9 pkt.

3. Ewentualne wątpliwości związane z niejednoznacznością sformułowań w zadaniach należy umieścić obok udzielonych odpowiedzi.

4. Dozwolone jest korzystanie z pomocy w formie własnoręcznych notatek i wydruków slajdów z wykładu. Nie wolno korzystać z książek i urządzeń elektronicznych.

5. Zbiór liczb naturalnych nie zawiera zera: 0 ∉ N.

6. Zapis "a | b" oznacza "a jest dzielnikiem b" czyli "b jest podzielne przez a". Zapis NWD(x,y) oznacza największy wspólny dzielnik liczb x i y.

7. W trakcie egzaminu nie wolno opuszczać sali przed oddaniem pracy.

8. Skala ocen jest opisana notacją (a/b/c) gdzie a - liczba pkt. za błędną odp., b - liczba pkt. za brak odp., c - liczba pkt. za dobrą odp.

9. Za żadne z dziewięciu zadań nie można uzyskać mniej niż 0 pkt.

10. Rozwiązania zadań 5, 6, 7, 8 należy umieścić na odwrocie (w ostateczności na osobnej kartce).

Zad. 1. (9 pkt. 0/0/3) Wyznacz liczbę klas abstrakcji domknięć rownoważnościowych następujących relacji R_i ⊆ N²:

1. xR₁y ⇔ NWD (x, y) = 2. Liczba klas abstrakcji p(s(z(R₁))): _{...........................}

2. xR₂y ⇔ x² + y² mod 3 ≠ 1. Liczba klas abstrakcji p(s(z(R₂))): _{...........................}

3. xR₃y ⇔ x ≥ 10 ∧ x | y. Liczba klas abstrakcji p(s(z(R₃))): _{...........................}

Zad. 2. (9 pkt. 0/0/3) Na ile sposobów można rozdać talię 52 (rozróżnialnych) kart pomiędzy 4 (rozróżnialne) osoby tak, aby:

1. Każdy otrzymał tyle samo kart_{............................................}

2. Każdy otrzymał co najmniej jedną kartę_{..........................................................}

3. Każdy otrzymał 1 asa, 1 króla, 1 damę, ...., 1 trójkę i 1 dwójkę_{........................................}

Zad. 3. (9 pkt. 0/0/6+3) Rozwiąż problem chińskiego listonosza dla grafu nr 1 (suma wag w tym grafie wynosi 72). Odpowiedz na pytania:

1. Jaka jest długość drogi przebytej przez chińskiego listonosza:_{....................................}

2. Jaka jest waga minimalnego drzewa spinającego w tym grafie:_{.......................}

Zad. 4. (12 pkt. T/N -1.5/0/0.5 Num. 0/0/0.5) Wypełnij poniższą tabelę wpisując TAK/NIE lub odpowiednie wartości liczbowe:

G	Hamilto-nowski	Euler-owski	Planar­ny	diam(G)	χ(G)	χ'(G)
Graf 1
Graf 2
Graf 3
Graf 4

Zad. 5. (9 pkt.) Podaj przykład dwóch spójnych grafów kubicznych (reg. stp. 3) o tej samej liczbie wierzchołków (nie więcej niż 8), które nie są izomorficzne. Odpowiedź uzasadnij.

Zad. 6. (9 pkt. (grafy dla większych r będą wyżej punktowane)) Dla wszystkich możliwych r ∈ N przedstaw planarny graf regularny stopnia r o najmniejszej możliwej liczbie wierzchołków.

Zad. 7. (9 pkt.) Wyznacz zwarty wzór na a_n, gdzie a₁ = a₃, a_­2 = -2 oraz a_n = a_n-1 + 2a_n-2 + 6n - 15. Udowodnij poprawność przedstawionego wzoru za pomocą indukcji.

Zad. 8. (9 pkt.) Znajdź wszystkie 1 ≤ n ≤ 2004, n ∈ N takie, że 99 | (n + 12)(n + 38)

Zad. 9. (9 pkt. 0/0/2+7*1) Niech A = { (x, y) : x, y ∈ N ∧ x ≤ 5 ∧ y ≤ 5 ∧ 2 | x + y + 1}

Dana jest relacja porządku częściowego R ⊆ A² określona formułą: (a, b)R(c, d) ⇔ a ≤ c ∧ b ≤ d. Wyznacz (względem relacji R):

1. Wszystkie elementy minimalne w A: _{...................................................................................}

2. Wszystkie elementy maksymalne w A: _{...................................................................................}

3. Element największy w A: _{......................................}

4. Element najmniejszy w A: _{......................................}

5. Wysokość porządku częściowego (A, R): _{....................................}

6. Szerokość porządku częściowego (A, R): _{....................................}

Narysuj diagram Hassego tej relacji poniżej:

---