Геометрические свойства локально минимальных сетей (1097521), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

1 Исторический обзор Понятие локально минимальной сети впервые неявным образом появилось при изучонии следующей классической задачи, известной в литературе как проблема Штейнера; среди всех сетей [свлзных одномерных континуумов), затлгиваюи1их данное конечное множество М точек плоскости, найти сеть наименьшей длины. Эта задача была названа "проблемой Штейнера" в замечательной книге Ричарда Куранта и Герберта Е.

Роббинса ч'Хто такое математикар" в честь Якоба Штайнера [ЛасоЬ Бхс1пег, 1796 1863), швейцарского математика, профессора Берлинского университета. Именно после появления этой очень популярной книги интерес к абсолютно минимальным сетям разгорелся с новой силой, и терминология, предложенная 1(урантом и Роббинсом стала общепринятой. Следует отметить, однако, что сама задача о поиске абсолютно минимальных сетей имеет более длинную историю.

Мы проследим ее здесь, воспользовавшись историческими обзорами в [88), [62), [37) и [34). 1. Исторический обзор. По-видимому, впервые задача такого типа была поставлена Ферма (1601 -1665) до 1640 года. А именно, Ферма интересовал ответ на следующий вопрос: как расположить на плоскости точку Е так, чтобы сумма расстояний от нее до трех фиксироаанныв точек Аы Аа и Аз была наимсньтсйр Торричелли предложил геометрическое решение этой задачи.

Построим на сторонах заданного треугольника А1АвАз вне его три правильных треугольника и опишем вокруг них окружности. Тогда, как показал Торричеяли, построенные три окружности пересекутся в одной точке Т,которая известна теперь в планиметрии как точка Торричелли, см. рис.

1. Торричелли утверждал, что Г = Т, т.е, эта точка Т и является решением задачи, поставленной Ферма. Однако, заметим, Торричелли ошибся: его рассуждения справедливы только в предположении, что все углы треугольника А1АзАз не превосходят 120'. Если же один иэ этих углов, скажем угол Ам больше 120', то, как легко видеть, точка Торричелли лежит вне треугольника Аь.4вАз и не минимизирует суммарное расстояние до вершин треугольника. В этом случае, как независимо заметили Хейнен (в 1834 году) и, позднее, Бертран (в 1853 году), искомой точкой является вершина .4г Рис. 1: Точка Торричелли.

Вернемся в ХЪ'П век. В 1647 году выходит книга Кавальери ьЕхссгсг$аНопсэ Ссотс1ггсас', в которой отмечается важное свойство точки Торричелли Т, в предположении, что эта точка лежит внутри треугольника А1АзАз. все углы между отрезками А,Т равны между собой и равны 120'. Этот факт оказывается весьма фундаментальным, и его аналоги, как мы увидим, имеют место в существенно более общих ситуациях. В середине следуя>щего столетия,в 1750 году,в своей книге "Рос1ппе апа' Арр11саБоп о1 Ейис11опя" Симпсон предложил другой способ построения точки Торричелли.

Конструкция Симпсона состоит в следующем. Снова построим на сторонах треугольника А~ 4зАз и вне Введение. его правильные треугольники. Объединение каждого из построенных нами треугольников с исходным треугольником А~ Аз.4з представляет собои четырехугольник, одна из диагоналей которого совпадает с соответствующей стороной треугольника А~АзАз. Проведем недостающие диагонали.

Три построенных отрезка называются теперь линиями Симпсона. Симпсон показал, что эти отрезки или их продолжения пересекаются в одной точке, совпадающей с точкой Торричелли, рис. 2. Аз Рис. 2; Линии Симпсона пересекаются в точкс Торричелли. Уже в Х1Х веке, в 1834 году, Хейнен показал, что если точка Торричелли лежит внутри треугольника А~АзАз, то длины всех трех линий Симпсона равны между собой и равны сумме расстояний от точки Торричелли до вершин треугольника. Таким образом, собирая воедино все сказанное выше, мы получаем следующий полный ответ на поставленную Ферма задачу.

Решение задачи Ферма. Точка Е, являющаясярешением задачи Ферма, единственна. Если один из углов треугольника А~ Авда, скажем Аы больше или равен 120', то Г = Аы Если же все углы треугольника А~АзАз меньше 120', то Е совпадает с точкой Торричелли. В этом случае все углы между отрезками Я.4, равны между собой и равны 120'. При этом линии Симпсона имеют одинаковыс длины, раиныс ~5А~ ~ + ~ЯАз ~ + ~ЯАз~. Симпсон предложил следующее обобщение задачи Ферма: найти на плоскости (в И-мерном пространстве) точку 5, сумма расстояний от которой до п данных точек наименьшая из возможных. Отметим, что эта задача отличается от сформулированной выше проблемы Штейнера, так как в задаче Симпсона рассматриваются не все возможные сети, затягивающие данное множество М, а лишь сети, имеющие ровно одну дополнительную вершину вершину 5.

Одним из вариантов задачи Симпсона занимался Якоб Штейнер. 1. Исторический обзор. Другое обобщение задачи Ферма получается, если в качестве объекта, у которого минимизируется длина, рассматривать произвольные сети, затягивающие данные множества точек. Впервые случай 4 и 5 точек рассматривался в работах французских математиков )Кергонна, Клайперона и Ламе, а также в письмах Гаусса. Наконец, в 1934 году Ярник и Кесслер поставили задачу в следующем современном виде: найти кратчайшую сеть, свлзываю~цую и данных точек плоскости.

Ярник и Кесслер решили поставленную проблему для граничных множеств, образующих вершины правильных и;угольников при п = 3, 4, 5 и и > 13. Для и = 3, 4, 5 Ярник и Кесслер нашли очевидные абсолютно миниьпмзьные сети, а для и > 13 показали, что абсолютно минимальная сеть состоит из Сп — ц-ой стороны рассматриваемого правильного и-угольника. В работе этих авторов не было ссылок на Ферма, так как им, по-видимому, казалось, что они занимшотся совсем другой задачей.

Переписка Гаусса и работы французских математиков им также не были известны. Заметим, кстати, что случаи оставшихся а были разобраны лишь в работе [2Ц Ду, Хванга и Венга 1987 года, где было показано, что и в этих случаях ответ такой же, как и для и > 13. Как мы уже отметили выше, проблема Штейнера получила свое называние благодаря книге Еуранта и Роббинса "Что такое математикар", написанной ими в 1941 году. Авторы этой книги сформулировали описанную выше задачу Ферма, назвав ее проблемой Штейнера, а затем поставили проблелеу Ярника и Кестяера как естественное обобщение проблемы Штейнера. Ни на Ферма, ни на Ярника и Кесслера ссылок сделано не было. Как уже отмечалось, благодаря огромной популярности книги, терминология, связанная с именем Штеинера, стала в этом контексте общепринятой.

Отметим, что книга Куранта и Роббинса породила не только недоразумение в вопросах приоритета, но, что гораздо более важно, привлекла к проблеме поиска минимальных сетей интерес большого числа ученых, В дальнейшем проблемой Штейнера занимались многие известные математики, такие как Винтер, Гилберт, Грехем, Гэри, Джонсон. Ду, Кокейн, Мелзак, Поллак, Рубинштейн, Томас, Хванг и друтие.

Ниже мы вкратце опишем основные результаты, полученные в этой науке за последние 40 лет. Одна из причин этого неослабевающего интереса специалистов к минимальным сетям состоит в том, что у проблемы Штейнера имеется много различных интерпретаций и приложений. Например, очевидно, заданное конечное множество ЛХ можно интерпретировать как набор конечных (терминальных) пунктов. Тогда минимальная сеть это самая дешевая транспортная система, обеспечивающая коммуникации между данными конечными пунктами. Введение. Здесь естественно предполагается,что стоимость коммуникаций пропорциональна их длине.

Отметим здесь же, что в реальных задачах часто встречаются ситуации, когда коэффициент пропорпиональности между стоимостью отдельного участка транспортной сети и длиной этого участка зависит от конкретного участка сети. В этом случае естественно определить взвешенную Олину сети как линейную комбинацию длин ребер сети с некоторыми положительными коэффициентами (для каждого ребра фиксирован свой коэффициент.

называемый весом этого ребра). Отметим что в этом случае топология сети предполагается фиксированной. Сети, для ребер которых фиксированы веса, будем называть взвешенными. На случай взвешенных сетей естественным образом переносятся понятия абсолютно минимальных и локально минимальных сетей (в смысле взвешенной длины), см. [46]. Изешиенныс минвмильные сеши так же изучаются в данной работе. Оказывается, что многие результаты, справедливые для обычных локально минимальных сетей обобщаются на случай взвешенных локально минимальных сетей. Локально минимальные сети можно наблюдать в несложных физических экспериментах, описанных ниже, а так же в живой природе. Скажем, если пренебречь высотой пчелиных сот,. то получится локально минимальная сеть, построенная из шестиугольников с углами по 120'. Таким образоьц пчелы, повинуясь инстинкту, уменьшают количество воска, идущего на постройку сот.

Характеристики

Список файлов диссертации