20121105669

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 Ę^l = {{ż,z+n l}j{M+n2}} dla i = 0,..., 1 — 1 (gdzie +„ oznacza dodawanie modulo n) oraz

n—1

En = {{i,n} : | = 0,...,n - 1} U U E¹.

0

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 $, zwany Piłą Szaniawskiego, ma drogę Eulera, czy jest grafem Hamiltona, wyznaczyć k(S), A(5), x(5) oraz Zbadać czy S jest grafem planarnym.

a_n = 3a„_i 4- 4a„_2 — 3 • 2^{n 1} dla n ^ 2,

1 = 2, || i i

5. (12p.) Udowodnić twierdzenie Eulera: dla spójnego grafu planarnego G zachodzi p — k + f = 2, gdzie p i | są liczbą wierzchołków i liczbą krawędzi grafu G, odpowiednio, a / oznacza liczbą regionów, na które dzieli płaszczyznę pewna płaska reprezentacja grafu G.