MD Zaoczne
Matematyka Dyskretna Studia ZaoczneJedyny termin egzaminu we wrześniu to 4 września.
Lista twierdzeń obowiazujących na egzaminie z dowodami
1. Twierdzenie Eulera (z dowodem lematu)
2. Twierdzenia Diraca lub Ore
3. Charakteryzacja grafów dwudzielnych (to że nie zawierają nieparzystych cykli)
4. Formuła Eulera
5. Twierdzenie o 4 kolorach, ewentualnie o 5 kolorach.
Zestaw 1 - Indukcja,
Zestaw 2 - Zliczanie, Zasada wł-wył,
Zestaw 3 - Grafy
Zestaw 4 - Spójność, obwód Eulera, cykl Hamiltona, kolorowanie
Zestaw 5 - Planarność
kolokwia z zeszłych lat
kolokwium 1 2007 | 2008 | 2009|2010
kolokwium 2 2007 | 2008 | 2009
Sylabus
Program przedmiotu:
1. Indukcja matematyczna, definicje rekurencyjne, równania rekurencyjne, asymptotyka, notacja O().
2-4.
Podstawy kombinatoryki - podstawowe struktury kombinatoryczne,
permutacje, kombinacje, współczynniki Newtona, podstawowe metody
zliczania, tożsamości kombinatoryczne, zasada włączania-wyłączania.
5. Podstawy teorii grafów - podstawowe pojęcia.
6. Drzewa, minimalne drzewa rozpinające, algorytm Kruskala.
7. Spójność, twierdzenie Mengera.
8. Obwód i ścieżka Eulera.
9-10. Cykl i ścieżka Hamiltona, problem komiwojażera.
11-12. Planarność, formuła Eulera, twierdzenie Kuratowskiego.
13. Kolorowanie krawędzi, indeks chromatyczny, twierdzenie Vizinga.
14. Kolorowanie wierzchołków, liczba chromatyczna.
15. Twierdzenie Halla, skojarzenia.
Przedmioty poprzedzające: Elementy logiki i teorii mnogości.
Literatura podstawowa:
- V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997.
- W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 1989.
- R. J. Wilson, Wstęp do teorii grafów, PWN, Warszawa 1998.
Literatura uzupełniająca:
- Z. Palka, A. Ruciński, Wykłady z Kombinatoryki, cz. 1, WNT, Warszawa 1998.
- W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986.
- R. Diestel, Graph Theory, Springer-Verlag 1997,2000,2005 http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.pdf
- http://users.utu.fi/harju/graphtheory/graphtheory.html