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

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