MD Zaoczne2
Matematyka Dyskretna Studia ZaoczneLista 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
Zestaw 3 - Zasada wł-wył, grafy
Zestaw 4 - Spójność, obwód Eulera, cykl Hamiltona, kolorowanie
Zestaw 5 - Planarność
kolokwia z zeszłych lat
kolokwium 1 2007
kolokwium 2 2007
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