Imię i nazwisko
Indeks
Prowadzący ćwicz.
MATEMATYKA DYSKRETNA -Elektronika - Termin ekstra -GRUPA A
W ZADANIACH 1-6 KRÓTKIE RACHUNKI LUB INNE WYJAŚNIENIA!
l.(2p.) Na ile sposobów można podzielić zbiór {1,2,10}: a) na 9 niepustych części; b) pomiędzy 9 osób tak, aby każda coś dostała?
2. (1+lp.) Wierzchołkami grafu Kq są 1, 2, 6. a wierzchołkami cyklu C5 są 7, 8, ...11.
Wierzchołek 1 łączymy krawędzią z wierzchołkiem 7.
a) He drzew spinających ma otrzymany graf?
b) He spośród tych drzew nie zawiera krawędzi 7-8.
3. (2p.) Drzewo ma wyłącznie wierzchołki stopnia 1 oraz 4. Znajdź liczbę wierzchołków stopnia 4, jeśli ma ono 43 krawędzie.
4. (2p.) Znajdź rozwiązanie rekurencji rn+2 Arn+1 = 6rn, ri — 1, r2 = 17.
5. (2p.) W drzewie 7-wierzchołkowym wierzchołek 1 sąsiaduje z 2, 3, 4, 5 i 6, a wierzchołek 6 z wierzchołkiem 3. Znajdź kod Pruefera tego drzewa.
6. (1+lp.) Do grafu G będącego zarazem grafem eulerowskim i hamiltonowskim dodajemy jedną krawędź. Otrzymany graf:
- jest grafem eulerowskim PRAWDA/FAŁSZ, bo...................................
- nie jest grafem hamiltonowskim PRAWDA/FAŁSZ, bo...............................
W ZADANIACH 7-9 TYLKO ODPOWIEDZI!
7. (2p.) Dla jakich n = 1,2,3,4,.....poniższe zdanie jest prawdziwe? Może się zdarzyć,
ze takich n nie ma.
a) Graf K^n nie jest planarny.
b) Indeks chromatyczny (dot. krawędzi) grafu Kn jest równy 3.
8. (2p.) Czy poniższa formuła jest równoważna formule ~ (p =+~ ę):
a) p =» q TAK/NIE; b) - (q p) TAK/NIE; c) p A q TAK/NIE.
9. (2p.) Określ wartość logiczną (PRAWDA-FAŁSZ) poniższych zdań:
a) Graf K2i10o nie jest drzewem;
b) Graf K\qq ma liczbę chromatyczną (dot. wierzch.) równą 99;
c) Szkielet krawędziowy ośmiościanu ma indeks chromatyczny równy 4.