Догонялки в графе | Всеволод Афанасьев | Математический слэм

Пусть у нас есть граф, по которому передвигаются Пастух и Овца. Задача Пастуха – за какое-то количество ходов поймать Овцу (оказаться с ней в одной вершине), задача Овцы – каждый новый ход иметь возможность убежать (она ходит первой). Как на исход противостояния влияют начальные условия, структура графа и какие существуют обобщения этой задачи рассказал Всеволод Афанасьев в рамках «Математического слэма». Подписывайтесь на нас в соцсетях: ТГ: ВК: Мероприятие прошло в гастро-баре Red Rabbit: , при поддержке Математического центра в Академгородке . 00:00 – вступление 00:49 – начало доклада и описание изначальной задачи 03:27 – решение задачи 04:36 – обобщение 06:04 – начальные условия для гарантированной победы каждой из сторон 09:24 – инвариант пастушьего графа, необходимые и достаточные условия пастушевости графа 11:52 – другие варианты задачи (Pursuit-evasion games) 12:57 – вопросы: 13:03 – об определении класса произвольного графа 14:06 – о переформулировке задачи для других видов графов и решёток 15:42 – вопрос про один из слайдов 16:55 – случай бесконечного графа 17:54 – случай направленных мультиграфов 18:49 – про начальные условия в исходной постановке задачи 19:51 – рассмотрение исходной задачи в бóльших размерностях и при бесконечном числе вершин; дифференциальные игры 21:31 – концовка