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

Zad. 1

Zad. 2

Zad. 3

Zad. 4

Zad. 5

SUMA

Zad. 1(12pkt) Zliczyć na ile sposobów k rozróżnialnych kobiet oraz m rozróżnialnych mężczyzn może

ustawić się w kolejkę w taki sposób, aby między każdymi dwoma mężczyznami stały przynajmniej

dwie kobiety.

Zad. 2.(12pkt) Wyznaczyć ogólny wyraz ciągu a

n

gdzie

a

n

= a

n−1

+ 2a

n−2

− 2 dla n ­ 2, a

0

= 2, a

1

= 3.

Zad. 3(12pkt) Niech P

k

= ({1, .., 100}, E) gdzie ij ∈ E ⇔ |i − j| ¬ k. Zbadać istnienie ścieżki eulera

w grafie P

k

w zależności od k.

Zad. 4(12pkt) Graf G ma dwa drzewa rozpinające T

1

i T

2

takie, że E(T

1

)∪E(T

2

) = E(G). Udowodnić,

że χ(G) ¬ 4. Podać przykład grafu G spełniającego założenia zadania, dla którego χ(G) = 4.

Zad. 5(12pkt) Udowodnić elementarnie (wprost z definicji), że jeśli G = (V, E) jest drzewem to

|V | = |E| + 1.

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

Zad. 1

Zad. 2

Zad. 3

Zad. 4

Zad. 5

SUMA

Zad. 1(12pkt) Zliczyć na ile k kobiet i m mężczyzn może się ustawić w kolejki od trzech rozróżnial-

nych kas w taki sposób, że przy każdej kasie pierwsza w kolejce jest kobieta.

Zad. 2.(12pkt) Wyznaczyć ogólny wyraz ciągu a

n

gdzie

a

n

= a

n−1

+ 6a

n−2

+ 6 dla n ­ 2, a

0

= 0, a

1

= 2.

Zad. 3(12pkt) Dla grafu G = (V, E) definiujemy G

2

= (V, E

2

), gdzie E

2

= {uv : dist(u, v) ¬

2}. Udowodnić że jeśli G jest spójnym grafem o co najmniej 3 wierzchołkach to G

2

jest grafem

dwuspójnym.

Zad. 4(12pkt) Wykazać, że wierzchołki dowolnego drzewa można pokolorować ∆(T ) + 1 kolorami

tak aby sąsiednie wierzchołki oraz wierzchołki o wspólnym sąsiedzie miały różne kolory.

Zad. 5(12pkt) Dla każdego grafu G = (V, E) o co najmniej dwóch wierzchołkach: Jeśli dla każdej

funkcji ”na” f : V − > {0, 1} istnieją wierzchołki x i y takie, że f (x) = 0, f (y) = 1 i x sąsiaduje z y

to G jest spójny.