Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

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

В проблеме Штейнера были заданы три точки А, В, С. Было бы естественно обобщить эту проблему на случай n заданных точек А1, A2, ..., Аn следующим образом: требуется найти в плоскости такую точку Р, чтобы сумма расстояний а1 + а2 + ... + аn (где аi обозначает расстояние РАi) обращалась в минимум. (В случае четырех точек, расположенных так, как показано на рис. 215, в качестве Р нужно взять точку пересечения диагоналей четырехугольника А1А2, A3A4; пусть читатель проверит это в качестве упражнения.) Эта обобщенная проблема, также изученная Штейнером, не ведет к интересным результатам. В данном случае мы имеем дело с поверхностным обобщением, подобных которому немало встречается в математической литературе. Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, приходится отказаться от поисков одной-единственной точки Р. Вместо того поставим задачей построить "уличную сеть" или "сеть дорог между данными деревнями", обладающую минимальной общей длиной. Точнее, даны n точек А1, A2, ..., Аn требуется найти такую связную систему прямолинейных отрезков, чтобы: 1) любые две из данных точек могли быть связаны ломаной линией, стороны которой входили бы в состав системы, 2) общая длина всей системы была наименьшей*.

* (Выработка общих методов для решения прикладных задач типа описанной составила в последние годы предмет так называемого линейного программирования; см., например, [45].)

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

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

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

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

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

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

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Зачем математики ищут простые числа с миллионами знаков?

Задача построения новых оснований математики - унивалентные основания

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru