Matematyka Dyskretna
7.06.2013
Zestaw A
Zad 1. Wierzchołkami grafu
𝐾
0
są 1, 2, 3, … 6, a kolejnymi wierzchołkami cyklu
𝐶
5
są 7, 8, … 11. Wierzchołek 1 łączymy krawędzią z wierzchołkiem 7.
a) Ile drzew spinających ma określony graf?
b) Ile drzew spinających nie zawiera krawędzi 7-8
Zad 2. Znajdź liczbę rozwiązań równania
𝑥
1
+ 𝑥
2
+ ⋯ + 𝑥
7
= 20 na liczbach:
a) Całkowitych nieujemnych …
b) Całkowitych większych lub równych 2
Zad 3. Rozważmy relacje inkluzji
⊂ na rodzinę wszystkich podzbiorów zbioru {1, 2, … 6}
o liczebności przynajmniej 2. Podaj liczbę elementów:
a) Maksymalnych
b) Minimalnych
c) Największych
d) Najmniejszych
Zad4. Podaj liczbę krawędzi:
a) grafu
𝐾
10
b) grafów etykietowanych o 6 wierzchołkach
Zad 5. Dla jakich n = 1, 2, 3,… poniższe zdanie jest prawdziwe:
a) graf
𝐾
3,𝑛
nie jest planarny
b) indeks chromatyczny grafu
𝐾
𝑛
jest równy 3
Zad 6. Czy poniższa formuła jest równoważna formule
~(𝑝 ⇒ ~𝑞):
a)
𝑝 ⇒ 𝑞 TAK/NIE
b)
~(𝑝 ⇒ ~𝑞) TAK/NIE
c)
𝑝 ∧ 𝑞 TAK/NIE
Zad 7. Znajdź rozwiązania szczególne rekurencji
𝑆
𝑛+2
+ 4𝑆
𝑛+1
= −4𝑆
𝑛
𝑆
2
= 12, 𝑆
3
= −16
Zad8. Do grafu G będącego zarazem grafem hamiltonowskim i eulerowskim dodajemy jedną krawędź.
Otrzymany graf:
a) Jest grafem eulerowskim PRAWDA/FAŁSZ, ponieważ
b) Nie jest grafem hamiltonowskim PRAWDA/FAŁSZ, ponieważ
Zad 9. Dana jest krata
8 × 8. Znajdź liczbę wszystkich dróg łączących lewy dolny wierzchołek kraty z
prawym górnym (możemy poruszać się jedynie do góry i w prawo). Ile spośród tych dróg przechodzi przez
środkowy punkt kraty?
Zad 10. Znajdź wyraz ogólny ciągu, którego funkcją tworzącą jest
𝑓(𝑥) =
1
1+3𝑥
+
2
4−𝑥
