|
СЕМИНАРЫ |
Научно-исследовательский семинар по дискретной геометрии и геометрии чисел
|
|||
|
Мультиобходы и многогранники бинарных деревьев Щербаков Олег Университетская гимназия МГУ |
|||
Аннотация: Минимальные заполнения конечных метрических пространств — объект, возникший как обобщение понятий кратчайшего дерева и минимального заполнения в смысле Громова. Как известно, вес минимального заполнения данного типа может быть найден как решение задачи линейного программирования или в терминах так называемых неприводимых мультиобходов бинарных деревьев, о чем далее подробнее. Бинарное дерево — дерево у которого степень каждой вершины 1 или 3. Мультиобход, грубо говоря, — это цикл, состоящий из простых путей между граничными вершинами дерева и проходящий через каждое ребро ровно 2ℓ раз. Из множества мультиобходов можно построить аддитивную полугруппу, при этом естественно возникают т.н. неприводимые мультиобходы. Мультиобход σ называется неприводимым, если мультиобход nσ не раскладывается нетривиальным образом в сумму ξ + η. Каждому бинарному дереву с m граничными вершинами можно поставить в соответствие некоторый выпуклый многогранник размерности |