April 3, 16.00
Public lecture (in Czech) by Martin Loebl
organised by the Learned Society of the Czech Republic, Národní 1009/3, Prague 1.
Chtěl bych vyprávět několik příběhů hledání cest. Začnu Eulerovým pozorováním o procházení hran grafu uzavřenou procházkou. Tento příběh pokračuje úvodem do teorie složitosti algoritmů a příběhem obchodního cestujícího. Pokračujeme potom problémem existence krátkých cyklů směrem k problému zimní údržby silnic, odkud se přirozeně dostaneme k hypotéze o vnořování grafů na pseudoplochy, známé jako „directed cycle double cover conjecture“. Potom se vrátíme se k Eulerovu pozorování ukázáním souvislostí s Isingovým problémem z oblasti statistické fyziky. Dalším příběhem, pokud čas dovolí, bude příběh Borůvkovy elektrifikace Moravy.
Posted on 2019-04-10