Геометрические свойства локально минимальных сетей (1097521), страница 13
Текст из файла (страница 13)
Рассмотрим произвольную компоненту Г,. Обозначим через ЛХм..., ЛХ„координаты образов граничных вершин вершин им...,н„сети Гь Пусть е единственное граничное ребро, инцидентное вершине н . Для каждого ребра е з отличного от ем фиксируем некоторый ориентированный путь з в Г, соединяющий ребра е1 и е, начинающийся в н1 и заканчивающийся в н .
Отметим, что ориентация пути 01 определяет значения чисел е(е) ДлЯ всех РебеР е из У . Далее, пУсть сы...,сь циклы из Гь соответствуя>щие некоторой фундаментальной системе циклов графа С„ на каждом из которых фиксирована ориентация. Как и в случае путей пи ориентация каждого циюяа св определяет значения чисел е(е) для всех ребер е из сю 4. Краткое содоржание диссертации. Каждому ребру е сети Г, поставим в соответствие вещественную переменную Л,.
Рассмотрим следующую линейную систему уравнений на вещественные переменные Л,, записанную в векторной форме: Е е(е)РЮЛе = ЛХ вЂ” Мы у7, .*ме ~„ е(е)о(е)Л, = О, емвь Эта система линейных уравнений называется фундаментальной системой невырожденной компоненты Г„а ее ранг рангом гйГ; ко,нпоненя~ы Гг Определение. фундаментальной системой сети Г называется линейная система уравнений, составленная из фундаментальных систем всех невырожденных компонент сети Г, Рангом гй(Г) сети Г называется ранг ее фундаментальной системы.
Отметим, что определенная нами фундаментальная система сети Г зависит от выбора путей ~; и циклов сю Оказывается, однако, что все фундаментальные системы сети Г эквивалентны как линейные системы уравнений. В частности, множества решений всех фундаментальных систем совпадают, и ранг сети Г определен корректно, т.е. не зависит от выбора фундаментальной системы сети, Предложение 3 Пусть à — — погруженная линейная сеть типа С в йо с границей ух Обозначи.м через г ранг сегаи Г, а через т -- количество ребер сети Г.
Тогда множество [С,|р)г погруженных линейных сетей типа С с границей р, параллельных Г, представляет собой внутренность выпуклого (т — г)-мерного многогранного множества (возможно, не ограниченного). Более гаага, многогранное множество ~С, ээ)г содержит не более чем т граней максимальной размерности. Чтобы использовать предложение 3 для описания множества всех взвешенных локально минимальных сетей с фиксированными топологией и границей, нужно воспользоваться слсдующим фактом. эгтверждеиие 1 Пусть С вЂ” вэвеиэенный граф с положительной весовой функцией ш, а Г и Г' две, взвешенных погруженных минимальных сети пиэпа С с одной, и той же границей со.
Тогда сети Г и Г' параллельны. Введение. Следствие 5 Пусть Г взвешенная локально минимальная погруженная сеть типа С в Вв с границей со и положительной весовой функцией. Тогда множество взвешенных локально минимальных сетей типа С с границей ср предшаавляет собой внутренность выпуклого (т — гкГ)-мерного ограниченного многогранника, где т количество ребер сети. Более того, этот многогранник содержит не более чем т граней максимальной размерности.
Далее, ребро Г сети отнесем к нулевому уровню, если оно принадлежит какому-нибудь циклу подвижного подграфа С атой сети. Ребро, не принадлежащее нулевому уровню, но инцидентное некоторому ребру этого уровня, назовем ребром лервого уровня, а все остальные, ребра (т.е, ребра, не лежащие ни на нулевом, ни на первом уровнях) назовем ребрами второго уровня. Имеет место следующий результат. Предложение 4 Любые две взвешенных локально минимальных погруженных сети одного и того же типа С в Й" с границей ср и положительной весовой функцией имеюпс одинаковую взвешенную длину и могут быть продеформированы друг в друга в классе взвешенных локально минимальных сетей того же типа и с' той же границей.
Более свого, при каждой тесаной деформации осптются несшдвижными все ребра второго уровня и все прямые, содерэкаисие ребра первого уровня. Для плоских (взвешенных) локально минимальных сетей Штейнера число (т — гкГ) может быть вычислено в геометрических терминах. Теорема 5 Пусть Г плоская взвешенная минимальная погруженна сепсь Штейнера типа С с границей со и аоложительной весовой функцией. Тогда множество взвешенных локально минимальных сетей типа С с границей сд предснсавляет собой внутренность выпуклого (й + з')-мерного ограниченного многогранника, где к — цикломатическое тело подвижного подгрифа графа С, а у --- количество подвижных вершин из С степени 2. Более того, этот многогранник содержит не более чем т граней максимальной размерности, где т количество ребер сети Г. Научная новизна 1.
Доказано существование минимальных сетей во всех основных рассматриваемых классах сетей на полном римановом многообразии: для параметрических сетей фиксированного типа с данной границей, взвешенных параметрических сетей фиксированного типа с данной границей, параметрических сетеи данного гомотопического типа с данной 4.
Краткое содержание диссертации. 53 не пустой границей, параметрических сетей любого типа с данной границей, сетей-следов с данной границей, см,теорему 1. 2. Описана локальная структура параметрических (взвопсенных) минилсальных сетей и сетей †следов римановом лсногообразии Ис, см. теоремы 2 и 3. В частности, получены критерии локальной минимальности погрухсенных (взвешенных) параметрических сетей и сетей-.следов в терминах их локальной структуры. Для параметрических (взвешенных) сетеи общего вида получены как необходимое, так и достаточное условия их локальной минимальности.
Для случая И' = 44" эти условия удается превратить в критерий локальной минимальности (взвешенных) параметрических сетей общего вида, см, следствие 1. 3. Изучаются геометрические свойства плоских линейных деревьев плоских связных ацикличных графов, все ребра которых прямолинейные отрезки. Дла плоских линейных деревьев вводятся оригинальные понятия их геометрической границы и наело врвсцения. Найдена линейная функция от числа уровней выпуклости геометрической границы плоского линейного дерева, ограничивающая сверху число вращения этого дерева, см. теорему 4. Показана точность полученной оценки.
4. В качестве следствия из теоремы 1 о локальной структуре минимальных сетей и теоремы 4 о связи между числом вращения плоского линейного дерева и числом уровней выпуклости его геометрической границы получены точные ограничения на возможную структуру локально минимальных плоских бинарных деревьев и локально минимальных плоских деревьев, затягивающих фиксированное конечное множество И точек плоскости, в терминах количества уровней выпуклости множества Л! и числа вращения плоских бинарных деревьев, см. следствие 3.
Отметиъс, что понятие числа вращения для случая плоских бинарных деревьев введено автором совместно с Алексеем Августиновичем Тужилиным [43~. 5. В качестве следствия нз теоремы 1 о локальной структуре взвешенных минимальных сетей и теоремы 4 о связи между числом вращения плоского линейного дерева и числом у.ровней выпуклости его геометрической границы полу.чены ограничения на возможную отру.ктуру взвешенных локально минимальных плоских бинарных деревьев, затягивающих фиксированное конечное множество Л! точек плоскости, в терминах количества уровней выпуклости множества ЛХ и числа вращения взвешенных плоских бинарных деревьев, см. следствие 4. 6. Для плоских взвешенньпс минимальных бинарных деревьев построен аналог алгоритма Мелзака, позволяющий для данного конечного подмножества плоскости или построить взвешенное локально минимальное бинарное дерево данного типа,или определить, что такого Введение.
54 дерева не существует. Также для этого случая построен аналог линий Симпсона, взвешенная длина которых оказывается равной взвешенной длине минимального дерева. 7. Показано, что множество всех линейных сетей в 1хв, параллельных данной погруженной линейной сети и имеющих те же топологию и границу, представляет собой выпуклое многогранное множество. Вычислена размерность этого многогранного множества и оценено количество его граней максимальной размерности, см. предложение 3.
Этот результат используется для описания структуры множества всех (взвешенных) локально минимальных сетей данного типа, затягивающих фиксированное конечное подмножество пространства Ь, см. следствие 5. Кроме того, изучоно, чом две таких сети могут отличаться друг от друга, см. предложение 4. В качестве следствия получено обобщение теоремы Хванга )35) о единственности плоского локально минимального дерева данной топожогии с данной границей на случай (взвешенных) локально минимаяьных деревьев в евклидовом пространствс К"'. Наконец, для случая плоских сетей Штеинера размсрность многогранника всех локально минимальных сетей данного типа с данной границей вычислена в топологических терминах, см.
теорему 5. Все основные результаты диссертации являются новыми и получены автором самостоятельно. Часть результатов получена автором совместно с А. А. Тужилиным и включена в диссертацию для полноты изложения. Апробация работы Результаты диссертации рассказаны и обсуждены на многочисленных научных конференциях, в том числе, на международных конфвренпиях и математическом конгрессе, а также на ведущих научно-исследовательских семинарах как в России, так и за рубежом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
