Grafy przejścia

29 września 2023
Kategoria: Festiwal Nauki w Warszawie, Nauka
495
Wykładowca: Festiwal Nauki

Wykład dr. Arkadiusza Męcla o grafach w ramach Festiwalu Nauki w Warszawie [24 września 2023]

Posłuchaj wykładu w formie podcastu:

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.

dr Arkadiusz Męcel – adiunkt w Instytucie Matematyki na Wydziale Matematyki Informatyki i Mechaniki Uniwersytetu Warszawskiego

Jeśli chcesz wspierać Wszechnicę w dalszym tworzeniu treści, organizowaniu kolejnych #rozmówWszechnicy, możesz:

1. Zostać Patronem Wszechnicy FWW w serwisie https://patronite.pl/wszechnicafww Przez portal Patronite możesz wesprzeć tworzenie cyklu #rozmowyWszechnicy nie tylko dobrym słowem, ale i finansowo. Będąc Patronką/Patronem wpłacasz regularne, comiesięczne kwoty na konto Wszechnicy, a my dzięki Twojemu wsparciu możemy dalej rozwijać naszą działalność. W ramach podziękowania mamy dla Was drobne nagrody.

2. Możesz wspierać nas, robiąc zakupy za pomocą serwisu Fanimani.pl – https://tiny.pl/wkwpk Jeżeli robisz zakupy w internecie, możesz nas bezpłatnie wspierać. Z każdego Twojego zakupu średnio 2,5% jego wartości trafi do Wszechnicy, jeśli zaczniesz korzystać z serwisu FaniMani.pl Ty nic nie dopłacasz!