Matematyka dyskretna 1300-Inf12MD-SP
Wykład (WYK) Semestr letni 2020/21

1. Libura M., Sikorski J., Wykłady z matematyki dyskretnej, t.1: Kombinatoryka, t.2: Teoria grafów, WIT Warszawa, 2005.

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

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

W1, W2, W3.

Egzamin ustny (przeprowadzony w trybie stacjonarnym) na podstawie listy zagadnień omawianych na wykładzie. Student otrzymuje trzy pytania. Brak odpowiedzi na jakiekolwiek z nich skutkuje oceną niedostateczną. Odpowiedź na wszystkie pytania daje ocenę bardzo dobrą.

1. Schematy kombinatoryczne: wariacje, kombinacje, permutacje, etc., podziały zbiorów i liczb.

2. Równania rekurencyjne i funkcje tworzące. Problem Fibonacciego.

3. 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 (problem mostów królewieckich), charakteryzacje grafów eulerowskich i półeulerowskich, drogi i cykle Hamiltona, kryteria hamiltonowskości grafów.

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), twierdzenia Brooksa i Wizinga.