Аннотация:
Мультиобходы и многогранники бинарных деревьев возникли при изучении задачи о минимальном заполнении конечного метрического пространства, которая появилась в работах Иванова и Тужилина как обобщение задачи Штейнера о кратчайшей сети и задачи Громова о минимальном заполнении гладкого риманова многообразия.
Бинарным деревом назовём дерево, у которого степени вершин могут быть равны 1 или 3. Мультиобход бинарного дерева — это обобщение понятия обхода, но каждое ребро проходится 2k раз. По каждому бинарному дереву G можно построить выпуклый многогранник X(G), т.н. многогранник бинарного дерева. Ранее было доказано, что между вершинами многогранника и неприводимыми мультиобходами существует естественная биекция. Для некоторых типов бинарных деревьев удалось явно получить множество вершин соответствующих многогранников.
Напомним, что усами бинарного дерева называется пара граничных вершин (вершин степени 1), имеющих общую смежную вершину. Если удалить усы, то получим снова бинарное дерево G', у которого число листьев на 1 меньше. Оказывается, что операция удаления усов индуцирует проекцию многогранника X(G) на X(G'), из этого получается ряд интересных следствий.
|
