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)?