RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2014, номер 1, страницы 17–25 (Mi vmumm291)

Эта публикация цитируется в 6 статьях

Математика

Оценки для суботношения Штейнера и отношения Штейнера–Громова

А. С. Пахомоваab

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

Аннотация: В статье доказана точная нижняя оценка для $n$-точечного суботношения Штейнера и отношения Штейнера–Громова произвольного метрического пространства. В качестве следствия получены значения этих величин для некоторых конкретных пространств, в частности филогенетических, а также доказано, что произвольное число от 0,5 до 1 может являться суботношением Штейнера или отношением Штейнера–Громова некоторого метрического пространства.

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

УДК: 519.176

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


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2014, 69:1, 16–23

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


© МИАН, 2024