Догонялки в графе | Всеволод Афанасьев | Математический слэм
Пусть у нас есть граф, по которому передвигаются Пастух и Овца. Задача Пастуха – за какое-то количество ходов поймать Овцу (оказаться с ней в одной вершине), задача Овцы – каждый новый ход иметь возможность убежать (она ходит первой).
Как на исход противостояния влияют начальные условия, структура графа и какие существуют обобщения этой задачи рассказал Всеволод Афанасьев в рамках «Математического слэма».
Подписывайтесь на нас в соцсетях:
ТГ:
ВК:
Мероприятие прошло в гастро-баре 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 – концовка