УДК 514+519.1
MSC: 58E10, 49K35, 05C35, 05C10, 30L05
DOI: 10.21538/0134-4889-2017-23-4-152-161
Полная версия статьи
Работа выполнена при поддержке РФФИ (проект 16-01-00378) и Программы государственной поддержки ведущих научных школ (НШ-7962.2016.1).
Изучается проблема Штейнера в пространстве Громова - Хаусдорфа, т. е. в пространстве компактных метрических пространств (рассматриваемых с точностью до изометрии) с расстоянием Громова - Хаусдорфа. Так как это пространство не является ограниченно компактным, вопрос существования кратчайшей сети, соединяющей конечное множество точек в этом пространстве, открыт. В работе доказано, что каждое конечное семейство конечных метрических пространств соединяется некоторой кратчайшей сетью. Более того, оказалось, что в рассматриваемом случае среди кратчайших деревьев найдется дерево, все вершины которого суть конечные метрические пространства. Получена оценка числа элементов в этих пространствах. В качестве примера разобран случай трехточечных метрических пространств. Также показано, что пространство Громова - Хаусдорфа не реализует минимальные заполнения, т. е. кратчайшие деревья в нем не обязаны быть минимальными заполнениями своих границ.
Ключевые слова: проблема Штейнера, кратчайшая сеть, минимальное дерево Штейнера, минимальное заполнение, пространство Громова-Хаусдорфа, расстояние Громова-Хаусдорфа.
Список литературы
1. Memoli F. On the use of Gromov–Hausdorff distances for shape comparison // Proc. Eurographics Symposium on Point Based Graphics 2007 / eds. M. Botsch, R. Pajarola, B. Chen, and M. Zwicker. Prague, 2007. P. 81–90. doi: 10.2312/SPBG/SPBG07/081-090 .
2. Hausdorff F. Grundzuge der Mengenlehre. Leipzig: Veit and Company, 1914 [reprinted by Chelsea in 1949]. 476 p. ISBN: 978-0-8284-0061-9 .
3. Edwards D. The structure of superspace // Studies in Topology / eds. N.M. Stavrakas, K.R. Allen. (Proc. Conf., Univ. North Carolina, Charlotte, N. C., 1974; dedicated to Math. Sect. Polish Acad. Sci.) N. Y.; London; San Francisco: Academic Press, Inc., 1975. P. 121–133.
doi: 10.1016/B978-0-12-663450-1.50017-7 .
4. Gromov M. Groups of polynomial growth and expanding maps // Publications Mathematiques I.H.E.S. 1981. Vol. 53, no. 1. P. 53–78. doi: 10.1007/BF02698687 .
5. Бураго Д.Ю., Бураго Ю.Д., Иванов С.В. Курс метрической геометрии. М.; Ижевск: Изд-во Ин-та компьютерных исследований, 2004. 512 c. ISBN: 5-93972-300-4 .
6. Иванов А.О., Николаева Н.К., Тужилин А.А. Метрика Громова — Хаусдорфа на пространстве метрических компактов — строго внутренняя // Мат. заметки. 2016. Т. 100, № 6. C. 947–950. doi: 10.4213/mzm11411 .
7. Иванов А.О., Тужилин А.А. Теория экстремальных сетей. М., Ижевск: Изд-во Ин-та компьютерных исследований, 2003. 424 p. ISBN: 5-93972-292-X .
8. Гаркави А.Л., Шматков В.А. О точке Ламе и ее обобщениях в нормированном пространстве // Мат. сб. 1974. Т. 95, № 2. С. 272–293.
9. Бородин П.А. Пример несуществования точки Штейнера в банаховом пространстве // Мат. заметки. 2010. Т. 87, № 4. С. 514–518, doi: 10.4213/mzm8697.
10. Беднов Б.Б., Стрелкова Н.П. О существовании кратчайших сетей в банаховых пространствах // Мат. заметки. 2013. Т. 94, № 1. С. 46–54. doi: 10.4213/mzm9228.
11. Ivanov A., Nikolaeva N., Tuzhilin A. Steiner problem in Gromov–Hausdorff space: the Case of finite metric spaces [e-resource]. 2016. 5 p. URL: https://arxiv.org/pdf/1604.02170.pdf .
12. Ivanov A. O., Tuzhilin A. A. Minimal networks: A review // Advances in Dynamical Systems and Control / eds. V.A. Sadovnochiy, M.Z. Zgurovsky. Cham: Springer Switzerland, 2016. pp. 43–80. (Studies in Systems, Decision and Control; vol. 69). doi: 10.1007/978-3-319-40673-2_4 .
13. Ivanov A., Iliadis S., Tuzhilin A. Realizations of Gromov–Hausdorff distance [e-source]. 2016. 6 p. URL: https://arxiv.org/pdf/1603.08850.pdf .
14. Chowdhury S., Memoli F. Constructing geodesics on the space of compact metric spaces [e-source]. 2016. 5 p. URL: https://arxiv.org/pdf/1603.02385.pdf .
15. Иванов А.О., Тужилин А.А. Одномерная проблема Громова о минимальном заполнении // Мат. сб. 2012. Т. 203, № 5. С. 65–118. doi: 10.4213/sm7777 .
16. Беднов Б.Б., Бородин П.А. Банаховы пространства, реализующие минимальные заполнения // Мат. сб. 2014. Т. 205, № 4. С. 3–20. doi: 10.4213/sm8264 .
17. Минимальные заполнения псевдометрических пространств / А.О. Иванов, А.А. Тужилин, А.Ю. Еремин, Е.С. Ероховец, А.С. Пахомова, О.В. Рублева, Н.П. Стрелкова, Е.И. Филоненко // Тр. семинара по векторному и тензорному анализу с их приложениями к геометрии, механике и физике. 2011. Т. 27. С. 83–105.
18. Ivanov A., Tuzhilin A. Gromov — Hausdorff distance, irreducible correspondences, Steiner problem, and minimal fillings [e-resource]. 2016. 11 p. URL: https://arxiv.org/pdf/1604.06116.pdf .
Поступила 23.06.2017
Иванов Александр Олегович
д-р физ.-мат. наук
профессор механико-математического факультета
Московский государственный университет им. М.В.Ломоносова,
г. Москва
e-mail: aoiva@mech.math.msu.su
Николаева Надежда Константиновна
преподаватель математики
СОШ НОУ “Православная Свято-Петровская школа”,
г. Москва
e-mail: nadkostnik@mail.ru
Тужилин Алексей Августинович
д-р физ.-мат. наук
профессор механико-математического факультета
Московский государственный университет им.– М.В.Ломоносова,
г. Москва
e-mail: tuz@mech.math.msu.su
English
A. O. Ivanov, N. K. Nikolaeva, A. A. Tuzhilin. Steiner’s problem in the Gromov-Hausdorff space: the case of finite metric spaces.
We study Steiner’s problem in the Gromov–Hausdorff space, i.e., in the space of compact metric spaces (considered up to isometry) endowed with the Gromov–Hausdorff distance. Since this space is not boundedly compact, the problem of the existence of a shortest network connecting a finite point set in this space is open. We prove that each finite family of finite metric spaces can be connected by a shortest network. Moreover, it turns out that there exists a shortest tree all of whose vertices are finite metric spaces. A bound for the number of points in such metric spaces is derived. As an example, the case of three-point metric spaces is considered. We also prove that the Gromov–Hausdorff space does not realise minimal fillings, i.e., shortest trees in it need not be minimal fillings of their boundaries.
Keywords: Steiner’s problem, shortest network, Steiner’s minimal tree, minimal filling, Gromov–Hausdorff space, Gromov–Hausdorff distance.
The paper was received by the Editorial Office on June 23, 2017.
A.O.Ivanov. Dr. Phys.-Math. Sci., Prof., Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow, 119991 Russia,
e-mail: aoiva@mech.math.msu.su
N.K.Nikolaeva. Mathematics Teacher, SOSh NOU “Orthodox Saint-Peter School”, Moscow, 109028, Tessinskiy per., 3 Russia,
e-mail: nadkostnik@mail.ru
A.A.Tuzhilin. Dr. Phys.-Math. Sci., Prof., Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow, 119991 Russia,
e-mail: tuz@mech.math.msu.su
