1.A- Na płaszczyźnie jest 10 prostych, przy czym żadne dwie nie są równoległe i żadne trzy nie przecinają się w jednym punkcie. W ilu punktach przecinają się te proste? (3pkt)

B- W przestrzeni jest 14 punktów, z których jedna czwórka leży na płaszczyźnie a poza tym żadne cztery nie leżą w jednej płaszczyźnie. Ile czworościanów wyznaczają te punkty?

C- Na płaszczyźnie jest 9 prostych przy czym żadne dwie nie są równoległe i żadne trzy nie przecinają się w jednym punkcie. W ilu pkt przecinają się te proste?

D- W przestrzeni jest 12 punktów, z których pięć leży na wspólnej płaszczyźnie a poza tym żadne cztery nie leżą w jednej płaszczyźnie. Ile czworościanów wyznaczają te punkty?

2. A-Ile podzbiorów o parzystej liczbie elementów ma zbiór 11-elementowy? (3pkt)

B- Ile podzbiorów o nieparzystej liczbie elementów ma zbiór 10-elementowy?

C- Ile podzbiorów o parzystej liczbie elementów ma zbiór 12-elementowy?

D- Ile podzbiorów o nieparzystej liczbie elementów ma zbiór 9-elementowy?

3. Ile rozwiązań w liczbach całkowitych dodatnich ma równanie:

A. x₁+x₂+..+x₇=12
B. x₁+x₂+..+x₈=13

C. x₁+x₂+..+x₈=21
D. x₁+x₂+..+x₇=31

4. Wiemy, że dla n
N zachodzi A: W(n)
W(n+3), a także W(10)
W(15). Rozstrzygnij: prawda, fałsz, nie wiadomo. (3pkt)
W(9)…………………….W(11)……………………W(19)………………W(21)………..

B: W(n)
W(n+4), W(11)
W(17).

W(9)…………………….W(19)……………………W(21)………………W(22)………..

C: W(n)
W(n+3), W(12)
W(17).

W(11)…………………….W(13)……………………W(21)………………W(23)………..

D: W(n)
W(n+4), W(13)
W(19).

W(11)…………………….W(21)……………………W(23)………………W(24)………..

5. Podaj rozwiązanie ogólne rekurencji o równaniu charakterystycznym A-(x-5)²=0, B- r²=r+2,C - (x+3)²=0, D - r²=2r+3 (3pkt)

6. A-Na ile sposobów można podzielić za pomocą przekątnych 10-kąt wypukły na trójkąty? Wynik podaj za pomocą odpowiedniego współczynnika newtonowskiego. (3pkt)

B- Na ile sposobów można podzielić za pomocą przekątnych 11-kąt wypukły na trójkąty?
C- Na ile sposobów można podzielić za pomocą przekątnych 12-kąt wypukły na trójkąty
D - C- Na ile sposobów można podzielić za pomocą przekątnych 9-kąt wypukły na trójkąty?

7. Podaj funkcję tworzącą ciągu A- a_n=2ⁿ+1,B - a_n=1-3ⁿ , C - a_n=(-3)ⁿ +1, D- a_n=2-3ⁿ .Wynik możesz zostawić w postaci sumy ułamków. (3pkt)

8. A- Który z grafów platońskich jest izomorficzny z pewnym K_n? Dla jakiego n?(3pkt)
B- Który z grafów dwudzielnych K_2,m jest izomorficzny z pewnym cyklem C_n? Dla jakiego n?

C- Które z grafów platońskich są grafami dwudzielnymi?
D. Który z grafów dwudzielnych K_m,2 jest izomorficzny z pewnym cyklem C_n? Dla jakiego n?


9. A-Ile jest drzew etykietowanych o wierzchołkach 1,2…,8?
B- Ile jest grafów etykietowanych bez pętli i wielokrotnych krawędzi o 10 wierzchołkach?
C- Ile jest drzew etykietowanych o wierzchołkach 1,2…,9?
D- Ile jest grafów etykietowanych bez pętli i wielokrotnych krawędzi o 11 wierzchołkach?

10. Określ wartość logiczną (P,F): (3pkt)

a. Każdy graf eulerowski jest planarny - F
b. Nie każdy graf planarny jest wierzchołkowo 5-cio kolorowany- P
c. Jeżeli K_n jest hamiltonowski, to n jest parzyste- F
d. Graf postaci K_n,n+2 nie może być eulerowski - F

a.Nie każdy graf hamiltonowski jest planarny- P
b.Każdy graf planarny jest krawędziowo 5-cio kolorowany - F

c.Graf postaci K_n,n+2 nie może być hamiltonowski - F

d. Jeżeli K_n jest eulerowski, to n jest parzyste - P

a.Każdy graf planarny jest eulerowski? F
b. Jeżeli K_n jest hamiltonowski, to n jest nieparzyste - F

c. Graf postaci K_n,n+3 nie może być eulerowski- T

d. Graf postaci K_n,n+2 nie może być hamiltonowski -

11. A-Pewien graf spójny G ma 20 wierzchołków i zawiera dokładnie jeden cykl (3pkt)
a. Ile krawędzi trzeba z niego usunąć aby otrzymać drzewo? 1
b. Ile krawędzi ma graf G? 20

c. Ile ścian ma graf G? 2

B- Pewien graf niespójny G ma 30 wierzchołków, a po dodaniu jednej krawędzi staje się drzewem

a. Czy G jest planarny? TAK
b. Ile krawędzi ma graf G? 30

C- Pewien graf spójny G ma 25 wierzchołków i zawiera dokładnie jeden cykl

a. Ile krawędzi trzeba z niego usunąć aby otrzymać drzewo? 1
b. Ile krawędzi ma graf G? 25

c. Ile ścian ma graf G? 2

D- Pewien graf niespójny G ma 35 wierzchołków, a po dodaniu jednej krawędzi staje się drzewem

a. Czy G jest planarny?
b. Ile krawędzi ma graf G?

12. przypomnij sobie rachunek zdań, kwantyfikatory

13. Co to jest drzewo spinające grafu spójnego? A-Ile drzew spinających ma graf powstały z połączenia C₅ z grafem C₇ wspólnym wierzchołkiem? (1+2pkt)
B- podaj przykład grafu, który ma 125 drzew spinających.

14. Czy alternatywa pVg jest równoważna? (Tak,Nie) (3pkt)

15. Wiadomo, że wierzchołek stopnia s występuje w kodzie Prufera s - 1 razy. Dla drzewa o kodzie: 3,1,4,1,5,6,1,8,7,4,4,3,2,1,3,4,2,2 podaj (nie rysujące drzewa) (2+4pkt)
a. liczbę wierzchołków wiszących

b. indeks chromatyczny

3,1,4,1,7,6,1,8,7,4,4,9,2,1,3,4,1,1

a. liczbę wierzchołków wiszących

b. indeks chromatyczny

5,6,1,8,4,1,3,2,7,4,3,4,4,3,1,2,1,2

a. liczbę wierzchołków wiszących

b. indeks chromatyczny

4,1,3,1,4,1,8,7,1,4,1,7,4,9,2,1,3,6

a. liczbę wierzchołków wiszących

b. indeks chromatyczny

16. Znajdź wyraz ogólny ciągu o funkcji tworzącej y=
, y=
, y=

17.Pewne drzewo ma wyłącznie wierzchołki stopnia 1 i 3, łącznie 15 wierzchołków. (3+3pkt)

a. ile ma wierzchołków wiszących?
b. Podaj jego liczbę indeks chromatyczny (krawędziowy)

Pewien graf płaski ma 12 wierzchołków, wszystkie stopnia 5.
a. Ile ma krawędzi? b. Ile ma ścian? c. Czy graf ten może być grafem dwudzielnym?

Pewne drzewo ma wyłącznie wierzchołki stopnia 1 i 3, łącznie 18 wierzchołków
a. ile ma wierzchołków wiszących?
b. Podaj jego liczbę indeks chromatyczny (krawędziowy)

---