Wprowadzenie do teorii grafów 360-MS1-2ZTG
Wykład (WYK) Rok akademicki 2020/21

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 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. - kolokwium; obserwacja ciągła aktywności studenta na zajęciach.

Zna pojęcia drogi, cyklu, grafu eulerowskiego i hamiltonowskiego oraz podstawowe twierdzenia dotyczące tych zagadnień (Eulera, Orego, Diraca) oraz potrafi te twierdzenia zastosować do konkretnych przykładów i klas grafów. - kolokwium; 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.

Zaliczenie w formie zdalnej na platformie Blackboard. Z zaliczenia mogą być zwolnione osoby mające ocenę bardzo dobrą z ćwiczeń.

Treść zajęć:

Definicja i przykłady grafów, grafy regularne. Drogi i cykle. Spójność. Grafy eulerowskie. Grafy hamiltonowskie. Zagadnienie najkrótszej drogi. Cykle, cięcia, drzewa; matroidy grafowe. Wartości własne i wektory własne grafów. Grafy z wagami. Problem najkrótszych połączeń. Digrafy. Zagadnienia geometrycznej realizowalności grafów.

Metody dydaktyczne: wykłady, konsultacje, praca nad literaturą, dyskusje w grupach problemowych.