Hledání cest jako problém v diskrétní matematice

Učená společnost České republiky
Vloženo: 14. 04. 2019

23. 04. 2019 - 16:00

Cena: Zdarma

Kapacita: 8/80

Přednášející: Prof. RNDr. Martin Loebl, CSc., MFF UK

Kraj: Praha

Adresa: Akademie věd ČR, Národní 3, Praha 1
Místo: místnost 206 (v případě velkého zájmu přenos do 205)

Detailní informace o místě konání se zobrazí pouze pro zúčastněné.

Kategorie: Lékařství a přírodní vědy

URL odkaz: https://learned.cz/cz/co-je-noveho/aktuality/pozvanka-na-verejnou-prednasku-ucene-spolecnosti.html

Přednáška matematika z Matematicko-fyzikální fakulty UK a člena Učené společnosti ČR
Anotace: 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 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.

Komentáře