Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 3
Текст из файла (страница 3)
Решение задачи Ферма. Егли один из углов тре1тольнтсз 4ВС, скажем А, больше пли равен 120', то точка, нвляющалсн решением задачи Исторический обзор Рис. 5: Решение задачи Ферма Ферма, единственна и совпадает г вершиной А. Исти жг все углы треугольника ЛВС меньше 120', то рсшснис задали это внутренняя точка Н треугольника АЛС, совнадвюгцвя с точкой Торричелли = точкой пересечения линий Снмпсонгь что и определяет сс однозначно. В этом слу*ше все углы между отрезками НА, ЯВ н НС рваны между гобой и рввны!20'.
Лри этом линии Симпсона имеют одпнаковьгс длины, рваные >эА~+ НВ + >)НС~> рис. 5 Существует естественное обобщение задачи Ферма, а именно. Задача 2 (Об>обще>иная задача Фе>рма) Пиита на плоскости (в >1-,вернон нрострсгнстве) п>очку, сум.ио раш тонной оп> которой >)о и данных точек нао,испытая из возлозюныл. Обобщенная за,чача Ферма бы,щ сформулирована в виде упражнения в книге Симпсона 'г'!ггггопв'> и имсппо этой задачей из рагсматрнвасмой области проблем занимался 1!!теияер.
Друг ое обобщение задачи Ферма получается, если в качестве объекта, у которого ыггггимгггггвруе Гся длина, рассыат!эивагь произвольные сыпи, затягивающие данные множества точек. Именно такая постановка задачи была вьгдвннута 1!рникоъг и Кеес.гером н 1934 голу. Задача 3 !Ярник, Кесслер) Найти крат нгйшрю ссгпь, связывающую и >ганг>ми >почек, плоскости.
Ярняк и Кеес.гер регггглли постшзленпую проблему для граничных мно>ксств, образующих вершины правильных и-угольников при и = 3, 4, 5 и и > 13. 1!сгя г>, = 3, 4, 5 51рняк и Кесслер нашли очевидные абсолютно минигивльныс сети, а для и > !3 показали, что абсолютно минимачьная сеть состоит яз (и, — 1)-ой стороны рассматрьпгаемого праввлыкп о и-уг ольпвка. В работе этих авторов не было ссылок на Ферма, так как сама эта проблема, возможно, казалась им существенно другой. Заметим, что случаи Исторический обзор оставшихся п были разобраны лишь в работс ~17~ Ду, Хванга н Вонга !987 года, ч де оыло показано, что в в этих случаях ответ такой же, как н для чч ) !3.
Как мы учкс отметили выше, проблема Штейнера получила свое называние благодаря книге Куранта н Роббинса "ч1чно такое зчатсзчатикиУ", написаччной ими в 104! голу. Лвторы этой книги сформулировали описшчную выше задачу Ферма, позвав ее проблемой !Птейне!гц а затем поставили проблему Ярпнка и Кесслера как естественное обобщение проблемы Штсйнсра.
Ни на Форма, нн на !!рника и Кссслера ссылок сделано нс было. !!лагодаря огромной популярности книги, наэвшчие "проблема Штейнера' прочно вошло в лексикон математиков. Отметим, что книга Курапта и Роббинса породила це голько недоразумение в авторстве, но, что более важно, привлекла к проблеме Штейнера интерес большого числа ученых. В дальнейшем проблемой Штсйнсра занимались многие иэвсстпыс математики, см. [!] — ~4б~, такис как Гилберт, Грехем, Гэри, /!жопсоп, Ду, Кокчни, ч!елзчччч, Поллак, Рубвнпггчйн, Хванг и другие.
Ниже мы вкратцч опишем основные результаты, полученные в:чтой науке эа последние 40 лет. Псугасаяэщий интерес к проблеме Штейнсра объясняется нссколькнмп причина лп. Первая из ннх состоит в том, что, несмотря на простоту постановки, эта задача чрезвычайно нетривиальна. И хотя, как будет описано ниже, существует несложный а:и оритм построения кратчайшей сети, затягивающей даппос множесчтво из и точек плоскости, этот алгоритм связан с очень болыпим перебором воэкчочкччых тонологни сетей. В действителч,— ности, проблема Штсйнсра является учуР-полной, см.
~2Ц. Последнее означает, что, скорее всего, дла этой проблемы не сушествует полиномиальноч о а:и оритма, т.е. алгоритма, решающего задачу за время порядка не выше чем п", где й некоторое фиксированное число. Поэтому вахчной задачей является исследование разных геометрических ограничений, которые ччакладываются на сеть условием линимальности. Другая причина связана с тем, что у проблемы !Птейнера имеется много различных интерпретаций и приложений. Так, например, предположим, что возникла необходимое ьь соединить некоторые города системой дорог.
При этом жюительпо, чтобы .чат!иты на прокладку дорог были наименьшими возможными. Естественно. затраты пропорциональны сумме длин,дорог, т.е. длине искомой сети. В идеальном случае, когда па сеть больше не накладывается никаких ограничений (счча кч;и, отсутствуют препятспчня, ьч мы вольны прокладыва гь дороги там, где пожелаем), сеть дорог, минимизирующая затраты, является абсолютно минимальной сетью.
В приведенном только что примере можно заменить города на пункты потребления, а дороги на нефте илп газопроводы. В этом случае абсо,потяо минимальная сеть это ошснмалч,ная система нефте нлн газоснабжения. Если под пунктакчп А ч, Дз,..., 1а понихшть местонахождения абонснтов, а под абсолютно минимальной остью Г телефонную сеть, то мы получим модельную ситуацию, использующуюся в СШЛ при вычислс- Исторический обзор пнн федерюп,ных тарифов за междугородные телефонные разговоры. В :лом случае плата за раз~ овор абонентов, находящнхся в пунктах А, н А, пропорциональна длине минимального пути в телефонной сстн Г, соеднняющего А„с 4 .. Локально минпмальныс сетя можно наблюдать, рассматривая естественные природные образования. Скажем, если пренебречь высотой пчелиных сот, то получится локально мнннмальная сеть, построенная нз ществугольпнков с углами по 120'.
Таким образом, пчелы инстинктивно мнннмнзнруют количество воска, идущег о на постройпху сот. В слелующнх примерах локально мпннмальпые сети образуются в результате работы законов нсжнвой природы. Чтобы нагляднее представить себе механизм, можно проделать следуквпне эксперименты. В первом эксперименте нам понадобятся две прозрачныс пластины, например пластины вз плексигласа, набор металлических штырьков, а также таз с мыльным раствором влп раствором шампуня.
Эксперимент 1. Возьмем две прозрачные лластнны, раслоложнм нх в параллельных плоскостях на некотором расгтояннп:1руг от друга, н соеднннм нх между собой произвольным чнслом штырьков, перпендикулярных плоскостям, в которых пластяны лежат. Опуттям полученную ьонфпгураПню л зарансс прнготолленный мыльный рчствор н осторожно нзвле гсм ее нз раствора. На конфнгурапяв осядет мыльнал пленка,. перленднкулярпая пластннам (рис, 6). Граница полученной мыльной пленки состоят нз двух частей: первая часть гранины это обьедилецле цпырькол, соедннякт1нх лластняы, а вторая часть обьедннсннс двух одинаковых "следов", ло которымплснка касается пластвн. Еслн 6 рассгояннс между пластянамв, а 1 длина одного нэ 'следов', то плошадь мыльной пленки равна В!.
Хорошо нэвсстно, что мыльная пленка всегда стремятся занять такое положеняе, в кото!эом ее плхлцау!ь бело,те нельзя уменьшить беэ предварнтельного увелнченвя. Поэтому каждый нз "следов' является сетью, длину которой нельзя уменьшить малыми цесвсленнялш, оставляюшнмя на месте точки креллення штырькоь грштцу эгон сета. Сета, удоллегиоргпощие такому услолнго, л дсйствптельпоств являютсл локально минимальными. Следующий эксперимент представляет собой механическую реализацию минимальных остей.
Для него нам потребуется одна пластина, достаточно длинная леска н набор одинаковых по массе грузиков. Экспоримепт 2. разрежем леску на некоторое. чнсю настен. Это число обоэначвм через и. Выберем нэ и полученных отрезков лсскн и — 1, в на одном конце каждел о иэ выбранных отрезков завяжем неэатягнлаюн!уюся петельку. Иэ полученных и — 1-ого отрезка с петелькой выберсаг Й~ пттук, н через петельки проденем едтютиенняяй отрезок беэ петэн. Тем самым Исторический обзор 10 г-" ! Рис. 6: Мыльныс пленки, моделирующие локально минимальные сети Рис. 7: Механическая реализация локально минимальных сетей мы полу гим коггг1лггурагГггю, состояшуго из Йг + 1-ого отрезка я иягекггггуго й~ + 2 концов.
Далее, из оставшихся неэадействовшшыми отрезков выберем йз гггтук и проденем через их петельки концы построенной конфигурации. Тезг самым мы по гучим новую конфигурацию угкс с йг + йз + 2 копнами. Опятг из осташиихся отрезков выберем Аз и вновь перестроим коггфигураггггю. Будем ггродолгиать это процесс до тех пор, пока все отрезки нс будут заняты. В результате мы построклг конфигурациго С, число концов которой равно и+ 1.
11росвер.гим в пластине и + 1 маленьких сквозных отверстий, распологким пластину горизонтально я пропустим сверху коииь1 конфигурация С через отверстия так, чт ооы на кал дое из них приходилось по одному концу из С. 11рикрспим теперь к концам грузики одинакопоп массы. Когда полученная механическая система пряйдет в состояние равновесия, конфигурация из лески, в случае. если все петельки свободно разошлись мел;дк гобои, образует .локально ъгпнимальную сеть.
граница которой набор просверленных отверстий, ряс. 7. Лбсошотно минимальные сети 2 Основные результаты теории абсолютно минимальных сетей Приведем теперь основные результаты, посвященныс исследованию абсолютно минимальных деревьев. Пусть ЛХ = ! ЛХ;) фиксированное множество, состоящее из и точек плоскости. Первые естественные вопросы рассматриваемой теории это теоремы существования и единственности абсолютно минимальных деревьев, затягивающих ЛХ. Как было отмечено выше, всегда существует абсолютно мипимап,нос дерево.
затягившощее ЛХ, однако, вообьце говоря, такое дерево не единственно, см. рис. 1. Кроме того, вьппс мы описали локальное устройство локально минимальных, а, значит, и абсолютно минимазп,ных сетей. А именно, каждая абсо.потно минимальная сеть состоит из отрезков. стыкуюп1ихся в вершинах под углами, не превосходящими 120'. В частности, степени вершин локально минимальной сети не превосходят 3, поэтому такие сети являются сетями П!тсйнсра. Более того, можно считать, что все вершины степени ! и 2 являются граничными, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
