Polytops of Binary Trees, Structure of the Polytop for the «Snake–type»–Tree
https://doi.org/10.22405/2226-8383-2022-23-4-136-151
Abstract
In the paper minimal fillings of finite metric spaces are investigated. This object appeared as a generalization of the concepts of a shortest tree and a minimal filling in the sense of Gromov. It is known that the weight of a minimal filling of a given type can be found by linear
programming and by so-called multitours technique. A relation between theses two approaches can be demonstrated using duality in linear programming, namely, rational points of the polytop
constructed by the dual problem correspond to multitours. The paper is devoted to investigation of such polytopes, It is shown that the vertices of the polytop are in one-to-one correspondence with irreducible multitours. A description of the polytop and an explicit formula for the weight of the minimal filling of the «snake–type» binary tree is obtained.
About the Author
Oleg Sergeevich Shcherbakov
Lomonosov Moscow State University; Bauman Moscow State Technical University
Russian Federation
Russian Federation
postgraduate student
References
1. Ivanov А.О., Tuzhilin А.А. Extreme Networks Theory // Moscow, Izhevsk: IKI, 2003.
2. Ivanov А.О., Tuzhilin А.А. One-dimensional Gromov minimal filling problem // Sbornik:
3. Mathematics 2012. vol. 203, № 5.pp. 65-118.
4. Ivanov A., Tuzhilin A. Dual Linear Programming Problem and One-Dimensional Gromov
5. Minimal Fillings of Finite Metric Space // Differential Equations on Manifolds and Mathematical
6. Physics. Trends in Mathematics. Birkh¨auser, Cham. 2022. pp. 165-182.
7. Eremin A.Yu. A formula for the weight of a minimal filling of a finite metric space.Sbornik:
8. Mathematics 2013. vol. 204, №9. pp.51-72.
9. Vasilyev F.P., Ivanitskiy A.Y. In-Depth Analysis of Linear Programming // Dordrecht:
10. Springer, 2001.
11. Ivanov А.О., Tuzhilin А.А., Eremin A.Yu. Minimal filling of a pseudometric space // Seminar
12. on tensor and vector analysis with applications in geometry, mechanics and physics, 2011.
13. Vol.27. pp.83-105
14. Ivanov A.O., Ovsyannikov Z.N., Strelkova N.P., Tuzhilin A.A. One-dimensional minimal fillings
15. with negative edge weights // Moscow University Mathematics Bulletin, 2012. vol.67. pp.189-
16.
17. Ivanov A.O., Tuzhilin A.A., Cieslik D. Steiner Ratio for Manifolds // Math. Notes 2003. vol.74,
18. №3. pp.387-395.
19. Ovsyannikov Z.N. An open family of sets that have several minimal fillings // Fundamental
20. and Applied Mathematics, 2013. Vol.18. №2, pp.153-156.
21. The length of minimal filling for a five-point metric space // Moscow University Mathematics
22. Bulletin, 2017. vol.72. pp.221-225.
23. Bednov B. B. The set of geometric medians for four-element subsets in Lindenstrauss spaces
24. // Moscow University Mathematics Bulletin 2019. №6. С.215-220.
25. Bednov B. B. The length of a minimal filling of star type // Sb. Math., 2016. Т.207, №8.
26. С.1064-1078.
27. Bednov B. B., Borodin P. A. Banach spaces that realize minimal fillings // Sb. Math., 2014.
28. vol.205, №4. С.459-475.
29. Pahkomova A.S. A Continuity Criterion for Steiner-Type Ratios in the Gromov-Hausdorff Space
30. // Math. Notes, 2014. vol.96, №1. pp.130-139.
31. Rubleva O.V. The additivity criterion for finite metric spaces and minimal fillings // Moscow
32. University Mathematics Bulletin, 2012. vol.67. pp.52-54.
Review
For citations:
Shcherbakov O.S. Polytops of Binary Trees, Structure of the Polytop for the «Snake–type»–Tree. Chebyshevskii Sbornik. 2022;23(4):136-151. (In Russ.) https://doi.org/10.22405/2226-8383-2022-23-4-136-151
Views:
252
Email this article 