Imię i nazwisko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Zad. 1

Zad. 2

Zad. 3

Zad. 4

Zad. 5

SUMA

1. (12p.) Udowodnić kombinatorycznie tożsamość P n

n 2 i = 3 n.

i=0

i

2. (12p.) Niech Vn = { 0 , ..., n − 1 }, gdzie n > 3. Niech Ei = {{i, i + n 1 }, {i, i + n 2 }, {i, i + n 3 }}

dla i = 0 , ..., n − 1 (gdzie + n oznacza dodawanie modulo n) oraz dodatkowo połóż-

my En = S n− 1 Ei. W końcu niech G

i=0

n będzie grafem ( Vn, En). Zbadać dla jakich n

graf Gn jest grafem Eulera.

3. (12p.) Niech P = {I 1 , . . . , In} będzie rodziną ograniczonych przedziałów do-mkniętych na prostej rzeczywistej, tzn. ( ∀i ∈ [ n]) Ii = [ ai, bi], gdzie ai, bi ∈ R

oraz ai < bi. Zdefiniujmy graf G = ( P, E), gdzie IiIj ∈ E wtedy i tylko wtedy, gdy Ii ∩ Ij 6= ∅. 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 ai 6 aj dla i < j.

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

an = an− 1 + 2 an− 2 − 1 + 10 · 4 n− 2 dla n > 2 , a 0 = 0, a 1 = 2.

5. (12p.) Udowodnić twierdzenie K˝

oniga o maksymalnym skojarzeniu w grafie

dwudzielnym.

Imię i nazwisko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Zad. 1

Zad. 2

Zad. 3

Zad. 4

Zad. 5

SUMA

1. (12p.) Wyznaczyć liczbę ciągów długości n o wyrazach ze zbioru {A, B, C, D}, które nie zawierają wyrazu A lub wyrazu B lub wyrazu C.

2. (12p.) Niech Vn = { 0 , ..., n}, gdzie n > 2. Niech Ei = {{i, i + n 1 }, {i, i + n 2 }}

dla i = 0 , ..., n − 1 (gdzie + n oznacza dodawanie modulo n) oraz

n− 1

E

[

n = {{i, n} : i = 0 , ..., n − 1 } ∪

Ei.

i=0

W końcu niech Gn będzie grafem ( Vn, En). Zbadać dla jakich n graf Gn jest grafem Eulera.

3. (12p.) Zbadać czy poniższy graf S, zwany Piłą Szaniawskiego, ma drogę Eulera,

czy jest grafem Hamiltona, wyznaczyć κ( S), λ( S), χ( S) oraz χ0( S). Zbadać czy S

jest grafem planarnym.

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

an = 3 an− 1 + 4 an− 2 − 1 − 3 · 2 n− 1 dla n > 2 , a 0 = 2, a 1 = 6.

5. (12p.) Udowodnić twierdzenie Eulera: dla spójnego grafu planarnego G zachodzi

p − k + f = 2, gdzie p i k są liczbą wierzchołków i liczbą krawędzi grafu G, odpowiednio, a f oznacza liczbą regionów, na które dzieli płaszczyznę pewna płaska

reprezentacja grafu G.