Matematyka dyskretna

fakultatywne

Przegląd wybranych elementów kombinatoryki i teorii grafów. Podstawowe prawa i metody zliczania, zliczanie różnych obiektów związanych ze zbiorami skończonymi. Wykorzystanie zależności rekurencyjnych w problemach zliczania. Zliczanie orbit grup przekształceń. Podstawy teorii grafów: cykle Eulera i Hamiltona, zliczanie drzew, grafy planarne, skojarzenia w grafach. Na wykładzie pojawiają się elementarne pojęcia z algebry i analizy, ale główny nacisk położony jest na dowody kombinatoryczne, w szczególności znajdowanie bijekcji pomiędzy danymi skończonymi zbiorami różnych obiektów kombinatorycznych.

1. Podstawowe prawa i metody zliczania: prawa dodawania i mnożenia, zasada bijekcji, zasada szufladkowa. Współczynniki dwumianowe, dowody kombinatoryczne.

2. Zasada włączania i wyłączania, zliczanie funkcji „na” i nieporządków, problem małżeństw Lucasa.

3. Zliczanie podziałów, liczby Stirlinga II rodzaju, liczby Bella.

4. Zliczanie permutacji, liczby Stirlinga I rodzaju.

5. Rozmieszczenia kul w urnach.

6. Zależności rekurencyjne i funkcje tworzące, liczby Fibonacciego, Catalana i Bella, rozwiązywanie rekurencji liniowych ze stałymi współczynnikami.

7. Zliczanie orbit grup przekształceń: lemat Burnside’a, twierdzenie Polyi o liczbie istotnie różnych, ze względu na ustaloną grupę przekształceń, kolorowań danego zbioru obiektów.

8. Podstawowe pojęcia teorii grafów. Cykle Eulera, grafy eulerowskie i twierdzenie Eulera o ich charakteryzacji, cykle Hamiltona, grafy hamiltonowskie i twierdzenie Orego.

9. Drzewa: charakteryzacje i zliczanie drzew, twierdzenie Cayleya.

10. Grafy planarne i płaskie, twierdzenie Kuratowskiego (bez dowodu), wzór Eulera, kolorowanie wierzchołkowe grafów, twierdzenie o 5 barwach.

11. Skojarzenia w grafach: twierdzenie Halla i jego zastosowania.

1. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 2007.

2. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986.

3. Z. Palka, A. Ruciński, Wykłady z kombinatoryki, WNT, Warszawa 1998.

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

Student:

1. Zna podstawowe prawa i metody zliczania, potrafi przeprowadzać kombinatoryczne dowody tożsamości dwumianowych.

2. Zna rozmaite szczególne liczby występujące w kombinatoryce (współczynniki dwumianowe, liczby Stirlinga, Bella, Fibonacciego i Catalana), ich kombinatoryczne interpretacje oraz własności.

3. Zna zasadę włączania i wyłączania i potrafi ją zastosować w zagadnieniach zliczania różnych obiektów kombinatorycznych.

4. Zna pojęcie funkcji tworzącej ciągu liczbowego; zna przykłady zastosowań aparatu funkcji tworzących do znajdowania wzoru ogólnego na n-ty wyraz ciągu,

5. Zna pojęcie zależności rekurencyjnej i umie je wykorzystać jako narzędzie kombinatoryczne; potrafi rozwiązywać rekurencje liniowe ze stałymi współczynnikami.

6. Zna lemat Burnside’a; potrafi znaleźć liczbę istotnie różnych, ze względu na ustaloną grupę przekształceń, kolorowań danego zbioru obiektów.

7. Zna podstawowe pojęcia teorii grafów i potrafi je zilustrować przykładami.

8. Zna twierdzenie Eulera o charakteryzacji grafów eulerowskich oraz twierdzenie Orego o grafach hamiltonowskich.

9. Zna twierdzenie Cayleya i umie znaleźć liczbę drzew o danym zbiorze wierzchołków.

10. Zna wzór Eulera i potrafi go zastosować do znajdowania ilościowych zależności w grafach planarnych.

11. Zna twierdzenie Halla i przykłady jego zastosowania.

Egzamin pisemny, ewentualnie dodatkowo egzamin ustny.