Симметрии выпуклых многогранников бинарных деревьев
https://doi.org/10.22405/2226-8383-2025-26-2-101-124
Аннотация
Задача о поиске минимальных параметрических заполнений конечного метрического пространства 𝑀 сводится к классической задаче линейного программирования. Множество допустимых значений двойственной задачи представляет собой выпуклый многогранник Λ𝐺, который зависит только от типа заполнения 𝐺 — дерева, множество вершин степени 1 которого совпадает с 𝑀, а остальные вершины имеют степень 3 (такие деревья называются бинарными, соединяющими 𝑀). Вершины этого многогранника играют важную роль при вычислении веса минимального заполнения.
Изоморфным бинарным деревьям, соединяющим одно и тоже пространство 𝑀, соответствуют, вообще говоря, разные многогранники. В данной работе получен полный ответ на вопрос о том, как они связаны между собой. Кроме того, в работе обсуждается вопрос об устройстве объединения 𝑈 множеств вершин всех многогранников Λ𝐺, соответствующих всевозможным бинарным деревьям 𝐺, соединяющим данное множество 𝑀. Множество 𝑈 = 𝑈(𝑚) зависит только от количества 𝑚 точек в множестве 𝑀. Оказывается при 𝑚 ⩽ 6 множество 𝑈(𝑚) является выпуклым, то есть представляет собой множество вершин
некоторого выпуклого многогранника. Выпуклость 𝑈(𝑚) при больших 𝑚 — это открытый вопрос.
Об авторах
Александр Олегович Иванов
Московский государственный университет им. М.В. Ломоносова; Московский государственный технический университет им. Н.Э. Баумана
Россия
Россия
доктор физико-математических наук, профессор
Дмитрий Алексеевич Марханов
Московский государственный университет им. М. В. Ломоносова
Россия
Россия
Список литературы
1. Иванов А.О., Тужилин А.А. Теория экстремальных сетей. М.–Ижевск: Институт компьютерных исследований, 2003. 256 с.
2. Иванов А.О., Тужилин А.А. Одномерная проблема Громова о минимальном заполнении // Матем. сборник. 2012. Т. 203, № 5. С. 65–118. DOI: https://doi.org/10.4213/sm7777.
3. Иванов А.О., Овсянников З.Н., Стрелкова Н.П., Тужилин А.А. Одномерные минимальные заполнения с ребрами отрицательного веса // Вестн. Моск. ун-та. Сер. 1: Матем., мех. 2012. № 5. С. 3–8.
4. Ivanov A.O., Tuzhilin A.A. Dual Linear Programming Problem and One-Dimensional Gromov Minimal Fillings of Finite Metric Space // Trends in Mathematics. Cham: Springer, 2021. P. 165–182. arXiv:1907.03828.
5. Gromov M. Filling Riemannian manifolds // J. Diff. Geom. 1983. Vol. 18, no. 1. P. 1–147. DOI:10.4310/jdg/1214509283.
6. Ivanov A.O., Tuzhilin A.A. Minimal fillings of finite metric spaces: The state of the art // Discrete Geometry and Algebraic Combinatorics. AMS, 2014. Vol. 625. P. 9–35. (Contemporary Mathematics).
7. Беднов Б.Б., Бородин П.А. Банаховы пространства, реализующие минимальные заполнения // Матем. сборник. 2014. Т. 205, № 4. С. 3–20. DOI: https://doi.org/10.4213/sm8264.
8. Еремин А.Ю. Формула веса минимального заполнения конечного метрического пространства // Матем. сборник. 2013. Т. 204, № 9. С. 51–72. DOI: https://doi.org/10.4213/sm7835.
9. Щербаков О.С. Многогранники бинарных деревьев, строение многогранника дерева типа «змея» // Чебышевский сборник. 2022. Т. 23, № 4. С. 136–151. DOI: https://doi.org/10.22405/2226-8383-2022-23-4-136-151.
10. Щербаков О.С. Ограничения на кратность неприводимых мультиобходов некоторых бинарных деревьев // Вестн. Моск. ун-та. Сер. 1: Матем., мех. 2025. № 2. (В печати).
11. Иванов А.О., Щербаков О.С. Существование неприводимых мультиобходов кратности 2 // Чебышевский сборник. 2024. Т. 25, № 3. С. 101–117.
12. Беднов Б.Б. Длина минимального заполнения пятиточечного метрического пространства // Вестн. Моск. ун-та. Сер. 1: Матем., мех. 2017. № 6. С. 3–8.
13. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал Пресс, 1998. 320 с.
14. Hwang F.K. A linear time algorithm for full Steiner trees // Operations Research Letters. 1986.
15. Vol. 4, no. 5. P. 235–237. DOI: https://doi.org/10.1016/0167-6377(86)90008-8.
16. Винберг Э.Б. Курс алгебры. 2-е изд., испр. и доп. М.: Факториал Пресс, 2001. 544 с.
17. Малышева О.С. Оптимальное положение компактов и проблема Штейнера в пространствах с евклидовой метрикой Громова–Хаусдорфа // Матем. сборник. 2020. Т. 211, № 10. С. 32–49. DOI: https://doi.org/10.4213/sm9361.
Рецензия
Для цитирования:
Иванов А.О., Марханов Д.А. Симметрии выпуклых многогранников бинарных деревьев. Чебышевский сборник. 2025;26(2):101-124. https://doi.org/10.22405/2226-8383-2025-26-2-101-124
For citation:
Ivanov A.O., Markhanov D.A. Convex Polyhedra of Binary Trees and their Symmetries. Chebyshevskii Sbornik. 2025;26(2):101-124. (In Russ.) https://doi.org/10.22405/2226-8383-2025-26-2-101-124
Просмотров:
5
Послать статью по эл. почте 