RUS  ENG
Полная версия
ЖУРНАЛЫ // Математический сборник // Архив

Матем. сб., 2014, том 205, номер 3, страницы 83–118 (Mi sm8222)

Стабилизация локально минимального леса

А. О. Ивановab, А. Е. Мельниковаa, А. А. Тужилинa

a Механико-математический факультет Московского государственного университета им. М. В. Ломоносова
b Московский государственный технический университет им. Н. Э. Баумана

Аннотация: Развивается метод частичной стабилизации локально минимальных сетей, созданный А. О. Ивановым и А. А. Тужилиным для построения примеров кратчайших деревьев заданной топологии, при котором добавления граничных вершин степени $2$ производятся не на все ребра исходного локально минимального дерева, а лишь на некоторые. Задача частичной стабилизации локально минимальных деревьев в конечномерном евклидовом пространстве решается в статье полностью, т.е. без ограничения на количество ребер, не подвергающихся подразбиению. Получен критерий того, что такая стабилизация возможна. Кроме того, формализуется общая задача поиска кратчайшего леса, соединяющего конечное семейство граничных компактов в произвольном метрическом пространстве, и доказывается, что такие леса существуют для произвольных наборов компактов, если и только если для любого конечного подмножества объемлющего пространства существует соединяющее его кратчайшее дерево. Построенная теория позволяет проводить дальнейшее обобщение теоремы стабилизации как для произвольных метрических пространств, так и для метрических пространств со специальными свойствами.
Библиография: 10 названий.

Ключевые слова: метрические пространства, локально минимальные деревья, минимальные деревья Штейнера, кратчайшие деревья, кратчайшие леса, стабилизация локально минимального дерева.

УДК: 514.774.8+515.124.2+515.124.4+514.177.2

Поступила в редакцию: 14.02.2013

DOI: 10.4213/sm8222


 Англоязычная версия: Sbornik: Mathematics, 2014, 205:3, 387–418

Реферативные базы данных:


© МИАН, 2024