доктор физико-математических наук, профессор
doctor of physical and mathematical sciences, professor
Ивановым и Тужилиным была предложена одномерная проблема Громова о минимальном заполнении конечных метрических пространств, где в качестве заполнений рассматриваются взвешенные графы с неотрицательными весами ребер. Они показали, что задача редуцируется к случаю так называемых бинарных деревьев — деревьев у которых вершины имеют только степени 1 и 3. Ерёминым была получена минимаксная формула веса минимального заполнения. Формула Ерёмина использует понятие минимального параметрического заполнения — фиксируется граф (параметризация или тип); он показал, что вес минимального параметрического заполнения равен максимальному значению так называемого мультипириметра среди всех неприводимых мультиобходов.Сложность структуры бинарного дерева можно измерять количеством так называемых усов — пар граничных вершин с общей смежной вершиной. Настоящая работа посвящена изучению мультиобходов бинарных деревьев с тремя усами. Найдена линейная рекуррентная формула для числа бинарных деревьев с тремя усами. Установлена связь между неприводимостью мультиобходов и включениями мультиграфов мультиобходов дляфиксированного бинарного дерева.Недавно Щербаковым было доказано, что кратность неприводимого мультиобхода длябинарного дерева с тремя усами не превосходит 2, в этой работе доказано существованиетаких неприводимых мультиобходов у любого такого бинарного дерева.Недавно Иванов и Тужилин предложили вычислять вес минимального параметрического заполнения, находя вершины многомерного многогранника допустимых значений переменных двойственной задачи линейного программирования с помощью компьютера.Разработанная в настоящей работе техника позволяет найти все неприводимые мультиобходы у бинарного дерева с 6 граничными вершинами и 3 усами без использования компьютерных вычислений.
Ivanov and Tuzhilin stated the problem of one-dimensional Gromov minimal filling of finite metric spaces, where the filling is considered as a weighted connected graph containing the metric space as a subset of its vertex set. They shown that the problem can be always reduced to the case of so-called binary trees — trees whose vertices have degrees 1 and 3 only. Later Eremin obtained a minimax formula for the weight of the minimal filling. Eremin’s formula uses the concept of minimum parametric filling, i.e. the filling with a fixed graph (parameterization or type), and the weight of the minimal parametric filling turns out to be equal to the maximum value of so-called multi-perimeters over all irreducible multi-tours.Moustaches of a binary tree is a pair of its vertices of degree 1 having a common adjacent vertex. The number of moustaches can measure complexity of binary trees. In this paper the multi-tours of binary trees with 3 moustaches are investigated. A linear recurrent formula is found for the number of such binary trees. For a fixed binary tree a connection is established between the irreducibility of multi-tours and inclusions of multi-tours multi-graphs.Recently Shcherbakov proved that the multiplicity of an irreducible multi-tour for a binary tree with 3 moustaches does not exceed 2; in this paper the existence of such irreducible multitour for any binary tree with 3 moustaches is proved.Ivanov and Tuzhilin proposed to calculate the weight of a minimal parametric filling by finding the vertices of a multidimensional polyhedron of feasible variable values of the dual linear programming problem. These their results are based on computer calculations. The technique developed in this paper permits to find all irreducible multi-tours of a binary tree with 6 boundary vertices and 3 moustaches without a computer.
The authors declare that there are no conflicts of interest present.