Egzamin z matematyki dyskretnej 18 września 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) W pewnym turnieju każda drużyna rozgrywała z każdą jeden mecz. Każdy mecz kończył się zwycięstwem jednej z drużyn (nie było remisów). Żadna drużyna nie wygrała wszystkich meczów. Wykaż, że można wybrać trzy takie drużyny A, B, C, że A wygrała z B, B wygrała z C i C wygrała z A.

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

(a) Wyznacz wszystkie elementy minimalne w A względem S: _{.............................................................................}

(b) Wyznacz wszystkie elementy maksymalne w A względem S: _{. ......................................................................}

(c) Wyznacz kres dolny zbioru {5, 7} w A względem S_.: _{............................................................................................}

(d) Wyznacz najdłuższy łańcuch w A względem S:_{. ........................................................................................................}

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

(a) Wszystkich podziałów siedmio-elementowego zbioru, na dwa (niepoetykietowane) co najmniej dwu elementowe podzbiory:

_{..........................................................................................................}

(b) Wszystkich automorfizmów w grafie K_2,2,2:

_{..................................................................................................}

(c) Wszystkich 10-cio literowych słów składających się z liter ze zbioru {a, b, c} tak, aby każda z liter wystąpiła co najmniej trzykrotnie:

_{..........................................................................................................}

(d) Wszystkich krawędzi w grafie K_1,2,3,4:

_{..........................................................................................................}

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

	K2 + N4	K2 + P3	K1,1,2,2
χ(G)
χ'(G)
rad(G)
τ(G)
chl(G)
ω(G)
cir(G)

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)):

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:

Wyznacz wzór na n-ty wyraz tego ciągu. Wykaż poprawność uzyskanego wzoru.

Długość marszruty chińskiego listonosza

Długość najdłuższego cyklu

---