Задачи о раскрасках. Андрей Райгородский
Задача о раскрасках. Андрей Райгородский
Можно ли любую карту мира покрасить в 4 цвета так, чтобы соседние страны были разного цвета? Над этой задачей математики бились 124 года — и решили её только с помощью компьютера. Андрей Райгородский рассказывает о проблеме четырёх красок, теории графов и её неожиданных приложениях — от оптимизации производства до моделирования интернета.
❤️ Отблагодарить лектора и поддержать предложенный фонд вы можете по ссылке: fund.mipt.ru/capitals/ck6/
⏱️ ТАЙМКОДЫ:
0:00 Вступление, о конференции
2:15 Начало лекции
4:53 Проблема четырёх красок
10:34 Анклавы и эксклавы — когда 4 цветов не хватит
17:12 Что такое граф
23:01 История задачи: от Гатри до Аппеля и Хакена
31:26 Приложения: интернет, соцсети, оптимизация
38:14 Хроматическое число
43:48 Почему задача алгоритмически сложная
47:08 Жадный алгоритм раскраски
54:46 Завершение
56:22 Вопросы и ответы
🐡 А если до 1 января пришлете чек с донейшеном в форму по ссылке: https://forms.gle/i2RGYRK8Yax6C6kg8 -получится месяц(!) бесплатного обучения математики с 0!