20121105670

Imię i nazwisko

Zad. 1	Zad. 2	Zad. 3	Zad. 4	Zad. 5	SUMA

1.    (12p.) Udowodnić kombinatorycznie tożsamość 53"=o (")2' = 3".

2.    (12p.) Niech V_n = {0.....n — 1}, gdzie n > 3. Niech

E' = {{i, i +_n 1}> {i, i +n 2}, {i,i +n 3}}

dla i gj 0,72 — 1 (gdzie +„ oznacza dodawanie modulo n) oraz dodatkowo połóżmy E_n = UŁo Eⁱ. W końcu niech G„ będzie grafem (V_n, E_n). Zbadać dla jakich n graf G„ jest grafem Eulera.

3.    (12p.) Niech P = { Ą ,...,/„ } będzie rodziną ograniczonych przedziałów domkniętych na prostej rzeczywistej, tzn. (Vi 6 [n])/, = [a,, 6j], gdzie aj, bi 6 R oraz Oj < ó,. Zdefiniujmy graf G — (P,E), gdzie Iilj € E wtedy i tylko wtedy, gdy Ii fi Ij -fi 0. Wykazać, że liczba chromatyczna grafu G jest równa liczności najliczniejszej kliki w tym grafie. (Klika to zbiór wierzchołków podgrafu pełnego.)

Wskazówka. Uporządkować wierzchołki grafu G tak, aby a* aj dla i < j.

4.    (12p.) Rozwiązać równanie rekurencyjne

dn = ijńji "1“ 2dn—2 -ł-10 • 4" \ dla n ^ 2,

oo = 0, aj = 2.

5.    (12p.) Udowodnić twierdzenie Kóniga o maksymalnym skojarzeniu w grafie dwudzielnym.