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

А. О. Иванов^ab, Д. А. Марханов<sup>b

a</sup> Московский государственный технический университет им. Н.Э. Баумана (г. Москва)
^b Московский государственный университет им. М. В. Ломоносова (г. Москва)

Аннотация: Задача о поиске минимальных параметрических заполнений конечного метрического пространства $M$ сводится к классической задаче линейного программирования. Множество допустимых значений двойственной задачи представляет собой выпуклый многогранник $\Lambda_G$, который зависит только от типа заполнения $G$ — дерева, множество вершин степени $1$ которого совпадает с $M$, а остальные вершины имеют степень $3$ (такие деревья называются бинарными, соединяющими $M$). Вершины этого многогранника играют важную роль при вычислении веса минимального заполнения.
Изоморфным бинарным деревьям, соединяющим одно и тоже пространство $M$, соответствуют, вообще говоря, разные многогранники. В данной работе получен полный ответ на вопрос о том, как они связаны между собой. Кроме того, в работе обсуждается вопрос об устройстве объединения $U$ множеств вершин всех многогранников $\Lambda_G$, соответствующих всевозможным бинарным деревьям $G$, соединяющим данное множество $M$. Множество $U=U(m)$ зависит только от количества $m$ точек в множестве $M$. Оказывается при $m\le 6$ множество $U(m)$ является выпуклым, то есть представляет собой множество вершин некоторого выпуклого многогранника. Выпуклость $U(m)$ при больших $m$ — это открытый вопрос.

Ключевые слова: конечное метрическое пространство, минимальное параметрическое заполнение, линейное программирование, многогранник бинарного дерева, группа перестановок, выпуклость.

УДК: 515.124.4+519.852.3

Поступила в редакцию: 15.11.2024
Принята в печать: 07.04.2025

DOI: 10.22405/2226-8383-2025-26-2-101-124