Многогранники бинарных деревьев, строение многогранника дерева типа «змея»
https://doi.org/10.22405/2226-8383-2022-23-4-136-151
Аннотация
В данной работе изучаются минимальные заполнения конечных метрических пространств (объект, возникший как обобщение понятий кратчайшего дерева и минимального заполнения в смысле Громова). Как известно, вес минимального заполнения данного типа может быть найден как решение задачи линейного программирования или с помощью так называемых мультиобходов. Связь между этими двумя подходами можно проследить, перейдя к двойственной задаче линейного программирования: рациональные точки выпуклого многогранника, который строится по типу заполнения, соответствуют мультиобходам.
Данная работа посвящена изучению таких многогранников. Показано, что их вершины соответствуют неприводимым мультиобходам. Получена описание многогранника и явная
формула веса для минимального параметрического заполнения бинарного дерева типа «змея».
Ключевые слова
конечное метрическое пространство,
минимальное заполнение,
линей- ное программирование,
двойственность,
выпуклые многогранники.
При поддержке: Исследование выполнено в рамках Научно образовательной школы МГУ «Математические методы анализа сложных систем».
Об авторе
Олег Сергеевич Щербаков
Московский государственный университет им. М. В. Ломоносова; Московский государственный технический университет имени Н. Э. Баумана
Россия
Россия
аспирант
Список литературы
1. Иванов А.О., Тужилин А.А. Теория экстремальных сетей // Москва-Ижевск: Институт
2. компьютерных исследований, 2003.
3. Иванов А.О., Тужилин А.А. Одномерная проблема Громова о минимальном заполнении
4. // Матем. сб. 2012. Т. 203, № 5.С. 65-118.
5. Ivanov A., Tuzhilin A. Dual Linear Programming Problem and One-Dimensional Gromov
6. Minimal Fillings of Finite Metric Space // Differential Equations on Manifolds and Mathematical
7. Physics. Trends in Mathematics. Birkh¨auser, Cham. 2022. pp. 165-182.
8. Еремин А.Ю. Формула веса минимального заполнения конечного метрического простран-
9. ства. Матем. сб., 2013. Т.204, №9. С.51-72.
10. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: МЦНМО, 2020.
11. Иванов А.О., Тужилин А.А. Еремин А.Ю. и др. Минимальные заполнения псевдометри-
12. ческих пространств // Труды семинара по векторному и тензорному анализу с их прило-
13. жениями к геометрии, механике и физике, 2011. Т.27. С.83-105.
14. Иванов А. О.,Овсянников З. Н., Стрелкова Н. П., Тужилин А. А. Одномерные минималь-
15. ные заполнения с ребрами отрицательного веса // Вестн. Моск. унив., Матем. Мех. 2012.
16. №5. С.3-8.
17. Иванов А. О., Тужилин А. А., Цислик Д. Отношение Штейнера для многообразий //
18. Матем. заметки, 2003. Т.74, №3. С.387-395.
19. Овсянников З.Н. Открытое семейство множеств, для которых минимальное заполнение не
20. единственно // Фунд. и прикл. матем. 2013. Т.18, № 2. С.153-156.
21. Беднов Б. Б. Длина минимального заполнения пятиточечного метрического пространства
22. // Вестн. Моск. унив., Матем. Мех. 2017. №6. С.3-8.
23. Беднов Б. Б. О множестве точек Штейнера четырех элементов в пространстве Линден-
24. штраусса // Вестн. Моск. унив., Матем. мех. 2019. №6. С.3-8.
25. Беднов Б. Б. Длина минимального заполнения типа звезды // Матем. сб. 2016. Т.207, №8.
26. С.31-46.
27. Беднов Б. Б., Бородин П. А. Банаховы пространства, реализующие минимальные запол-
28. нения // Матем. сб., 2014. Т.205, №4. С.3-20.
29. Пахомова А. С. Критерий непрерывности отношений типа Штейнера в пространстве
30. Громова-Хаусдорфа // Матем. заметки, 2014. Т.96, №1. С.126-137.
31. Рублева О.В. Критерий аддитивности конечного метрического пространства и минималь-
32. ные заполнения// Вестн. Моск. унив., Матем. Мех. 2012. №2.С.8-11.
Рецензия
Для цитирования:
Щербаков О.С. Многогранники бинарных деревьев, строение многогранника дерева типа «змея». Чебышевский сборник. 2022;23(4):136-151. https://doi.org/10.22405/2226-8383-2022-23-4-136-151
For citation:
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
Просмотров:
248
Послать статью по эл. почте 