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.