аспирант
postgraduate student
В данной работе изучаются минимальные заполнения конечных метрических пространств (объект, возникший как обобщение понятий кратчайшего дерева и минимального заполнения в смысле Громова). Как известно, вес минимального заполнения данного типа может быть найден как решение задачи линейного программирования или с помощью так называемых мультиобходов. Связь между этими двумя подходами можно проследить, перейдя к двойственной задаче линейного программирования: рациональные точки выпуклого многогранника, который строится по типу заполнения, соответствуют мультиобходам.Данная работа посвящена изучению таких многогранников. Показано, что их вершины соответствуют неприводимым мультиобходам. Получена описание многогранника и явнаяформула веса для минимального параметрического заполнения бинарного дерева типа «змея».
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 linearprogramming 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 polytopconstructed 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.
The authors declare that there are no conflicts of interest present.