chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2025-26-2-101-124cheb-1962Research ArticleСтатьиArticleСимметрии выпуклых многогранников бинарных деревьевConvex Polyhedra of Binary Trees and their SymmetriesИвановАлександр ОлеговичIvanovAlexandr Olegovich

доктор физико-математических наук, профессор

doctor of physical and mathematical sciences, professor

aoiva@mech.math.msu.suМархановДмитрий АлексеевичMarkhanovDmirtii Alexeevichdemetryfotball@gmail.comМосковский государственный университет им. М.В. Ломоносова; Московский государственный технический университет им. Н.Э. БауманаРоссияLomonosov Moscow State University; Bauman Moscow State Technical UniversityRussian FederationМосковский государственный университет им. М. В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian Federation202510072025262101124Copyright © Иванов А.О., Марханов Д.А., 20252025Иванов А.О., Марханов Д.А.Ivanov A.O., Markhanov D.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1962

Задача о поиске минимальных параметрических заполнений конечного метрического пространства 𝑀 сводится к классической задаче линейного программирования. Множество допустимых значений двойственной задачи представляет собой выпуклый многогранник Λ𝐺, который зависит только от типа заполнения 𝐺 — дерева, множество вершин степени 1 которого совпадает с 𝑀, а остальные вершины имеют степень 3 (такие деревья называются бинарными, соединяющими 𝑀). Вершины этого многогранника играют важную роль при вычислении веса минимального заполнения.Изоморфным бинарным деревьям, соединяющим одно и тоже пространство 𝑀, соответствуют, вообще говоря, разные многогранники. В данной работе получен полный ответ на вопрос о том, как они связаны между собой. Кроме того, в работе обсуждается вопрос об устройстве объединения 𝑈 множеств вершин всех многогранников Λ𝐺, соответствующих всевозможным бинарным деревьям 𝐺, соединяющим данное множество 𝑀. Множество 𝑈 = 𝑈(𝑚) зависит только от количества 𝑚 точек в множестве 𝑀. Оказывается при 𝑚 ⩽ 6 множество 𝑈(𝑚) является выпуклым, то есть представляет собой множество вершиннекоторого выпуклого многогранника. Выпуклость 𝑈(𝑚) при больших 𝑚 — это открытый вопрос.

Problem of finding minimal parametric fillings of a finite metric space 𝑀 can be reduced to classical linear programming. The set of admissible values of the dual problem is a convex polyhedron Λ𝐺 that depends on the filling type 𝐺, i.e., on a tree, whose set of degree 1 vertices equals 𝑀, and all other vertices have degree 3 (such trees are referred as binary trees connecting 𝑀). Vertices of this polyhedron have an important role in minimal filling weight calculation.

Generally speaking, isomorphic binary trees connecting the same space 𝑀 correspond to different polyhedra. In the present paper a complete answer on the relations between such polyhedra is obtained. Besides, the question on the structure of the set 𝑈 obtained as the union

of the vertices of all polyhedra Λ𝐺 over all binary trees connecting a given set 𝑀. This set 𝑈 = 𝑈(𝑚) depends on the number of points 𝑚 in the set 𝑀. It turns out that the set 𝑈(𝑚) is convex for 𝑚 ⩽ 6, i.e., it is a vertex set of a convex polyhedron. Convexity of 𝑈(𝑚) for other 𝑚 is an open question.

конечное метрическое пространствоминимальное параметрическое заполнениелинейное программированиемногогранник бинарного деревагруппа перестановоквыпуклость.finite metric spaceminimal parametric fillinglinear programmingconvex polyhedron of a binary treepermutation groupconvexityReferencesИванов А.О., Тужилин А.А. Теория экстремальных сетей. М.–Ижевск: Институт компьютерных исследований, 2003. 256 с.Ivanov, A.O., Tuzhilin, A.A., 2003, Extreme Networks Theory, Moscow-Izhevsk: Regul. i Khaot. Dinamika [in Russian].Иванов А.О., Тужилин А.А. Одномерная проблема Громова о минимальном заполнении // Матем. сборник. 2012. Т. 203, № 5. С. 65–118. DOI: https://doi.org/10.4213/sm7777.Ivanov, A.O., Tuzhilin, A.A., 2012, “One-dimensional Gromov Minimal Filling Problem”, Sbornik Math., vol. 203, no. 5, pp. 65–118. DOI: https://doi.org/10.1070/SM2012v203n05ABEH004239.Иванов А.О., Овсянников З.Н., Стрелкова Н.П., Тужилин А.А. Одномерные минимальные заполнения с ребрами отрицательного веса // Вестн. Моск. ун-та. Сер. 1: Матем., мех. 2012. № 5. С. 3–8.Ivanov, A.O., Ovsyannikov, Z.N., Strelkova, N.P., Tuzhilin, A.A., 2012, “One-dimensional Minimal Fillings with Negative Edge Weights”, Moscow Univ. Math. Bull., vol. 67, no. 5–6, pp. 189–194. DOI: https://doi.org/10.3103/S0027132212050014.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.Ivanov, A., Tuzhilin, A., 2021, “Dual Linear Programming Problem and One-Dimensional Gromov Minimal Fillings of Finite Metric Space”, in Trends in Mathematics, Cham: Springer, pp. 165–182. arXiv:1907.03828 [math.MG] (2019).Gromov M. Filling Riemannian manifolds // J. Diff. Geom. 1983. Vol. 18, no. 1. P. 1–147. DOI:10.4310/jdg/1214509283.Gromov, M., 1983, “Filling Riemannian Manifolds”, J. Diff. Geom., vol. 18, no. 1, pp. 1–147. DOI: 10.4310/jdg/1214509283.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).Ivanov, A.O., Tuzhilin, A.A., 2014, “Minimal Fillings of Finite Metric Spaces: The State of the Art”, in Discrete Geometry and Algebraic Combinatorics, AMS, vol. 625, pp. 9–35.Беднов Б.Б., Бородин П.А. Банаховы пространства, реализующие минимальные заполнения // Матем. сборник. 2014. Т. 205, № 4. С. 3–20. DOI: https://doi.org/10.4213/sm8264.Bednov, B.B., Borodin, P.A., 2014, “Banach Spaces that Realize Minimal Fillings”, Sb. Math., vol. 205, no. 4, pp. 459–475. DOI: https://doi.org/10.1070/SM2014v205n04ABEH004383.Еремин А.Ю. Формула веса минимального заполнения конечного метрического пространства // Матем. сборник. 2013. Т. 204, № 9. С. 51–72. DOI: https://doi.org/10.4213/sm7835.Eremin, A.Yu., 2013, “A Formula for the Weight of a Minimal Filling of a Finite Metric Space”, Sb. Math., vol. 204, no. 9, pp. 1285–1306. DOI: https://doi.org/10.1070/SM2013v204n09ABEH004340.Щербаков О.С. Многогранники бинарных деревьев, строение многогранника дерева типа «змея» // Чебышевский сборник. 2022. Т. 23, № 4. С. 136–151. DOI: https://doi.org/10.22405/2226-8383-2022-23-4-136-151.Shcherbakov, O.S., 2022, “Polyhedra of Binary Trees, Structure of the Polyhedron for a Tree of the “Snake” Type”, Chebyshev. Sbornik, vol. 23, no. 4, pp. 136–151 [in Russian]. DOI: https://doi.org/10.22405/2226-8383-2022-23-4-136-151.Щербаков О.С. Ограничения на кратность неприводимых мультиобходов некоторых бинарных деревьев // Вестн. Моск. ун-та. Сер. 1: Матем., мех. 2025. № 2. (В печати).Shcherbakov, O.S., 2025, “Upper Estimates on the Multiplicities of Irreducible Multitours for Some Binary Trees”, Moscow Univ. Math. Bull. [in Russian, to appear].Иванов А.О., Щербаков О.С. Существование неприводимых мультиобходов кратности 2 // Чебышевский сборник. 2024. Т. 25, № 3. С. 101–117.Ivanov, A.O., Shcherbakov, O.S., 2024, “Existence of Irreducible Multitours of Multiplicity 2”, Chebyshev. Sbornik, vol. 25, no. 3, pp. 101–117.Беднов Б.Б. Длина минимального заполнения пятиточечного метрического пространства // Вестн. Моск. ун-та. Сер. 1: Матем., мех. 2017. № 6. С. 3–8.Bednov, B.B., 2017, “The Length of Minimal Filling for a Five-Point Metric”, Moscow University Math. Bull., vol. 72, no. 6, pp. 221–225. DOI: https://doi.org/10.3103/S0027132217060018.Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал Пресс, 1998. 320 с.Vasiliev, F.P., Ivanitskii, A.Yu., 1998, Linear Programming, Moscow: Factorial Press.Hwang F.K. A linear time algorithm for full Steiner trees // Operations Research Letters. 1986.Hwang, F.K., 1986, “A Linear Time Algorithm for Full Steiner Trees”, Operations Research Letters, vol. 4, no. 5, pp. 235–237. DOI: https://doi.org/10.1016/0167-6377(86)90008-8.Vol. 4, no. 5. P. 235–237. DOI: https://doi.org/10.1016/0167-6377(86)90008-8.Vinberg, E.B., 2003, A Course in Algebra, New York: AMS.Винберг Э.Б. Курс алгебры. 2-е изд., испр. и доп. М.: Факториал Пресс, 2001. 544 с.Malysheva, O.S., 2020, “Optimal position of compact sets and the Steiner problem in spaces with Euclidean Gromov–Hausdorff metric”, Sb. Math., vol. 211, no. 10, pp. 1382–1398. DOI:https://doi.org/10.1070/SM9361.Малышева О.С. Оптимальное положение компактов и проблема Штейнера в пространствах с евклидовой метрикой Громова–Хаусдорфа // Матем. сборник. 2020. Т. 211, № 10. С. 32–49. DOI: https://doi.org/10.4213/sm9361.Малышева О.С. Оптимальное положение компактов и проблема Штейнера в пространствах с евклидовой метрикой Громова–Хаусдорфа // Матем. сборник. 2020. Т. 211, № 10. С. 32–49. DOI: https://doi.org/10.4213/sm9361.

The authors declare that there are no conflicts of interest present.