O kolorowaniu map i nie tylko map

W programie
Wykład O kolorowaniu map i nie tylko map.
Po wykładzie rozwiązywanie łamigłówek i zadań.

Prowadzący
dr Konstanty Junosza-Szaniawski

Czas i miejsce
13 marca 2010 r.
wykład - godz. 14.30, Gmach Główny PW - sala 134
warsztaty - godz. 16.00, Gmach Główny PW - sale 228, 306 i 309

Wykład
Problem kolorowania mapy, hipoteza 4 kolorów, rys historyczny. Definicja grafu, kolorowania grafu, liczby chromatycznej, definicja grafu planarnego, przykłady. Formuła Eulera wraz z wnioskami o ograniczeniu na liczbę krawędzi i minimalnym stopniu. Twierdzenie o 6 kolorach, twierdzenie o 5 kolorach, informacja o twierdzeniu o 4 kolorach.

Warsztat
Kolorowanie przykładowych map, grafów. Testowanie algorytmu zachłannego. Zadanie o szalonym kartografie i jeszcze bardziej szalonym kartografie. Twierdzenie o 4 kolorach dla ubogich. Twierdzenie o liczbie krawędzi i minimalnym stopniu w grafie planarnym bez trójkątów, twierdzenie o 4 kolorach dla grafów planarnych bez trójkątów. Gra w kolorowanie grafów.

Materiały

Zobacz plakat

Zdjęcia

Prezentacja z wykładu