Cel kursu:

Celem kursu jest wprowadzanie uczniów w świat grafów i zapoznanie ich z praktycznymi zastosowaniami teorii grafów.

Opis kursu:

Dawno temu Leonard Euler, jadąc do Petersburga, zatrzymał się po drodze w Królewcu. Tam zainteresował go problem, nad którym, jak wieść niesie, głowili się mieszkańcy tego miasta: czy da się przespacerować po Królewcu tak, aby każdy z jego siedmiu mostów przejść dokładnie raz? Euler podszedł do zadania poważnie i zamiast rozwiązać tylko ten konkretny problem, dziesięć lat później opublikował referat naukowy, w którym dał dokładny wywód dlaczego takiego spaceru nie da się odbyć, a przy okazji zapoczątkował nowy dział matematyki, zwany dziś teorią grafów.

W trakcie kursu zapoznamy się z podstawowymi rodzajami grafów i ich własnościami, przeanalizujemy klasyczne problemy chińskiego listonosza i komiwojażera oraz zaznajomimy się z najróżniejszymi zastosowaniami teorii grafów, np. jak zaprojektować sieć komputerową, aby działała optymalnie, jak wykorzystać kolorowanie grafów do układania planu lekcji w szkole, jak zaplanować trasę odśnieżarek miejskich, aby praca była wykonana szybko i minimalnym kosztem, jak przygotować plan wycieczki objazdowej, aby zwiedzić jak najwięcej w danym czasie.