Kolokwium – matematyka dyskretna – grupa D – 7.06.2013

1) W (etykietowanym) drzewie o 7 wierzchołkach, wierzchołek 2 sąsiaduje z 1,3,4,5,6 oraz

wierzchołek 1 z wierzchołkiem 7. Podaj kod Prufera tego drzewa.

2) Permutacje π

1

=(1256)(34) π

2

=(236)(14)(5). Rozłóż na cykle π

1

π

2

, ile jest inwersji π

1

π

2

3) Rozważmy relację inkluzji na rodzinie wszystkich podzbiorów zbioru *1,2,…,8+ o

liczebności co najwyżej 6. Podaj liczbę elementów maksymalnych, minimalnych,
największych, najmniejszych.

4) Podaj liczbę krawędzi w drzewie spinającym grafu K

5,9

oraz grafów (etykietowanych) o 9

wierzchołkach

5) Dla jakich n=1,2,3,… poniższe zdanie jest prawdziwe

- graf K

4,n

jest eulerowski

- graf K

n,n+2

jest planarny

6) Czy poniższa formuła jest równoważna formule ~(~p => r)

- p => ~r TAK/NIE
- p v r TAK/NIE
- ~(~r => p) TAK/NIE

7) Znajdź rozwiązanie szczególnie rekurencji r

n+2

= 2 r

n+1

+ 3 r

n

r

1

= 0, r

3

= 24

8) Z grafu G, będącego jednocześnie eulerowskim i niehamiltonowskim usuwamy 1 krawędź,

otrzymamy graf:
- niehamiltonowski TAK/NIE, ponieważ…
- eulerowski TAK/NIE, ponieważ…

9) Rozważmy zbiór wszystkich funkcji f:{1,2,3,4,5} -> {1,2,3,4,5,6,7} Ile spośród tych funkcji to

funkcje: różnowartościowe, rosnące, niemalejące

10) Znajdź wyraz ogólny ciągu, którego funkcja tworząca spełnia równanie (1 ) ( )

11) Uzasadnij, że w grafie planarnym o przynajmniej 3 wierzchołkach, który nie zawiera

trójkątów, zachodzi nierównośd K≤2W-4. Wykaż, że graf K

3,3

nie jest planarny.

12) Ile jest istotnie różnych sposobów pokolorowania dwoma kolorami kwadratu podzielonego

na trójkąty jak na rysunku poniżej, jeśli za grupę symetrii przyjmiemy grupę symstrii kwadratu
(obroty i symetrie osiowe)?