5. Обобщение: проблема уличной сети.

В проблеме Штейнера были заданы три точки А, В, С. Было бы естественно обобщить эту проблему на случай заданных точек следующим образом: требуется найти в плоскости такую точку Р, чтобы сумма расстояний (где а; обозначает расстояние обращалась в минимум. (В случае четырех точек, расположенных так, как показано на рис. 215, в качестве Р нужно взять точку пересечения диагоналей четырехугольника пусть читатель проверит это в качестве упражнения.) Эта обобщенная проблема, также изученная Штейнером, не ведет к интересным результатам. В данном случае мы имеем дело с поверхностным обобщением, подобных которому немало встречается в математической литературе. Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, приходится отказаться от поисков одной единственной точки Р. Вместо того поставим задачей построить «уличную сеть» или «сеть дорог между данными деревнями», обладающую минимальной общей длиной. Точнее, даны точек требуется найти такую связную систему прямолинейных отрезков, чтобы: 1) любые две из данных

Рис. 215. Минимум суммы расстояний до четырех точек

точек могли быть связаны ломаной линией, стороны которой входили бы в состав системы, 2) общая длина всей системы была наименьшей.

Рис. 216-218. Кратчайшая система путей, соединяющих данные точки

Решение этой задачи имеет тот или иной вид в зависимости от расположения данных точек. Читатель с пользой сможет заняться более внимательным рассмотрением этого вопроса, исходя из проблемы Штейнера. Мы ограничимся здесь указанием результатов в типических примерах, изображенных на рис. 216-218. В первом примере решение дается системой из пяти отрезков с двумя «кратными точками», в которых сходятся по три сегмента, образуя между собой углы в 120°. Во втором примере число кратных точек равно трем. При некоторых иных расположениях данных точек указанные фигуры не получаются: возможны случаи «вырождения», когда какая-нибудь одна из данных точек (или несколько таких точек) становится сама «кратной точкой» сети — таков третий из приведенных примеров.

Рис. 219-220. Кратчайшие системы путей, соединяющие вершины квадрата

Если число данных точек равно то всего будет не более кратных точек, в которых сходятся по три отрезка, образуя углы в 120°.

Решение проблемы — не всегда единственное. Так, если четыре данные точки расположены в вершинах квадрата, то возникает два эквивалентных решения (рис. 219, 220). Если точки являются вершинами ломаной линии с углами при вершинах, достаточно близкими к 180°, то сама ломаная является решением.