Egzamin z matematyki dyskretnej 26 czerwca 2007

Imię:

Nazwisko:

Grupa:

Numer Indeksu:

Uwagi:

1. Czas rozwiązywania 90 minut.

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

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

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

5. Zapis "a | b" oznacza "a jest dzielnikiem b" czyli "b jest podzielne przez a".

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

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

8. Za żadne z siedmiu zadań nie można uzyskać mniej niż 0 pkt.

9. Rozwiązania zadań 1 i 6 należy umieścić na odwrocie.

Zad. 1. (10 pkt. 10/0/0) Wyznacz wszystkie liczby naturalne, których nie da się wyrazić w postaci sumy 3m + 5n, gdzie n, m ∈ N. Pamiętaj, że przyjmujemy 0 ∉ N. Odpowiedź uzasadnij. (Wskazówka: Korzystając z indukcji wykaż, że każdą „dużą” liczbę naturalną można przedstawić w zadanej powyżej postaci.)

Odp.: 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 15

Zad. 2. (10 pkt. 2.5/0/0) Dany jest zbiór A = {1, 2,...,10}. W zbiorze A² określono relację R: formułą (a, b) R (c, d) ⇔ ad < bc. Niech S będzie zwrotnym domknięciem relacji R.

(a) Wyznacz wszystkie elementy minimalne w A² względem S: _. (1, 10)

(b) Wyznacz wszystkie elementy maksymalne w A² względem S: _. (10, 1)

(c) Przedstaw najdłuższy antyłańcuch w A² względem S_.: (1, 1), (2, 2), ... , (10, 10)

(d) Wyznacz długość najdłuższego łańcucha w A² względem S_. 63

Zad. 3. (10 pkt. 2.5/0/0) Wyznacz liczbę:

(a) Wszystkich cykli w grafie K_10:.

W przypadku cykli skierowanych o wyróżnionym początku:
(obie odpowiedzi były uznawane przy sprawdzaniu za poprawne, ze względu na dualną definicję cyklu w literaturze)

(b) Wszystkich automorfizmów w grafie K_10,10: (10!)²∙2

(c) Wszystkich dróg otwartych maksymalnej długości w grafie K_10,10: (10!)²

W przypadku dróg skierowanych: (10!)²∙2 (obie odpowiedzi były uznawane przy sprawdzaniu za poprawne, ze względu na dualną definicję cyklu w literaturze).

(d) Wszystkich cykli długości 5 w grafie K_10,10,10: 3⁵∙10³

W przypadku cykli skierowanych o wyróżnionym początku: 3⁵∙10⁴ (obie odpowiedzi były uznawane przy sprawdzaniu za poprawne, ze względu na dualną definicję cyklu w literaturze)

Zad. 4. (10,5 pkt. 0.5/0/-0.5) Wyznacz wybrane parametry następujących grafów:

	K2,3 + K1	Q3 + C4	C4 + N3
χ(G)	3	4	3
χ'(G)	5	10	6
rad(G)	1	2	2
τ(G)	2	2	2
chl(G)	14	52	18
ω(G)	3	4	3
cir(G)	6	12	7

Zad. 5 (10 pkt.) Uporządkuj według niemalejącego tempa wzrostu następujące funkcje (tak, że jeśli f występuje przed g, to zachodzi f = O(g)):

1

2

5

3

4

6

W powyższej tabelce należy wpisać jedynie indeksy funkcji, a nie formuły.

Zad. 6 (10 pkt. 10/0/0) Dany jest ciąg (a_n), określony rekurencyjnie:

a₁ = 3, a₂ = 7, a_n = 5a_n­-1 - 6a_n-2, dla n > 2. Wyznacz zwarty wzór na n-ty wyraz tego ciągu.

Odp.: 2ⁿ + 3^n-1

Długość marszruty chińskiego listonosza

Długość najdłuższego cyklu

---