Egzamin z matematyki dyskretnej 17 września 2004

Imię:

Nazwisko:

Grupa:

Numer Indeksu:

Rezygnuję z zadania nr:

Uwagi:

1. Czas rozwiązywania 125 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. Słowo "graf" oznacza graf prosty (bez pętli i krawędzi równoległych).

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

7. 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.

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

9. 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.

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

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

Zad. 1. (9 pkt. 0/0/3) Wyznacz liczbę klas abstrakcji domknięć równoważ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 ≠ 2. Liczba klas abstrakcji p(s(z(R₂))): _{...........................}

3. xR₃y ⇔ x mod y = 2. 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ł 13 kart, a w tym jednego asa_{............................................}

2. Każdy otrzymał co najmniej jedną kartę, a w tym jednego asa_{..........................................................}

3. Każdy otrzymał karty w tym samym kolorze (tzn. same piki lub same kiery lub same kara lub same trefle)_{........................................}

Zad. 3. (9 pkt. 0/0/6+3) Rozwiąż problem chińskiego listonosza dla grafu nr 1 (suma wag w tym grafie wynosi 367). 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 spójnego, kubicznego (reg. stp. 3) grafu o nie więcej niż 20 wierzchołkach, który nie jest hamiltonowski. Odpowiedź uzasadnij.

Zad. 6. (9 pkt.) Jak dużo krawędzi może mieć 9-wierzchołkowy spójny graf planarny, który nie zawiera cykli długości 3 (trójkątów)? Odpowiedź uzasadnij. Przedstaw przykład takiego grafu o największej możliwej liczbie krawędzi.

Zad. 7. (9 pkt.) Wyznacz zwarty wzór na a_n, gdzie a₁ = a₃ - 14, a_­2 = -1 oraz a_n = 2a_n-1 + 3a_n-2 + 20n - 40, dla n ≥ 3. Udowodnij poprawność przedstawionego wzoru za pomocą indukcji. (Wskazówka: Wyznacz początkowe wyrazy ciągu a_n. Wyznacz wyrazy początkowe ciągów b_n = a_n - a_n-1 oraz c_n = b_n - b_n­-1. Odgadnij zwarty wzór dla ciągu c_n. Wyznacz zwarty wzór dla ciągów b_n i a_n)

Zad. 8. (9 pkt.) Wyznacz największą liczbę naturalną n taką, że n ≤ 1959 oraz 245 | (n + 100)(n + 201). Odpowiedź uzasadnij.

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

Dana jest relacja porządku częściowego R ⊆ A² określona formułą: (a, b) R (c, 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 Hass'ego tej relacji (na odwrocie strony).

---