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.