MATEMATYKA DYSKRETNA

PROGRAM PRZEDMIOTU

MiNI PW   Strona główna   Informacje ogólne  

Niekoniecznie w tej kolejności:
  1. Kombinatoryka. Reguła dodawania i reguła mnożenia. Permutacje i wariacje.
  2. Podzbiory. Podzbiory k-elementowe. Współczynniki Newtona. Reguła włączeń i wyłączeń.
  3. Nieporządki i surjekcje. Kombinacje z powtórzeniami. Zasada szufladkowa Dirichleta.
  4. Pojęcie grafu. Wierzchołki i krawędzie. Stopień wierzchołka, droga, cykl, grafy spójne i niespójne, składowe grafu. Graf pełny. Dopełnienie grafu.
  5. Zagadka mostów królewieckich. Cykl i droga Eulera. Twierdzenie Eulera.
  6. Drzewa. Korzeń, gałęzie i liście. Twierdzenie charakteryzacyjne dla drzew. Drzewa rozpinające. Grafy ważone. Algorytm Kruskala.
  7. Spójność grafu. Spójność wierzchołkowa i krawędziowa. Twierdzenie Mengera. Twierdzenie małżeńskie Halla.
  8. Cykle Hamiltona w grafach. Proste warunki konieczne i warunki dostateczne istnienia cyklu Hamiltona w grafie. Twierdzenia klasyczne - Diraca, Ore, Posa. Pojęcie k-domknięcia grafu. Twierdzenie Bondy'ego i Chvatala.
  9. Niezależne zbiory wierzchołków/krawędzi. Pokrycia wierzchołkowe/krawędziowe. Faktory i faktoryzacja. Twierdzenie Tutte'a o istnieniu 1-faktora.
  10. Kolorowanie grafów. Liczba chromatyczna i indeks chromatyczny. Twierdzenie Szekeresa-Wilfa. Twierdzenie Brooksa. Twierdzenie Vizinga o indeksie chromatycznym.
  11. Grafy planarne. Wzór Eulera. Twierdzenie Kuratowskiego.
  12. Funkcje tworzące. Ciągi rekurencyjne. Ciąg Fibonacciego.