Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 635254)
Контекстум
Руконтекст антиплагиат система
Вестник Московского университета. Серия 1. Математика. Механика  / №3 2010

ДЛИНА МИНИМАЛЬНОГО ДЕРЕВА ЗАДАННОЙ ТОПОЛОГИИ: ОБОБЩЕННАЯ ФОРМУЛА МАКСВЕЛЛА (60,00 руб.)

0   0
Первый авторИванов
АвторыТужилин А.А.
Страниц8
ID360047
АннотацияКлассическая формула Максвелла вычисляет длину плоского, локально минимального, бинарного дерева по координатам граничных вершин и направлениям приходящих в них ребер. Однако, если для заданной бинарной структуры соответствующее экстремальное дерево с фиксированной границей имеет вырожденные ребра, классическая формула Максвелла непосредственно неприменима: чтобы вычислить длину экстремального дерева в этом случае, необходимо знать, какие ребра выродились. В настоящей статье мы обобщаем формулу Максвелла на произвольные экстремальные деревья в евклидовом пространстве произвольной размерности: теперь для вычисления длины такого дерева не нужно знать, ни какие ребра выродились, ни направления невырожденных граничных ребер. Ответом является максимальное значение линейной функции на выпуклом компактном подмножестве евклидова пространства, образованном пересечением цилиндров.
УДК514.774.8, 519.176
Иванов, А.О. ДЛИНА МИНИМАЛЬНОГО ДЕРЕВА ЗАДАННОЙ ТОПОЛОГИИ: ОБОБЩЕННАЯ ФОРМУЛА МАКСВЕЛЛА / А.О. Иванов, А.А. Тужилин // Вестник Московского университета. Серия 1. Математика. Механика .— 2010 .— №3 .— С. 10-17 .— URL: https://rucont.ru/efd/360047 (дата обращения: 14.05.2024)

Предпросмотр (выдержки из произведения)

№3 9 вершин V = {vk}, содержащим фиксированное подмножество B = {v1,. ,vn}, и множеством ребер E, причем будем предполагать, что все вершины степени 1 и 2 дерева G лежат в B. <...> Такое множество B назовем границей дерева Gи обозначим через ∂G. <...> Сетью типа G в отрезок Γ(vk), Γ(vl) (который может быть вырожденным). <...> Тем самым естественно определены углы между смежными невырожденными ребрами сети и длина сети как сумма длин всех ее ребер. <...> Кроме того, ребро сети назовем граничным (внутренним), если таковым является соответствующее ему ребро дерева G. <...> Ребро дерева G назовем Γ-вырожденным (Γ-невырожденным), если таковым является соответствующее ему ребро сети Γ. <...> Определим редуцированное дерево евклидовом пространстве Rm будем называть произвольное отображение Γ V → Rm. <...> Каждую сеть Γ полезно представить как линейный граф, сопоставив каждому ребру vkvl дерева G подграфа, порожденного Γ-вырожденными ребрами дерева G. <...> Граница дерева G/α состоит из всех вершин этого дерева, содержащих элементы из ∂G. <...> Для каждой сети Γ определим Γ-редукцию дерева G,выбраввкачестве Gk связные компоненты смежными ребрами приведенной сети ˆ с границей ϕ. <...> Тогда сеть наименьшей длины среди всех таких сетей называется минимальным деревом Штейнера или кратчайшей сетью с данной границей. <...> Сеть Γ называется локально минимальной, если ∂Γ взаимно однозначно с образом и углы между Пусть ϕB → Rm — отображение, взаимно однозначное с образом. <...> Отметим, что степени вершин сети ˆ Γ могут равняться 1, 2 и 3, причем все ее вершины степени 1 и 2 являются граничными. <...> Локально минимальную сеть, множество граничных вершин которой совпадает с ее множеством вершин степени 1, назовем бинарной. <...> Локально минимальные сети в свою очередь являются кратчайшими “в малом”, т.е. каждый достаточно малый фрагмент такой сети является кратчайшей сетью с соответствующей границей. <...> Для произвольной сети Γ типа G положим zk =Γ(vk) ∈ Rm. <...> Зададим в конфигурационном пространстве вектор θ, точками z =(z1,. ,zn) ∈ Rmn <...>