Существование неприводимых мультиобходов кратности 2

Ивановым и Тужилиным была предложена одномерная проблема Громова о минимальном заполнении конечных метрических пространств, где в качестве заполнений рассматриваются взвешенные графы с неотрицательными весами ребер. Они показали, что задача редуцируется к случаю так называемых бинарных деревьев — деревьев у которых вершины имеют только степени 1 и 3. Ерёминым была получена минимаксная формула веса минимального заполнения. Формула Ерёмина использует понятие минимального параметрического заполнения — фиксируется граф (параметризация или тип); он показал, что вес минимального параметрического заполнения равен максимальному значению так называемого мультипириметра среди всех неприводимых мультиобходов.
Сложность структуры бинарного дерева можно измерять количеством так называемых усов — пар граничных вершин с общей смежной вершиной. Настоящая работа посвящена изучению мультиобходов бинарных деревьев с тремя усами. Найдена линейная рекуррентная формула для числа бинарных деревьев с тремя усами. Установлена связь между неприводимостью мультиобходов и включениями мультиграфов мультиобходов для
фиксированного бинарного дерева.
Недавно Щербаковым было доказано, что кратность неприводимого мультиобхода для
бинарного дерева с тремя усами не превосходит 2, в этой работе доказано существование
таких неприводимых мультиобходов у любого такого бинарного дерева.
Недавно Иванов и Тужилин предложили вычислять вес минимального параметрического заполнения, находя вершины многомерного многогранника допустимых значений переменных двойственной задачи линейного программирования с помощью компьютера.
Разработанная в настоящей работе техника позволяет найти все неприводимые мультиобходы у бинарного дерева с 6 граничными вершинами и 3 усами без использования компьютерных вычислений.

1. Иванов, А.О., Тужилин, А.А. Одномерная проблема Громова о минимальном заполнении // Матем. сб. 2012. Т. 203, № 5.С. 65-118.

2. Ivanov, A., Tuzhilin, A. Dual Linear Programming Problem and One-Dimensional Gromov

3. Minimal Fillings of Finite Metric Space // Differential Equations on Manifolds and Mathematical Physics. Trends in Mathematics. Birkhauser, Cham. 2022. pp. 165-182.

4. Ivanov, A.O., Tuzhilin, A.A. Minimal fillings of finite metric spaces: The state of the art //

5. Discrete Geometry and Algebraic Combinatorics. - Vol. 625 of Contemporary Mathematics. - United States: AMS Press, 2014. pp. 9-35.

6. Еремин, А.Ю. Формула веса минимального заполнения конечного метрического пространства. Матем. сб. 2013. Т.204, № 9. С.51-72.

7. Иванов, А.О., Тужилин, А.А. Задача Штейнера на плоскости или плоские минимальные сети, Матем. сб. 1991. Т. 182, № 12, с.1813–1844

8. Gromov, M. Filling Riemanian Manifolds // J.Differential Geom. 1983. vol.18, № 1. pp.1-147.

9. Беднов, Б.Б., Бородин, П.А. Банаховы пространства, реализующие минимальные заполнения. Матем. сб. 2014. т.205 № 4, 3–20;

10. Степанова, Е.И. Бифуркации минимальных деревьев Штейнера и минимальных заполнений для невыпуклых четырехточечных границ и суботношение Штейнера на евклидовом плоскости // Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 2. С.48-51.

11. Степанова, Е.И. Бифуркации минимальных заполнений для четырех точек евклидовой плоскости // Фундамент. и прикл. матем. 2019. Т. 22, № 6. С. 253–261.

12. Рублева, О.В. Критерий аддитивности конечного метрического пространства и минимальные заполнения // Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2012. № 2. С.8-11.

13. Овсянников, З.Н. Открытое семейство множеств, для которых минимальное заполнение не единственно // Фунд. и прикл. матем. 2013. Т.18, № 2. С.153-156.

14. Иванов, А.О., Овсянников, З.Н., Стрелкова, Н.П., Тужилин, А.А. Одномерные минимальные заполнения с ребрами отрицательного веса // Вестн. Моск. унив., Матем. Мех. 2012. № 5. С.3-8.

15. Щербаков, О.С. Многогранники бинарных деревьев, строение многогранника дерева типа «змея». Чебышёвский сб. 2022. Т.23, № 85. С.136-151.

16. Щербаков, О.С. Оценки на кратности неприводимых мультиобходов некоторых бинарных деревьев. Вестн. Моск. ун-та. Сер. 1. Матем., мех. 2025, № 2.

17. Васильев, Ф.П., Иваницкий, А.Ю. Линейное программирование. М.: МЦНМО, 2020.

18. Смирнов, Е.Ю. Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. М: МЦНМО, 2014.

19. Ландо, С.К. Введение в дискретную математику. М: МЦНМО, 2014.

20. Пахомова, А.С. Оценки для суботношения Штейнера и отношения Штейнера–Громова, Вестн. Моск. ун-та. Сер. 1. Матем., мех. 2014. № 1, С.17–25.