Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 69
Текст из файла (страница 69)
С другой стороны, [и,сб] < л'+ 3 — пн![Е ) < 4, откуда и < 30, противоречие. '1акихл образом, если к ячейке сх' крепится нарост, то паркет Р нс имеет минимальной реализации на правильном многоугольнике. Пусть теперь к ячейке Лэ парост пс крепится. Если па участке Ез наростов нет, то, в силу предложения 6.6, паркет Р не имеет минимальной реализации па правильном ллттогоугольтттттсе. Пусть к участку Ез крепятся наросты.
Так как, в силу леммы 6.5, длина боковины участка Ез, соотвстствутощей Вт э, нс болыпе 3, то к Ез крепится ровно один нарост, и длина Произвольныс паркеты с правильной границей 311 этой ооковины равна 3. Наьл понадобится следующее обобщение предло'ке- ния 6.6. Предложение 6.9 1)усть паркет Р имеет. два концевых,тпьейных участка змеи Е и Е', угол .яезкдлу напраьления,ни которых, равен к)зЗ.
11редположим, что единственная ячейка Л' паркета Р, нс лсжаи!ая ни в Е, ни в Е.", и снежная с той его внутренней ячейкой Ьх, к которой крепятся зти концевые линейньсс у застки, ис,является внутренней ячейкой паркета Р. Еро.яе псого, предположихц чпсо единственное граничное ребро ячейки Л' параллельно напраелсшзю ьонцсвого .швейного учасгпка Е. ))усть д количество норостоь на участке Е.
Тогда, если паркет Р имеет минимальную реализацшо иа правильном .яногоугольиикс, то длина коицевоео ланеиного участка Е' ие преьстходит 2д+ 1. Доказательство. Пусть, паркет Р имеет минимальную реализацию Г на множестве ЛХ = ) тл) вершин правильного многоугольника. Ооозяачим через А:, ребро дерева Г, соотве"гствуюшее грани шому ребру ячейки ьлс.
В силу с,лсланпых предполоясепий, Рт параллельно отросткам конпевого линейного участка Е. Обозначим через Й концевое ребро из Г, а через тс концевую вершину из 31, соответствукпцие участку Е. )!алое, обозначим через В боковину участка Е, не пересекающуюся с общей боковиной участков Е и Е', и пусть )з длина боковины В. Проведем через 1, прямую 1„, параллельную отросткам участка Е. Обозначим через П, открытую полуплоскость, ограниченную праман 1, и содержащую вершину зицз. Легко видеть, что в полуплоскости !1, содержится не бстее чем 1+ д вершин из !Х, ьье инпидеььтных граничным ребрам:змеи Е. Обозначим через йп единственное ребро участка Е', принадлсясащсс впутреьшей ячейке сз, и через )о прямую, проходяьцую через яп. Легко видстлч что 1.п и, значит, !", параллельны отросткам участка Е. Кроъсс того, прямая )и содержится в полуплоскости П„.
Далее, пусть Пп открытая полуплоскостьч ограниченная прямой !", такая что концевое рсбро концевого линейного участка Е' содержится в П". Очевидно, что Пп С П,. Легко видеть, что в сьосьуььсьосьсосз ьл Пп лежьлт нс монсе [гьс2]+ 1 точек из 3Х, инцицснтных гРаничным Рс*бРам Участка Е' [а именно, все [х)з2] точек боковины участка Е', соответствукзшеи обшей боковине концевых линейных участков Е и Е', и одна концевая вершина участка Е'). Поэтому, [хьс2]+1 < у+1, откуда г < 2д+1. Прелложение доказано. В силу предложения 6.9, длина участка Ез нс превосходит 3.
Поэтому длина боковины Взз равна 4 — 'шд[Ез). С другои стороны, в силу следствия 4.23 главы 4, длина боковины Взз больше или равна [ьз)зб] — 1, откуда [сз)'6] < 5 — шс1[Ег). Произвольныс паркеты с правильной г раницей 312 !4ак и вылив, без огра~ичепия общности можно предполагать, по тнп пз.,юма концевого линейного учасгка Ел равен лллн 1, и.пл 4. Пусть тип излома участка Ел равен 1. Тогда, в силу следствия 4.11 главы 4, длина боковины хвоста участка Ел, соответствующей Влз, нс мсныпе чем [и/3]— [(гс + 9)/12] — 1, откуда длина боковины Влз нс меньше чем [и/3] — [(и + 9)/!2] + 3.
С,лругой стороны, так как !пс!(Ел) = 1, в силу следствия 4.23 главы 4, дллша боковины Влз равна [и/:!]+ !ллс!(Ез) — 2. Поэтому [и/3] + !вс!(Ез) — 2 > [и/3] — [(и+ 9)/12]+ 3, т.е. [(и + 9)/12] > 5 — !ггс!(Ез). Если !глс!(Ез) = 1, то [(и + 9)/12] > 4, откуда и > 39. С другой стороны, [п/6] < 5 — шс1(Ез) = 4, откуда и < 30, противоречие. Если же пп1(Ез) = 2, то [(и+ 9)/12] > 3, откуда и > 27. С другои стороны, [и/6] < 5 — шс1(Ез) = 3, откуда и < 24, противоречие.
Пусть теперь тип излома концевого линейного участка Ег равен 4. Тогда, в силу следствия 4.14 главы 4, длина боковины хвоста участка Ел, соответствующей Вгз, нс меньше чем [и/3] — [и/12] — 2, откуда длина боковины Влз це меньше лем [и/3] — [и/12]+ 2. С друг ой стороны, так как шс!(Ег) = 2, в силу следствия 4.23 главы 4, длина боковины Влз равна [и/3] — ! . Поэтому [и/3] — 1 > [и/3] — [п/!2]+ 2, т.е.
[п/12] > 3, откуда п > 36. Однако, (и/6] < 5 — шс1(Е ) < 4, откуда и < 30, противоречие. '1аким образом, и в этом случае паркет 12 нс имеет мллннмальной реализации на правильном многоугольнике. Объединял все полученные результаты, получаем доказательство основной теоремы 6.1. Глава 7 Невырож денные минимальные сети с выпуклои Границеи. Циклический случай !3 настоящей главе мы обобщим теоремы классификации минимальных оинарпых деревьев с выпуклой граниной на случай певырожденпых минимальных сетей с циклами. !3 главе 1, рассматривая вопросы мнннмальнон реализации сетей с циклами, мы ввели понятие фундаментального цикла. Оказывается, фундаментальныс циклы невырождснных сетей Штейнсра, имеющих выпуклую минимальную реализап1по, устроены максимально просто.
1(роме того, имеется возможность обобщить понятие числа вращения на случай невырождснпых сетей 111тейнера, все фундаментальныс пиклы которых устроены именно так. 1 сРундаментальные циклы невырожденных минимальных сетей с выпуклой границей. Тривиальные сети Пусть Г плоская невырожденная сеть Штсйнера, и б .
сс фундаментальный цикл. Предположим, что шс16 = 6, Тогда, очевидно,;: состоит нс менее чем из 6 ребер, причем, если число ребер равно 6, то все вершины цикла ~ впспшие. 'Грнвиальные сети Определение. Фуччдамептальньэй ппкл индекса 6, состоящий ровно из шести ребер, назовем тривиальны,.н. Плоскую невырожденную сеть 1Птейнера Г, вес фундаментальные циклы которой тривиальны, назовем триоиаяьнои' ос эп ь эо. Предложение 7.1 Пусэээь Г плоская нь,аыроосдснная сс"ть Шэээсйнсрц имгэогцоя ььтркчую мини„наяьнрю рсачизаччто.
Тогда Г эпрчэьиаяьээая сс ть. Доказательство. Поскольку, как было поэсззано выше, каждая плоская минимальная сеть лежит в выпуклой оболочке множестээа своих граничных вершин, то, если зта сеть имеет хотя бы одно ребро, множество сс граничных вершин состоит не менее чем из двух элементов. Пусть у произвольньш фундаментальный цикл сети Г. Если у нстривиалсн, то он имеет внутреннюю вершину Л, к которой крепится подсеть Г', целиком лежащая в области, ограниченной циклом у. Б силу сделанноэ о выше замечания, подсеть Г' имеет граничную вершину, отличную от А. Поэтому, внутри области, ограни ченной циклом у, а, значит, и внутри выпуклой оболочки множества граничных вершин сети Г, содержится граничная вершина сети Г. Г!олучепное противоречие и завершает ,чоказательство предложения.
Из прсдлоя опия 7.! вытекает, что при изучении топологии нсвырождепных миннмалэ,ных сетей с выпуклой границей, моэкно ограничиться рассмотрением тривиальных сетей. В дальнейшем, нам будет полезно следующее утверждение, вытекающее непосредственно из предложения 1.9 главы 1. остверждение 7.1 Индекс произаояьного цикла триаиальной ссэпи раасн. 6. Приведем сщс одно важное свойство тривиальных остей. о'тверждение 7.2 У колодой триоиаяьной сети имеется ьсршина сте- пени 1. Дсэказательствсэ.
Предположим противное. Тогда все вершины рассматриваемой сети имеют степень 3. Разобьем ребра тризна,эьной сети на три класса. Ребро пазовсэч внутрсяним, сели оно одновременно вхо,чит в два фундаментальных цикла, и полувнутренцим, если оно входит ровно в один фундаментальный цикл. Остальные ребра назовем внешними. Отметим, что полувнутреняие и внешние ребра лежат на ч ронине единственной нсограни генной грани рассматриваемой сети. Обозначим через й число внутрснччих ребер, через 1 число полувнутренних, и через т число внешних ребер. '1оч да, как легко видеть, 11швиальные сети 616 количество граней равно 126+1)66+1, число ребер равно 6+1+ го, а число вершин равно 216+ 1+ т),13.
По формуле Эйлера: 26+ 1 2 6 + 1 — (6+1+ т) + — (6+1+ т) = 2, 3 откуда — 1/6 — сп,13 = 1. Противоречие. 1.1 хтисло вращения тривиальной сети Оказывается, для тривиальных сетеи, несмотря на наличие циклов, также можно корректно определить число вращения. Пусть Г тривиальная сеть, и пусть а и 6 пара се г1заничпых ребер. Предположим, что уу и уз пити в Г, ка кдыи из которых соединяет ребро а с ребром 6. 'Гак же, кзк и выше, числом вращения ен, ~а, 6) пары ребер (а, 6) вдоль пути у„назовем разность количеств поворотов "налево" и "направо' во внутренних вершинах пути у; при движении по и ох а к 6. Утверждонио 7.3 Число вращения пары 6а,6) гративтчх ребер тривиаль- ной сети Г нс зависит ат пити, ис соединяющего: бжт (а, 6) = 1,н-„(а,6), для любых путей 17 и ум каакдьяй из которых соединяет а с 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
