MAD egzamin

Egzamin z matematyki dyskretnej (EiTI) z dnia 27.06.2002

Imię i nazwisko:

Wszyskie odpowiedzi uzasadnić podając treść odpowiedniego twierdzenia¹

1.    (12pkt) Rozwiązać równanie rekurencyjne: A_n =    + (-l)^ⁿ⁺¹^(n — 1) dla n > 1 i ,4o = 0.

2.    (8pkt) Ile rozwiązań w liczbach całkowitych nieujemnych parzystych i równych 2 modulo 3 rna równanie a-j + t-> +a- )4-X<j ~ 188. .

3.    (8 pkt) Czy graf G jest eulerowski, semieulerowski, hamiltonowski, dwudzielny?

4 (8 pkt) Wyznaczyć \{G) oraz x«(G).

5.    (6 pkt)Ile jest grafów izomorficznych z T i różnych od niego.

6.    (6 pkt) Dla jakich warości parametru i prostokąt łaciński P można rozszerzyć do kwadratu łacińskiego 5x5. .Jeśli można to pokaż algorytm rozszerzenia na tym przykiadzie?

4 3 2' 3 5 »

2 4 3

7, (12 pkt) Wyprowadzić wzór na liczbę drzew na zbiorze stopnia 1 dla k = 0,.... n

1

1^