Literatura: |
Literatura obowiązkowa:
1) R. J. Wilson, Wprowadzenie do teorii grafów, PWN Warszawa 1998,
2) N. Deo, Teoria grafów i jej zastosowania w technice i informatyce, PWN Warszawa 1980
Literatura uzupełniająca:
1) R. Diestel, Graph Theory, Springer Verlag, 2000
2) Ch. Godsil, Algebraic Graph Theory, Springer 2001
|
Efekty uczenia się: |
Efekty kształcenia w ramach realizacji przedmiotu:
Zna podstawowe pojęcia teorii grafów; umie podać konkretne przykłady różnych poznanych typów grafów i wyznaczać ich parametry. - kolokwium zaliczeniowe; domowe prace rachunkowe/problemowe; prezentacje rozwiązań zadań na zajęciach.
Zna pojęcia drogi, cyklu, grafu eulerowskiego i hamiltonowskiego oraz podstawowe twierdzenia dotyczące tych zagadnień, potrafi te twierdzenia zastosować do konkretnych przykładów i klas grafów. - kolokwium zaliczeniowe; domowe prace rachunkowe/problemowe; prezentacje rozwiązań zadań na zajęciach; obserwacja ciągła aktywności studenta.
Uzyskuje podstawy metodologiczne do stosowania teorii grafów w zagadnieniach praktycznych i rozwiązywania jej elementarnych zagadnień - obserwacja ciągła aktywności studenta.
|
Zakres tematów: |
Treść zajęć:
Definicja i przykłady grafów: grafy proste, regularne, skierowane, nieskończone. Reprezentacja macierzowa i spójność. Drogi i cykle. Grafy eulerowskie i hamiltonowskie: algorytm Fleury'ego, warunki konieczne i wystarczające. Grafy z wagami: problem najkrótszych połączeń, problem chińskiego listonosza i komiwojażera. Drzewa - własności, zliczanie drzew i ich zastosowania. Grafy planarne i twierdzenie Eulera. Kolorowanie grafów, map i zagadnienie czterech barw. Grafy dualne. Twierdzenie Halla o kojarzeniu małżeństw.
|
Metody dydaktyczne: |
Metody dydaktyczne: dowodzenie prost(sz)ych zależności numerycznych i własności grafów i drzew, konsultacje, praca nad literaturą, rozwiązywanie zadań domowych, dyskusje w grupach problemowych.
|