Главная » Просмотр файлов » Классификация локально минимальных плоских сетей с выпуклыми границами

Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 13

Файл №1097579 Классификация локально минимальных плоских сетей с выпуклыми границами (Классификация локально минимальных плоских сетей с выпуклыми границами) 13 страницаКлассификация локально минимальных плоских сетей с выпуклыми границами (1097579) страница 132019-03-13СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Поясггггзг, что значит "локальная сеть с центром н Р является абсо,потно мггггггьгаггьггои". Пыше мы определили каноническую границу локальной сети. Рассола грим образ этой канонической границы. Получим некоторое подмножество г1Х плоскости Дз. Так вот, абсолютная минимальность рассматриваемой локальной сети означает, что эта сеть имеет наимсцыпую длину среди всех измерп лых сетей.

затягивагоших ЛГ. В дальнейшем основное гзниманяе будет уделяться лишь локально мглнилальны л сетязгг поэтому, для краткости. будем называть их просто, минимщгьными, опуская слово "локвлыгыи '. Локальное устройство минимальных остей 4 Локальное устройство минимальных сетей В силу определения, локальное устройство абсолютно минимальных н локально минимальных остей одинаково. Следующая теорема полностью описывает локальное устроиство минимальных сетей, н гиохьет, с небольшими изменениями формулировки, быть обобщена на случай сетей в произвольном римановом многообргзип, см.

[53) и Введение настоящей диссертации. Предложение 1.1 (Локальная структура минимальных сотой) Лг меримая стиь Г с границей Л! .иинимаяьна, если и тоьько если имеют место следуюи)ие свойсп~ва: ° все ребра сети прямо ьинейные отрезки: ° угоя,яслсду як были доучя снежными ребиами не .ненмае !20', ° ссе вершины, степени 1 яазяются сраничнымю ° если вершина ьгасиени 2 не граничная, то угол мсокду выяодяти.ни иэ нее исвыроокденными ребрами равен !80'. Доказательство. Пусть 1' минимальная сеть. Покажем, что для нее выполняются вес свойства, псречислснныс в предложении.

Пусть е произвольное ребро сети Г, и предположим, что е пс является отрезком прямой. дто означает, что существует такая внутренняя точка Р из с, что лкьбая связная замкнутая окрестность точки Р не есть отрезок прямой. С ,)ругай стороны, каждая локальная сеть Гп с пептром в Р это часп, ребра с между некоторыми его точками ! и В, содержащая Р. Так как сеть Г, по предположению, минимальна, то некоторая локальная сеть Гп абсолютно минимальна, т.е. является отрезком [А, В). Полученное противоречие заверпиет доказательство перво~ о пункта предложения.

Доказательство второго пункта проведем от противного. Пусть Р вершина сети Г, такая что угол между ннцидснтными сй рсбрами-отрезками е и е' меньше 120'. Пусп, Гп абсолютно минимальная локальная сеть с центром в точке Р. Выберем лекальнук> сеть Г' С Гп с ценз ром в Р, такую что длины всех се ребер одинаковы. Так как Гн абсолютно минимальна, то Г' также абсолютно минимальная сеть. Пусть Г и Г' те ребра из Г', которые содержатся в е и е' соответственно, а А и А' вершины из Г', отличные от Р и ипцидентцые соответственно Г н )и.

В треуголшшке РА:!' все уг.лы меньше, чем 120', поэтому минимальная сеть Г,„, затягивающая вершины этого треугольника, короче, чем сумма длин ребер ~' и Заменив в локальной сети Ги отрезки Г и ~' ребер е и е' на сеть Г„„ наделив полученную совокупность кривых структурой какой-нибудь сети Г' н выбрав, в качестве границы, все те вершины из 1ч, которые были границей в сети Гн, получим есть, граница которой совпадает с границей сети Гн, но длина которой меньше длины сети Гп. Это противоречит Локальное устройство минимальных остей абсолютной минимальности локальной сети Гн, что и доказывает второй пункт предло. кения.

Иокшкем теперь, что все верппп|ы степени ! граничные. Действительно, если некоторая вершина Р степени 1 не граничная, то каж,лая локальная сеть Гн с центром в Р зто отрезок [Р, Я] лля некоторой точки Я из единственного ребра, инцидептного Р. !!ри этом, вершина Р сети Гп не является граничной вершиной. Иоэтому, если Р' произвольная внутренняя точка отрезка [Р, ф, то сеть [Р', ГЗ] затягивает дГс и короче, чем Гн,противоречие. Пусть теперь Р внутренняя вершина степени 2 сети Г, и предположим, что угол мел'ду выходящи ли из Р ребрами отличен от !80'. Пусть Гп произвольная локальная сеть с центром в Р. Тогда сеть Гц состоит из двух ребер-отрсзков, скажем [Р, ГЗ] и [Р, Л], стыкук1шихся в Р под некоторым углом, отли п|ым от 180'. При этом, (каноническая) граница сети Гп состоит из двух точек с2 и Л.

Поэтому сеть [б2, Л] затягивает границу дГп и короче сетя Гн, противоречие. Итак, мы доказали, что каждая локально минимальная сеть оо,шдает всеми свойствами, персчисленнымн в предложении 1.1. Покажем теперь, что каждая сеть Г, удовлстворязощая всем условиям этого предложения, локально мпнимшп,па. 2(ля этого мы должны показатгь гго некоторая локальная сеть произвольной точки из Г является абсолютно минимальной. Пусть Р произвольная внутренняя точка некоторого ребра сети Г.

Так как ребра из Г являются отрезками, то каждая локальная сеть Гп с центром в Р некоторый отрезок [Я, Л], причем дГп = (Я, Л). Ясно, что такая Гн абсолютно минимальна. Далее, пусть Р вершина сети Г, и Гп произвольная локальная сеть с центром в Р. '1ак как угол между лкюой парой ребер-отрезков, инпидентных Р, не меньше 120', то степень с!сьи(Р) вершины Р нс превосходит 3. Иредположим сначала, что вершина Р граничная. !',ели с!ей(Р) = 1, то Гн некоторый отрезок [Р, 1,1], причем дГь = (Р, ®, поэтому Гс абсолютно минимальна. Если с!ея(Р) = 2, то Гц,пзе стороны [Р, Я] и [Р, Л] трау~ ольника РОЛ, угол которого пря вершине Р больше или равен 120'. При этом, дГн = (Р, 1;1, Л), поэтому Гс абсолютно минимальная сеть.

Наконец, если 4ея(Р) = 3, то Гн состоит пз трех отрезков, скажем [Р, ГЗ], [Р, Л] и [Р, Л], углы между которыми равны 120'. Отсюда немедленно вьггекает, что в треугольнике ЯЛЛ все углы меньше 120', поэтому абсолк1тно минимальная сеть Г', затягивающая вершины !л, Л и сз, совпадает, как подмножество плоскости, с Го. Однако, у сети Гн, в отличие от Г', имеется дополнительная граничная вершина, а именно, Р. Если Гп нс является абсолютно минимальной сетью с границей (с,,с Л. Л, Р), то абсолкхгно линнмальная сеть с этой граниной короче, чем ! ' и. с другой стороны, затяе иваст вершины !„), Л и Л, что противоречит абсолк1тной минимальности сети Г'.

'!'аким образом, сеть Гь: абсолютно минимальна. Локальное устройство минимальных остей Пусть геперь вершина Р внутренняя. Если с!еоо[Р) = 2, то Гьь как подмножество плоскости, это некоторый отрезок [!ь!, Й], для которого вершина Р некоторая внутренняя точка. Граница сстп Гн состоит из двух точек, О и Й, поэтому 1 ь абсолютно миннмальнал сеть.

Пусть теперь с!ся[Р) = 3. Тогда Гь состоит из трех отрезков, скажем [Р, Я, [Р, Й] и [Р, о], стыкующихся в Р под углами в !20'. Поэтому в треугольнике ЯЙэ' все углы мепыпе 120', и абсолютно минимальная сеть с границей Я, Й, х) совпадает, как по;!множество плоскости, с Гьл. С другой стороны, граница сети Гн зто Я, Й, Й), поэтому Гн абсолютно минимальна. Доказательство предложения Е1 закопчено.

Замечание. П соответствии с предложением 1.1, кюк,лая минимальная сеть параълетриэуется простым ерофолб т.е. графом без петель и кратных ребер. Поэтому. в дап,пейшеы мы ограни плмся рассмотрением лишь простых графов, и под топологическим графом будсьг всегда понимать граф без кратных ребер н петель. Замечание. Из предложения 1.1 вытекает, что каждая минимальная сеть является погруженной сетью, степень каждой вершины которой нс превосходит 3.

Именно такие сети являются предметом нашего рассмотрения. Связный топологический граф, степени вершин которого нс превосходят трех, называется грофоль Штайнера, а соответствующая погруженнан сеть сшиькз Шьнейнора. Графы [сетп) Штейнера без вершин степени 2 называются нооыроледеннььии. Итак, каждая минимальная сеть является сетью Штсйнсра.

Среди графов Штейнера выделяется важный подкласс бинарньи: деревьев или 2-дерооььо. состояший из невырожденных графов !Птейнсра, являющихся деревьями. Такие деревья, по определению, содержат лишь всрпппььь степени ! и 3, Соответствующие сети мы будем называть поерулеснны.яи бинарнььни дсрсоьл.ин или ноеруэкеннььяи 2-дсрооьл.яи. Замечание. Легко видеть, что из любой сети Г, не меняя ес как подмножес г во плоскости, можно получить другую сеть, выбрав на ребрах параметрнэующего графа С произвольные внутренние точки и добавив их к множеству подвижных вершин.

Эту операцию мы описали выше, назвав ее измельчением сети Г. По предложепикь 1.1, при измельчении каждая минимальная сеть остается минима.ьной.. Обратно, укрупняя произвольную минимальную сеть !' выбрасыванием нз множества вершин параметрнзующего графа С подвижных вершин степени 2, вновь, по предлоькению 1. 1, получаем минимальную сеть. Отметим, что операция укрупнения минимальных сетей на плоскости корректна, так как минимальные ости не содержат петель. Определение.

Каждую подвижную вершину степени 2 произвольной сстн Г будем называть фиктионой. Локальное устройство минимальных остей В дальнейшем, цс ограничивая общности, буде.и всегда считать, лпю расс,яатриваемью сети не и.явют фактивиьш ьгршин. Замечание. Пусть Г произвольная минимальная сеть с граниной дГ. По предложению 1.1, степени вершин сети Г нс щэсвосходят 3. В соотвстствис со сделанным вылив соглашением, граница сети ! вклло лает все вершины степени 1 и 2 (напоьлпим, что мы договорились запретить все фнктивныс вершины), однако может также содержать и вершины степени 3. Выкинем из г)Г все вершины сети Г степени 3.

По тому же црелложелппо 1.1, сстл Г с так полученной границей по-прежнему является минимальной сетькь Однако теперь граница сети Г сослхплз в точности из всех вершин степени 1 и 2. Опродлщенно. Пусть, С произвольный граф П!тейнера, Множество всех вершин из С степени 1 и 2 мы назовем эффскьпивной границей и будем обозначать через д,С. Вершины из С степени 3 назьплаются олечками Шлпсл!нера. Вес зтн определения дословно псрсносятся и на сстн Штсйнсра. Итак, имеет место следующий очевидный результат. УтвеРжДение 1.1 Сеть ШлиевнвРа Г с гРаницей д!" З длр,лшлш кольна то,.да и то„шьо пюгда, когда .,яинимаяьна сеть Г с эффективной границей д,Г.

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

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6508
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее