Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 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 Сеть ШлиевнвРа Г с гРаницей д!" З длр,лшлш кольна то,.да и то„шьо пюгда, когда .,яинимаяьна сеть Г с эффективной границей д,Г.