Nowoczesna teoria grafów

RSS

Cel przedmiotu

Zapoznanie z wynikami teorii grafów i kombinatoryki, ze szczególnym uwzględnieniem tych, które mają zastosowania w informatyce. Opanowanie metod dowodzenia twierdzeń.

Program wykładu

Wybrane problemy kombinatoryczne. Przeliczanie. Zasada gołębnika, liczby Stirlinga. Zasada włączania i wyłączania. Funkcje tworzące. Rekurencje. Tw. Erdösa-Ko-Rado. Metody algebraiczne w kombinatoryce (miasta pzrzyste i nieparzyste). Grafy. Ścieżki i cykle Eulera, Grafy płaskie. Ścieżki i cykle Hamiltona. Grafy planarne, wzór Eulera i jego konsekwencje, bryły platońskie. Twierdzenie Kuratowskiego.Kolorowanie wierzchołków i krawędzi. Wielomiany chromatyczne. Drzewa. Drzewa ukorzenione. Przeszukiwanie wgłąb i wszerz. Centrum grafu. Tw. Koeniga. Poziom wierzch. w drzewie. Grafy ekstremalne. Twierdzenie Turána. Problem Zarankiewicza. Uogólnienia problemu Turana. Hipotezy Erdös–Sós. Pakowanie grafów. Hipotezy Gyárfása i Ringela. Teoria Ramseya. Optymalizacja. Złożoność obliczeniowa. Sieci. Algorytm Dijkstry najkrótszej ścieżki. Algorytmy Kruskala i Prima minimalnego drzewa rozpinającego. Twierdzenie maksymalnego przepływu i minimalnego przekroju. Związki z programowaniem liniowym. Teoria skojarzeń.

Charakterystyka pozostałych zajęć

Bibliografia

1. J.A. Bondy & U.S.R. Murty, Graph Theory, Springer 2008.
2. R. Diestel, Graph Theory, Springer, 2010.
3. R.P. Grimaldi, Discrete and Combinatorial Mathematics: Applied Intoduction, Addison–Wesley Publishing Comp., 1994
4. W. Lipski & W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986
5. K.A. Ross & Ch.R.B. Wright, Discrete Mathematics, Prentice Hall Inc. 1992 (polish edition: Matematyka dyskretna, PWN, Warszawa 1996)

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards