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

Zad. 1

Zad. 2

Zad. 3

Zad. 4

Zad. 5

SUMA

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

P

n
i=0

n

i

2

i

= 3

n

.

2. (12p.) Niech V

n

= {0, ..., n − 1}, gdzie n > 3. Niech

E

i

= {{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 E

n

=

S

n−1
i=0

E

i

. W końcu niech G

n

będzie grafem (V

n

, E

n

). Zbadać dla jakich n

graf G

n

jest grafem Eulera.

3. (12p.) Niech P = {I

1

, . . . , I

n

} będzie rodziną ograniczonych przedziałów do-

mkniętych na prostej rzeczywistej, tzn. (∀i ∈ [n])I

i

= [a

i

, b

i

], gdzie a

i

, b

i

∈ R

oraz a

i

< b

i

. Zdefiniujmy graf G = (P, E), gdzie I

i

I

j

∈ E wtedy i tylko wtedy,

gdy I

i

∩ I

j

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 a

i

6 a

j

dla i < j.

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

a

n

= a

n−1

+ 2a

n−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 V

n

= {0, ..., n}, gdzie n > 2. Niech E

i

= {{i, i +

n

1}, {i, i +

n

2}}

dla i = 0, ..., n − 1 (gdzie +

n

oznacza dodawanie modulo n) oraz

E

n

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

n−1

[

i=0

E

i

.

W końcu niech G

n

będzie grafem (V

n

, E

n

). Zbadać dla jakich n graf G

n

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

a

n

= 3a

n−1

+ 4a

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