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−𝑥

Matematyka Dyskretna

7.06.2013

Zestaw A

Zad 11. Podaj wzór Eulera (z założeniami). Uzasadnij, że wielościan foremny, którego ścianami są trójkąty,
a w każdym z wierzchołków stykają się cztery trójkąty musi być ośmiościanem.

Zad 12. Prowadząc trzy wysokości dzielimy trójkąt równoboczny na sześć rozłącznych trójkącików. Ile jest
istotnie równych pokolorowań tych sześciu pól za pomocą 3 kolorów, jeżeli dwa pokolorowania uznajemy za
równoważne, gdy jedno z nich możemy otrzymać z drugiego przez obrót lub symetrię osiową?