Grafy przejścia
Grafy są obiektami, które łączą w sposób niezwykle efektowny świat zagadek i łamigłówek logicznych, oraz świat matematyki. Nawet najtęższe umysły uczonych uderza elegancja z jaką sformułować można w ich języku najbardziej skomplikowane nawet problemy. Począwszy od rozwiązania zagadnienia mostów w Królewcu przez Eulera w 1736 roku, przez problem komiwojażera, aż do budzącego liczne kontrowersje wspomaganego komputerowo dowodu twierdzenia o czterech barwach - grafy przeszły długą drogę inicjacji w świat pełnoprawnych i ważnych obiektów matematycznych badanych współcześnie przede wszystkim przez informatyków, a także fizyków, chemików, biologów, socjologów czy wszelkiej maści inżynierów. Grafy stanowią nie tylko ważny obiekt badawczy, ale też wygodne narzędzie do komunikowania problemów pomiędzy specjalistami z różnych dziedzin nauki. Również w świadomości osób pasjonujących się matematyką grafy stały się wdzięcznymi obiektami, ilustrującym układy znajomości, turnieje, konfiguracje geometryczne, a także niebanalne problemy wykonalności określonych konstrukcji lub procesów, na przykłady tytułowych przejść. Właśnie temu ostatniemu zagadnieniu przyjrzymy się w trakcie wykładu, posługując się zupełnie intuicyjną wersją pojęcia grafu. Motywacją naszych rozważań będzie następujący problem.
Dwóch wspinaczy porusza się po paśmie górskim. Czy jest możliwe, żeby obydwaj spotkali się na szczycie startując równocześnie odpowiednio z przeciwległych krańców tego pasma, by w każdym momencie wspinaczki znajdować się na tej samej wysokości? Problem ten ma, w zależności od dopuszczalnego poziomu skomplikowania kształtu pasma górskiego, bogatą literaturę. Podczas mojego wykładu zapoznamy się z wersją problemu pozwalającą na skorzystanie z metod teorii grafów.
Zanim przedyskutujemy to ciekawe zagadnienie i sprecyzujemy dokładnie po jakim paśmie górskim pozwolić chcemy naszym wspinaczom się poruszać, zilustrujemy pojęcie grafu przejścia na przykładach kilku prostych łamigłówek. Do zrozumienie wykładu nie jest potrzebna żadna wiedza, poza umiejętnością odróżniania liczb parzystych od nieparzystych. Pozwoli nam ona sformułować lemat o uściskach dłoni i zastosować go zbadania problemu równoległej wspinaczki.
