Kolokwium – matematyka dyskretna – grupa B – 7.06.2013 

1.  W drzewie 7-wierzchołkowym (etykietowanym) wierzchołek 3 sąsiaduje z 4, 5, 6, 7, a 

wierzchołek 6 z wierzchołkiem 1 i 2. Kod Prüfera to… 

2.  Na ile sposobów można podzielić 10 przedmiotów pomiędzy 4 osoby (przy czym 

niektóre osoby mogą nic nie dostać), gdy: 
a)  wszystkie przedmioty są różne, 
b)  wszystkie przedmioty są takie same. 

3.  Rozważmy relację inkluzji ⊂ na rodzinie wszystkich podzbiorów zbioru {1, 2, …, 7} o 

liczebności co najwyżej 5. Podaj liczbę elementów: 
a)  maksymalnych 
b)  minimalnych 
c)  największych 
d)  najmniejszych 

4.  Podaj liczbę: 

a)  Grafów etykietowanych o 7 wierzchołkach, 
b)  Permutacji zbioru {1, 2, …, 7} pozostawiających 5 na swoim miejscu. 

5.  Dla jakich n=1, 2, 3 poniższe zdanie jest prawdziwe (może się zdarzyć, że takich n nie 

ma) 
a)  Graf K

n

 jest eulerowski 

b)  Graf K

n,n+1 

jest planarny. 

6.  Czy poniższa formuła jest równa formule ~ (~𝑝 ⇒ 𝑞) 

a)  𝑝 ⇒ ~𝑞 TAK/NIE 

b)  ~(~𝑞 ⇒ 𝑝) TAK/NIE 

c)  𝑝⋁𝑞 

Na powyższe zadania wystarczyło udzielić odpowiedzi, w tych niżej trzeba napisać 
rozwiązanie 

7.  Znajdź rozwiązanie szczególne rekurencji r

n+2

+r

n+1

=6r

n

, r

1

=1, r

2

=17. 

8.  Z grafu będącego jednocześnie grafem eulerowskim i niehamiltonowskim usuwamy 

jedną krawędź. Otrzymany graf: 
a)  nie jest grafem eulerowskim PRAWDA/FAŁSZ ponieważ… 
b)  jest grafem hamiltonowskim PRAWDA/FAŁSZ ponieważ… 

9.  Na ile sposobów można rozdzielić 52 karty pomiędzy 4 graczy tak, aby: 

a)  Każdy miał dokładnie 1 asa, króla, damę, itd. 
b)  Jeden z nich miał same piki, inny same trefle. 

10. Znajdź wyraz ogólny ciągu, którego funkcję tworzącą spełnia równanie 

(1 − 2𝑥)𝑓(𝑥) =

1+2𝑥

1−𝑥

. 

11. Uzasadnij, że w każdym grafie planarnym o przynajmniej 3 wierzchołkach zachodzi 

nierówność 𝐾 ≤ 3𝑊 − 6. Wykaż, że graf K

5

 nie jest planarny. 

12. Ile jest istotnie różnych pokolorowań pól prostokąta 3x4 za pomocą 4 kolorów, jeśli 2 

pokolorowania uznajemy za równoważne, gdy jedno z nich można otrzymać z 
drugiego przez obrót, lub oś symetrii.