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

Zad. 1

Zad. 2

Zad. 3

Zad. 4

Zad. 5

SUMA

Zad. 1 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 żadne dwie kobiety nie stały jedna za drugą.

Zad. 2. Zliczyć na ile sposobów można kupić 47 litrów soku, jeśli dostępne są sok pomarańczowy

w opakowaniach po 1 i 2 litry w nieograniczonych ilościach oraz sok grejpfrutowy w opakowaniach

dwulitrowych, ale tylko 20 sztuk.

Zad. 3 Niech G będzie grafem Eulera, a v dowolnym jego wierzchołkiem. Udowodnić, że liczba

składowych grafu G − v nie przekracza

deg

G

(v)

2

.

Zad. 4 Niech k ∈ N. Udowodnić, że jeśli dla każdej pary niesąsiednich wierzchołków x, y w n-

wierzchołkowym grafie G zachodzi deg

G

(x) + deg

G

(y) ­ n + k, to κ(G) ­ k + 2.

Zad. 5 Udowodnić twierdzenie Szekeresa-Wilfa: Jeśli k = max{δ(H) : H– indukowany podgraf grafu G},

to χ(G) ¬ k + 1.

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

Zad. 1

Zad. 2

Zad. 3

Zad. 4

Zad. 5

SUMA

Zad. 1 Zliczyć na ile sposobów n osób może ustawić się w kolejki do trzech nierozróżnialnych kas w

taki sposób, aby do każdej kasy stała przynajmniej jedna osoba.

Zad. 2. Zliczyć na ile sposobów można kupić 49 litrów soku, jeśli dostępne są sok pomarańczowy

w opakowaniach po 1 i 2 litry w nieograniczonych ilościach oraz sok grejpfrutowy w opakowaniach

dwulitrowych, ale tylko 10 sztuk.

Zad. 3 Udowodnić, że jeśli δ(G) ­

n

2

− 1, gdzie n ­ 4 jest liczbą wierzchołków grafu G, to G ma

ścieżkę Hamiltona.

Zad. 4 Udowodnić, że jeśli wierzchołki grafu G można ustawić w ciąg (v

1

, . . . , v

n

), w taki sposób,

że dla każdego i ∈ {1, . . . , n} zbiór N (v

i

) ∩ {v

1

, . . . , v

i

} indukuje podgraf pełny, to χ(G) jest równa

rozmiarowi najliczniejszej kliki (klika to zbiór wierzchołków podgrafu pełnego).

Zad. 5 Udowodnić, że dla każdych dwóch wierzchołków v i u grafu dwuspójnego istnieje cykl prosty

C

v,u

taki, że v, u ∈ V (C

v,u

).