ELEMENTY TEORII GRAFÓW

podstawowy

specjalistyczny

algebra liniowa, wstęp do matematyki

Głównym celem wykładu jest pokazanie licznych zastosowań teorii grafów. Wykład zawiera klasyczne zagadnienia teorii grafów i ich zastosowania do rozmaitych problemów z zakresu zarządzania i ekonomii.

1. Podstawowe definicje teorii grafów.

2. Przykłady grafów.

3. Poruszanie się po grafach; problem najkrótszej drogi.

4. Grafy eulerowskie i półeulerowskie; problem chińskiego listonosza.

5. Drzewa i lasy; problem minimalnych połączeń, problem zliczania izomerów.

6. Grafy hamiltonowski i półhamiltonowskie; problem komiwojażera.

7. Grafy planarne.

8. Grafy geometrycznie dualne.

9. Kolorowanie grafów; problem przechowywania chemikaliów.

10. Skojarzenia; problem kojarzenia małżeństw, problem harmonogramu zajęć.

11. Transwersale i matroidy; problem kwadratów łacińskich.

12. Grafy skierowane; problem dróg jednokierunkowych, problem rankingu zawodników w turnieju, problem drogi krytycznej.

13. Sieci zdarzeń.

1. C. Berge, Graphs, North-Holland Mathematical Library, 6-1, North-Holland Publishing Co., Amsterdam, 1991.

2. J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008.

3. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.

4. R. Diestel, Graph Theory, Graduate Texts in Mathematics, 173, Springer, Heidelberg, 2005.

5. F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. Series, Computer Science Press, Inc., Woodland Hills, Calif., 1979.

6. O. Ore, Graphs and Their Uses, Edited and with an introduction by Robin J. Wilson, New Mathematical Library, 34, Mathematical Association of America, Washington, DC, 1990.

7. R.J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 2007.

Uczestnik kursu pozna podstawowe technikami stosowane w teorii grafów. Nabędzie umiejętność opisu rozmaitych problemów z zakresu zarządzania i ekonomii w języku tej teorii. Będzie mógł stosować poznane algorytmy i techniki do rozwiązywania opisanych i pokrewnych problemów.

1. Zaliczenie laboratorium: Dwa sprawdziany, za które można uzyskać łącznie 50 punktów i bieżąca ocena aktywności za którą można uzyskać łącznie 20 punktów. Skala ocen na zaliczenie laboratorium:

0 – 29 punktów = niedostateczny

30 – 39 punktów = dostateczny

40 – 47 punktów = plus dostateczny

48 – 55 punktów = dobry

56 – 63 punktów = plus dobry

64 – 70 punktów = bardzo dobry

2. Zaliczenie egzaminu: Zaliczenia na ocenę co najmniej dobrą z laboratorium są premiowane analogicznym zaliczeniem egzaminu. Pozostałe osoby oraz te, które są chcą poprawić oceny przystępują do egzaminu pisemnego.

3. Ocena końcowa: Średnia ważona z poszczególnych sposobów weryfikacji efektów kształcenia:

aktywność na zajęciach i sprawdziany pisemne – 50%

egzamin – 50%