В данной работе изучаются минимальные заполнения конечных метрических пространств (объект, возникший как обобщение понятий кратчайшего дерева и минимального заполнения в смысле Громова). Как известно, вес минимального заполнения данного типа может быть найден как решение задачи линейного программирования или с помощью так называемых мультиобходов. Связь между этими двумя подходами можно проследить, перейдя к двойственной задаче линейного программирования: рациональные точки выпуклого многогранника, который строится по типу заполнения, соответствуют мультиобходам. Данная работа посвящена изучению таких многогранников. Показано, что их вершины соответствуют неприводимым мультиобходам. Получена описание многогранника и явная формула веса для минимального параметрического заполнения бинарного дерева типа 'змея'.

многогранники, бинарные деревья

Щербаков Олег Сергеевич,  Московский государственный университет