Imię i nazwisko
Indeks
Prowadzący ćwicz.
MATEMATYKA DYSKRETNA -Elektronika - Termin ekstra -GRUPA C
W ZADANIACH 1-6 KRÓTKIE RACHUNKI LUB INNE WYJAŚNIENIA!
1. (2p.) Znajdź rozwiązanie rekurencji rn+2 = 4rn+i — 3rn, ri = 0, r% — 24.
2. (2p.) W drzewie 7-wierzchołkowym wierzchołek 1 sąsiaduje z 2, 3, 4, 5 i 6, a wierzchołek 4 z wierzchołkiem 7. Znajdź kod Pruefera tego drzewa.
3. (2p.) Drzewo ma 25 wierzchołków, wszystkie stopnia 1 albo 6. Znajdź liczbę wierzchołków stopnia 1, jeśli ma ono 51 krawędzi.
4. (1+lp.) Wierzchołkami grafu K7 są 1, 2, 6, 7. a wierzchołkami cyklu C$ są 8,9 ...12.
Wierzchołek 1 łączymy krawędzią z wierzchołkiem 12.
a) Ile drzew spinających ma otrzymany graf?
b) Ile spośród tych drzew nie zawiera krawędzi 8-9?
5.(2p.) Na ile sposobów można podzielić zbiór {1,2,.., 11}: a) na 10 niepustych części; b) pomiędzy 10 osób tak, aby każda coś dostała?
6. (1+lp.) Do grafu G będącego zarazem grafem eulerowskim i hamiltonowskim dodajemy jedną krawędź. Otrzymany graf:
- nie jest grafem eulerowskim PRAWDA/FAŁSZ, bo...................................
- 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.) Określ wartość logiczną (PRAWDA-FAŁSZ) poniższych zdań:
a) Szkielet krawędziowy ośmiościanu ma liczbę chromatyczną (dot. wierzch.) równą 2;
b) Graf AT10i ma liczbę chromatyczną równą 100;
c) Nie każde drzewo jest grafem planarnym.
9. (2p.) Czy poniższa formuła jest równoważna formule ~ (r q):
a) ~ (q r) TAK/NIE; c) r A q TAK/NIE; b) r q TAK/NIE?