Algorytmiczna teoria grafów

Tematyka przedmiotu

• Wprowadzenie do podstawowych pojęć z teorii grafów
• Podstawowe klasy grafów
• Najkrótsze ścieżki/skojarzenia w grafie
• Minimalne drzewa spinające w grafach
• Grafy eulerowskie i hamiltonowskie
• Kolorowanie grafów
• Grafy planarne
• Problem maksymalnego przepływu w sieci

Literatura podstawowa

• G. Chartman, P. Zhang, A first course in Graph Theory, Dover Publications, New York, 2012.
• T. H. Cormen, Ch. E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, Wyd. Naukowe PWN, 2012.
• M. Kubale (ed.), Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT 2002.
• K. A. Ross, Ch. R. B. Wright Matematyka Dyskretna, Wyd. Naukowe PWN, 2000.
• A. Szepietowski, Matematyka dyskretna, Wyd. UG 2004.

                            Literatura uzupełniająca

• R.J. Wilson, Wprowadzenie do teorii grafów, Wyd. Naukowe PWN 2012.
• J. Wojciechowski, K. Pieńkosz, Grafy i sieci, Wyd. Naukowe PWN 2013.
• P. Wróblewski, Algorytmy, struktury danych i techniki programowania, Wyd. Helion, 2010.