Teoria grafów

Wiele sytuacji z życia codziennego można przedstawić za pomocą tak zwanych grafów – zbioru punktów (wierzchołków) na płaszczyźnie, których pewne pary są połączone liniami (krawędziami). W takim kontekście grafy pojawiają się coraz częściej, w szczególności używane są już na wczesnych etapach edukacji dzieci. Teoria grafów jest stosunkowo młodą dyscypliną matematyczną, za początek której przyjmuje się opublikowanie przez Eulera, tak zwanego problemu mostów Królewieckich w XVIII wieku. Ze względu na wiele naturalnych zastosowań oraz na związki z przeżywającą bardzo burzliwy rozwój w ostatnich dziesięcioleciach informatyką, podstawy teorii grafów powinny należeć do elementarnego kanonu wiedzy matematyka i informatyka. W czasie reklamowanego kursu będziemy budować teorię grafów wychodząc od oczywistych i prostych intuicji, narzucających się zastosowań i skojarzeń. Pozwala to na łatwe zapamiętanie i zrozumienie podstawowych pojęć i formalnej terminologii. Przykładowo będziemy wymazywać krawędzie i wierzchołki grafu by zrozumieć pojęcie jego podgrafu, czy też by badać jego siłę spójności. Będziemy spacerować po grafach by zdefiniować pojęcia spaceru, szlaku, ścieżki i cyklu. Zdefiniujemy las i drzewa tak by nie było wątpliwości, że las jest zbiorem drzew, a drzewo miało strukturę „drzewiastą”. Pokażemy jakie warunki muszą być spełnione by w czasie naszego spaceru po grafie możliwe było odwiedzenie każdego jego wierzchołka lub przejście przez każdą jego krawędź. Będziemy kojarzyć w pary wierzchołki grafu by móc w sposób optymalny przydzielać stanowiska pracy kompetentnym pracownikom. Kolorowanie wierzchołków i kolorowanie krawędzi grafu posłużą nam do rozwiązywania problemu rozłożenia dostawy środków chemicznych w pomieszczeniach magazynu i problemu układania planu zajęć. Poznamy warunki, przy których będziemy w stanie narysować graf na płaszczyźnie tak by jego krawędzie przecinały się tylko w wierzchołkach. Pokażemy własności takich grafów, z których między innymi dowiemy się jaki jest związek między liczbami wierzchołków, krawędzi i ścian wielościanu i ile kolorów potrzebujemy do pokolorowania mapy.

Mimo, że na wykładzie budujemy teorię grafów od podstaw, nie zabraknie ciekawych i czasami zaskakujących zastosowań innych działów matematyki, a kilka dowodów to „perełki” matematycznego rozumowania.