Grafy przejścia
- 29 września 2023
- Kategoria: Festiwal Nauki w Warszawie, Nauka
- 980
- 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!
Playlista: Festiwal Nauki w Warszawie
- Awaria elektrowni jądrowej w Fukushimie
- Finanse świata
- Czego boimy się bardziej: ciemności czy promieniowania?
- Wszystko, co chcielibyscie wiedziec o Hollywood
- Maria Skłodowska-Curie: znaczenie naukowe jej badań
- Wszystko, co chcielibyście wiedzieć o prezydencie USA
- Czy polska agresja w życiu publicznym jest czymś wyjątkowym?
- Dwie Polski, a może więcej?
- Otwarcie XVI Festiwalu Nauki w Warszawie
- Alergia wczoraj i dziś
- W poszukiwaniu nowej Ziemi
- Polska-Rosja-Świat
- Krótka historia naukowa globalnego ocieplenia
- Komórki macierzyste: między lekiem a nadzieją
- Janusz Korczak. Wychowanie jako "rzeźbienie dusz"
- Jak schudnąć nie tracąc zdrowia?
- Disruptive technologies – technologie, które zmieniają świat
- Czarnobyl po ćwierćwieczu
- Wielkie wpadki nauki
- Kręgosłup - jego mechanika i funkcja
- Kiedy najlepiej zacząć oszczędzać na emeryturę?
- Rejbaki, kartacze, parepace czyli o słownictwie kulinarnym w gwarach Mazowsza i Podlasia
- Zlodowacenia i ich ślady na Ziemi
- Po co Polakom Polska?
- Rozpoczęcie XVII Festiwalu Nauki w Warszawie
- Gaz w łupkach – szanse i obawy
- Fanfiki, fanvidy i fansuby - co może fan w sieci?
- Dlaczego warto znać strukturę DNA?
- Nadzieja z probówki, czyli o zapłodnieniu in vitro
- Geometrie nieeuklidesowe
- Co się dzieje, gdy grawitacja przestaje działać?
- Izaak Newton i prawo powszechnego ciążenia
- Jaskinie, wulkany i inne skalne osobliwości Dolnego Śląska
- Globalne ocieplenie, topniejące lody Arktyki i długa zima w Polsce. Czy jest związek?
- Ze skórką czy bez, czyli co wyrzucamy obierając owoce.
- Bić się czy nie bić? Powstanie styczniowe i nie tylko
- Modyfikacje molekularne w biologii i medycynie
- Trzęsienia ziemi i tsunami
- Sekrety „Władcy Pierścieni", czyli o pożytkach z opowiadania bajek i wymyślania języków
- Czy rośliny się stresują?
- Jan Czochralski - przywracanie pamięci i dokonań naukowych
- Kapitał społeczny – czy konieczny czynnik budowania lepszej Polski?
- European dream vs. American dream - czy marzenie europejskie zastępuje amerykańskie?
- Czy świat realny jest poznawalny?
- Jak znaleźć ekstremum funkcji?
- Margaret Thatcher (1925-2013) - portret polityka. Prof. Piotr Jachowicz
- Zielona energia. Czy bez niej możliwy jest dalszy rozwój naszej cywilizacji?
- Bagno wciąga
- Ale ja się głupio zakochałem! Dr Wojciech Kulesza
- Wszechświat - prosty czy złożony? Debata S.Bajtlik, M.Demiański, K.Meissner
- Mity w żywieniu człowieka. Dr hab. Małgorzata Drywień
- I wojna światowa - zapomniana wojna Polaków
- Żywienie człowieka dawniej i dziś
- Prawda i mity na temat kosmetyków. Wykład Katarzyny Pytkowskiej
- Stereotypy związane z konsumpcją żywności i zdrowiem. Wykład Marzeny Jeżewskiej-Zychowicz
- Znikający Polak. Debata inaugurująca XIX Festiwal Nauki w Warszawie
- Świat komórek macierzystych
- Po co komu matematyka?
- Mord rytualny - długie życie legendy
- Mięso z probówki - jak zrobić hamburgera w laboratorium?
- Być przyzwoitym w XXI wieku. Sesja poświęcona prof. W. Bartoszewskiemu
- Czy pamięć jest w głowach czy pomiędzy ludźmi?
- Alan Turing, czyli o myślących komputerach
- Skąd się bierze prognoza pogody? Modelowanie numeryczne prognoz
- Umysł przeciwko materii. Jak kryptolodzy zmieniali losy świata
- 100-lecie teorii względności - teoria, astrofizyka, praktyka
- Fale grawitacyjne - największe odkrycie XX wieku?
- Październik 1956 - najważniejszy przełom w historii PRL
- Spór o początki państwa polskiego
- Meandry redystrybucji - czym się kierować tworząc system ulg i świadczeń
- Czy jesteśmy właścicielami naszych ciał?
- Mars - badania, plany, nadzieje
- Historia świata według roślin
- Ile kultury w gospodarce, ile gospodarki w kulturze?
- Jak powstaje nowotwór?
- Choroba Alzheimera, problem pacjenta i rodziny
- Śladami dinozaurów od Tatr do Bałtyku
- Komety - wyprawa do granic Układu Słonecznego
- Geometryczne piękno wszechświata
- Migracja - asymiliacje i odrzucenia, swoi i obcy
- Wskaźniki, Głupcze!
- Prawda, kłamstwo, fake news
- O nietypowych kształtach i niesfornych liczbach
- Uwaga kleszcze!
- Puszcza Białowieska - ostatni taki las
- W imieniu Rzeczypospolitej Polskiej skazuję robota J[...]S[...] na karę śmierci
- Czy robot zabierze ci pracę?
- Problemy aerodynamiczne szybkiego transportu – HyperloopPoland
- Przemoc szkolna jako zjawisko grupowe
- Istota świadomości
- Prawda historyczna: Jak unikać fałszu
- Zwierzęta, które zmieniły bieg historii
- Edycja genów - rewolucja w biologii
- Czy neuronauka zdetronizuje psychologię?
- Polska, ale czyja? / Debata o II Rzeczpospolitej
- Czy istnieją granice wolności badań?
- (Nie)pokoje 1918-1923. Trudne narodziny nowego świata
- Jakie wiatry wieją z czarnych dziur?
- Globalne ocieplenie - różne perspektywy
- Więcej niż samolubny gen – gen w dialogu ze środowiskiem
- Największe afery sportowe podczas olimpiad, mundiali i turniejów
- Skąd wiemy, że istnieją ogólne prawa przyrody?
- Antybiotyki - historia odkrycia, mechanizm działania, wpływ na organizm człowieka
- Mózg prawdziwy i sztuczny
- Bitcoin i inni. Kryptografia a kryptowaluty
- Badania na zwierzętach jako motor nauki
- Chiny innowacyjne – mocarstwo wiedzy
- Automatyzacja, robotyzacja, sztuczna inteligencja: obawy i obietnice
- Ratowanie ginących języków: od teorii do praktyki
- Instrukcja nadużycia. Historia kobiet służących w XIX-wiecznych domach
- Nauka w walce z przestępczością
- Bieda w państwie miliardera: o ubóstwie w USA
- Początek zmian – Okrągły Stół w oczach uczestników
- Człowiek i dieta, czyli zwyczaje żywieniowe okiem biologia ewolucyjnego
- Kto tu rządził? Kto tu rządzi? Kształtowanie się trójpodziału władzy po II wojnie światowej
- Metamateriały
- Miejsca pamięci współczesnej Chorwacji i Serbii
- Trucizny w "Grze o tron"
- Jak działa czarna dziura?
- Czego mogą się o nas dowiedzieć firmy technologiczne?
- Czego jeszcze nie wiemy o neutrinach?
- Ludowa historia Polski
- Irlandii zawiłe drogi do niepodległości
- Podziały polityczne Polaków w XX wieku
- Czy nauka może przekroczyć samą siebie?
- Proces starzenia i możliwość jego odwrócenia
- Czy rata mojego kredytu nie jest za wysoka?
- Stare chwyty, nowe metody - jak wykorzystać sztuczną inteligencję
- Polecimy na marsa?
- Jaka będzie następna pandemia, czyli co nadejdzie po COVID-19?
- Orzeszkowa, złote runo i hejterzy. Sprawa „Argonautów” (1898-1899)
- Prus jako fotograf, Prus na fotografii
- Wierna adaptacja? Różnice między filmem "Rok 1863" i powieścią "Wierna rzeka" Stefana Żeromskiego
- Największa znana liczba?
- Grafy przejścia
- Media społecznie (nie)odpowiedzialne? Debata o współczesnych środkach przekazu
- Rosyjski neofaszyzm XXI wieku – genologia i symptomy choroby
- Populizm – czym jest i skąd się bierze? - debata Festiwalu Nauki
- Podkop pod przekop. Dzieje idei kanału przez Mierzeję Wiślaną
- Żywność 4.0 – co będą jeść nasze wnuki
- Robotyka medyczna – rozwiązania dla przyszłości
- O uwarunkowaniach orientacji seksualnej i tożsamości płciowej - debata Festiwalu Nauki w Warszawie
- W krainie Snake'a
- Zagadka niebytu
- Jakiej energii potrzebujemy? - debata XXVI Festiwalu Nauki
- Zarządzanie ryzykiem klimatycznym oraz edukacja klimatyczna
- Nierozwiązane problemy współczesnej fizyki
- Wojna 1920 roku nieoczywistości niespójności niekonsekwencje - debata Festiwalu Nauki
- Romantyzm, młodość, rewolucja: co łączy Mickiewicza i hippiesów?
- Stoicyzm wczoraj i dziś. Dlaczego filozofia starożytnych stoików tak bardzo przydaje się nam w XXI wieku?
- Spotkanie Noblowskie Festiwalu Nauki w Warszawie 2021 r.
- Polityka historyczna – czym jest i jaka powinna być
- Między feminizmem a uniwersalizmem. Status i uzasadnienia postulatów równościowych
- Czy żyjemy coraz dłużej?
- Intencjonalność. O czym myślę i co zamierzam
- Ukraina, Rosja, Polska - historia, teraźniejszość, przyszłość
- Przemysł 4.0 - nowe wyzwania w świecie zmian - debata Festiwalu Nauki
- Dlaczego lew jest groźny?
- Hipoteza Keplera: układanie pomarańczy i dowody wspierane komputerowo
- Tyrania większości: Jak budżet partycypacyjny w Polsce dyskryminuje mniejszość
- Wycieczka po geometriach nieeuklidesowych
- Zajrzeć w czwarty wymiar
- Kiedy granie w gry komputerowe staje się problemem? Granica między przyjemnością a uzależnieniem
- Ruszamy w świat, czyli o tym jak wyznaczyć najlepszą trasę podróży
- Błądzenie losowe: powroty i spotkania
- Twierdzenie Banacha i mapy
- Spacer wśród wysokich drzew
- Bo w tym cały jest ambaras, kiedy dwoje zmienia naraz
- Wspólnie czy obok siebie Żydzi na ziemiach polskich i w Polsce w pierwszej połowie XX w - debata Festiwalu Nauki
- O popularyzacji nauki, kawiarniach naukowych i festiwalach nauki
- Neutralność klimatyczna - paląca sprawa
- Falujące społeczeństwo obywatelskie
- Kwadratura kwadratu
- O niczym, czyli o paradoksach
- To samo, czy nie to samo?
- Jak różne mogą być dowody jednego twierdzenia z kombinatoryki
- Efektywny altruizm, czyli naukowe podejście do pomagania
- Jak wymieniać się nerkami i innymi przedmiotami
- Biologia wśród gwiazd – czym zajmują się astrobiolodzy?
- Życie na Ziemi - od początku do końca
- Czy uczony jest artystą? Jaka jest relacja między nauką a sztuką?
- Lot ptaków i owadów