Matematyka dyskretna 1300-Inf12MD-SP
Ćwiczenia (CW) Semestr letni 2020/21

1. Rybnikow K. A. (red.), Analiza kombinatoryczna w zadaniach, PWN Warszawa, 1988.

2. Wilson R. J., Wprowadzenie do teorii grafów, PWN Warszawa, 1998.

U1, U2, U3.

Do uzyskania zaliczenia konwersatorium wymagane jest:

- aktywna obecność na zajęciach;

- uzyskanie pozytywnych ocen z dwóch sprawdzianów pisemnych (kombinatoryka i zliczanie oraz teoria grafów) przeprowadzonych w trybie stacjonarnym.

1. Algebra zbiorów, indukcja matematyczna, relacje.

2. Schematy kombinatoryczne: wariacje, kombinacje, permutacje, etc.

3. Równania rekurencyjne i funkcje tworzące.

4. Pojęcia wstępne teorii grafów: graf i digraf, stopnie wierzchołków, rodzaje grafów (grafy dwudzielne, regularne, turnieje, etc.).

5. Planarność grafu, wzór Eulera z zastosowaniami.

6. Drogi i cykle, drogi i cykle Eulera, drogi i cykle Hamiltona.

7. Drzewa i lasy, drzewa (lasy) rozpinające, twierdzenia Cayleya i Kirchhoffa o zliczaniu drzew rozpinających.

8. Niezależność zbiorów wierzchołków i krawędzi. Optymalne (najliczniejsze/najmniej liczne) zbiory niezależne/pokrywające (tożsamości Gallaia, kryterium Berge’a), twierdzenia minimaksowe (Koeniga), twierdzenie Halla, liczba i indeks chromatyczny (oszacowania).