Мультиобходы и многогранники бинарных деревьев

Минимальные заполнения конечных метрических пространств — объект, возникший как обобщение понятий кратчайшего дерева и минимального заполнения в смысле Громова. Как известно, вес минимального заполнения данного типа может быть найден как решение задачи линейного программирования или в терминах так называемых неприводимых мультиобходов бинарных деревьев, о чем далее подробнее. Бинарное дерево — дерево у которого степень каждой вершины 1 или 3. Мультиобход, грубо говоря, — это цикл, состоящий из простых путей между граничными вершинами дерева и проходящий через каждое ребро ровно 2ℓ раз. Из множества мультиобходов можно построить аддитивную полугруппу, при этом естественно возникают т.н. неприводимые мультиобходы. Мультиобход σ называется неприводимым, если мультиобход nσ не раскладывается нетривиальным образом в сумму ξ + η. Каждому бинарному дереву с m граничными вершинами можно поставить в соответствие некоторый выпуклый многогранник размерности $C^2_m−2$ (это некоторое допустимое множество в задаче линейного программирования). Оказалось, что вершины многогранника находятся во взаимно-однозначном соответствии с неприводимыми мультиобходами. Автору удалось получить ряд результатов: • Найдены координаты вершин многогранника и формула веса минимального параметрического заполнения для бинарного дерева типа “змея”, оказывется это некоторые вершины многомерного куба. • Для бинарного дерева с тремя парами т.н. “усов” ограничена кратность неприводимого мультиобхода числом 2. • Получена формула веса минимального параметрического заполнения для бинарного дерева с тремя парами т.н. “усов”. • Доказано существование неприводимых мультиобходов кратности 2 у любого бинарного дерева с не менее чем 3 парами усов. • Кратность неприводимого мультиобхода для бинарного дерева, построенного из 4 т.н. “побегов”, не превосходит 4. • Найдена т.н. нормальная форма мультиобходов. • Верхняя оценка на кратность неприводимого мультиобхода для бинарного дерева на m вершинах равна m.