004. Малый ШАД - О дорогах и сетях - Владимир Протасов

Как соединить несколько точек на плоскости системой дорог наименьшей суммарной длины, если разрешается ставить сколько угодно дополнительных перекрестков? Эта задача решается в явном виде, причем для любого числа точек, с помощью вполне элементарной геометрической конструкции, известной со времен Ферма и Торричелли. Это тем более удивительно, что многие известные экстремальные задачи, которые выглядят значительно проще этой, не имеют столь ясных решений. Сети Штейнера — это объект, в котором школьная геометрия сходится с самой современной математикой (теорией графов, комбинаторной и дифференциальной геометрией, оптимизацией, теорией алгоритмов). В ходе лекции мы докажем, что именно сети Штейнера определяют кратчайшие системы дорог, научимся их строить, а также немного оглянемся вокруг и посмотрим на связанные задачи геометрии, теории экстремума и теории графов.