| Математические заметки |
|
|
|
|
|
Краткие сообщения Нормальная форма мультиобходов бинарных деревьев О. С. Щербаков Московский государственный технический университет им. Н. Э. Баумана
Англоязычная версия:
Mathematical Notes, 2024, Volume 116, Issue 4, Pages DOI: https://doi.org/10.1134/S0001434624090438 
Реферативные базы данных:
 1. Введение и необходимые определенияЗадача о минимальном заполнении конечного метрического пространства появилась в [1] как обобщение задачи Штейнера о кратчайшей сети и задачи Громова о минимальном заполнении гладкого риманова многообразия. Пусть $\mathcal{M}=(M,\rho)$ – конечное псевдометрическое пространство, $G=(V,E)$ – связный граф, соединяющий $M$ (т.е. $M\subset V$), и $\omega\colon E\to [0;\infty)$ – весовая функция, которая порождает взвешенный граф $\mathcal{G}=(G,\omega)$. Весом взвешенного графа $\mathcal{G}$ называем сумму $\sum_{e\in E}\omega(e)$ и обозначим $\omega(\mathcal{G})$. Аналогично вес пути в графе равен сумме весов всех входящих в него ребер. Весовая функция $\omega$ порождает псевдометрику $d_\omega$ на множестве вершин графа $G$, а именно, расстояние между вершинами равно наименьшему возможному весу пути в графе $G$, соединяющему эти вершины. Если для любых $i,j\in M$ выполнено условие $\rho(i,j)\leqslant d_{\omega}(i,j)$, то взвешенный граф $\mathcal{G}$ называют заполнением пространства $\mathcal{M}$, а граф $G$ – типом этого заполнения. Весом минимального заполнения называется число $\operatorname{mf}{\mathcal{M}}$, равное $\inf \omega(\mathcal{G})$ по всем заполнениям $\mathcal{G}$ пространства $\mathcal{M}$. Заполнение $\mathcal{G}$, для которого $\omega(G)=\operatorname{mf}(\mathcal{M})$, называют минимальным заполнением. Если в задаче зафиксировать граф $G$ (тип заполнения), то говорят о минимальном параметрическом заполнении. Дерево $G$ называем бинарным, если у него есть только вершины степени 1 и 3. Множество бинарных деревьев обозначим $\mathfrak{B}$. Вершины степени 1 называем граничными, вершины степени 3 – внутренними. В [1; теорема 2.1] показано, что для любого псевдометрического пространства $\mathcal{M}$ существует минимальное заполнение, имеющее тип бинарного дерева $G$ с множеством граничных вершин $\partial G=M$. В работе [2] получена формула веса минимального заполнения в терминах так называемых мультиобходов, к определению которых мы переходим. Элементы пространства $M$ будем обозначать натуральными числами от $1$ до $|M|$. Мультициклический порядок кратности $l$ на множестве $M$ мощности $|M|=m$ – это отображение $\sigma\colon \mathbb{Z}_{ml}\to M$ такое, что
$$
\begin{equation*}
\Gamma^{\sigma}:=\lbrace \Gamma_{\sigma(0)\sigma(1)}, \Gamma_{\sigma(1)\sigma(2)}, \dots, \Gamma_{\sigma(ml-1)\sigma(0)} \rbrace.
\end{equation*}
\notag
$$
Согласно [2; предложение 2.6] мультиобходом кратности $l$ (или $l$-обходом) дерева $G\in\mathfrak{B}$ с границей $\partial G=M$ назовем такой мультициклический порядок $\sigma$, что через каждое ребро дерева $G$ проходит ровно $2l$ путей из $\Gamma^{\sigma}$. По всякому мультиобходу построим целочисленный неотрицательный вектор мультиобхода $w^{\sigma}=(\sigma_{12},\dots, \sigma_{(m-1)\,m})\in \mathbb{R}^{C_m^2}$, координаты которого соответствуют неупорядоченным парам точек из $\partial G$, и $\sigma_{ij}$ равно числу граничных путей $\Gamma_{ij}$ из мультимножества $\Gamma^{\sigma}$. По дереву $G$ построим матрицу разрезов $A=(a_{ij}^k)$ полного графа $K(M)$, где элемент $a_{ij}^k$ положим равным $1$, если $e_{k}\in \Gamma_{ij}$ и $0$ в противном случае. Столбцы матрицы индексированы неупорядоченными парами $ij$ вершин $V$, а строки соответствуют ребрам $E$ дерева $G$. Замечание 3.1 и теорема 3.3 из [2] могут быть сформулированы следующим образом: Теорема 1. Вектор $u\in\mathbb{R}^{C_{m}^2} $ с целыми неотрицательными координатами является вектором $l$-обхода тогда и только тогда, когда $Au=2l(1,1,\dots,1)^\top$. Эта теорема позволяет корректно ввести отношение эквивалентности на множестве мультиобходов и определить сумму мультиобходов и умножение мультиобхода на натуральное число (подробнее см. [2]). Мультиобходы $\sigma$ и $\tau$ называются эквивалентными ($\sigma\cong\tau$), если $w^\sigma=w^{\tau}$. Фактормножество мультиобходов бинарного дерева $G$ по указанному отношению эквивалентности обозначим $\mathcal{T}(G)$. Суммой мультиобходов $\sigma$ и $\tau$ кратностей $l_1$ и $l_2$ называется мультиобход $\xi$ кратности $l_1+l_2$ такой, что $w^{\xi}=w^{\sigma}+w^{\tau}$. Произведением мультиобхода $\sigma$ на натуральное число $n$ называется такой мультиобход $\xi$, что $w^\xi=nw^\sigma$. Мультиобход $\sigma$ называется неприводимым, если $n\sigma$ не раскладывается в сумму мультиобходов нетривиальным образом, т.е. из равенства $n{\sigma}\cong\tau+{\xi}$ следует, что ${\tau}\cong k\sigma$, ${\xi}\cong (n-k)\sigma$. Подмножество в $\mathcal{T}(G)$, соответствующее неприводимым мультиобходам, обозначим $\mathcal{T'}(G)$. Мультипериметр метрического пространства $\mathcal{M}$ мультиобхода $\sigma$ кратности $l$ определяется формулой
$$
\begin{equation*}
p(\mathcal{M},\sigma):=\frac{1}{2l}\sum_{k=1}^{ml}\rho(\sigma(k-1),\sigma(k))
\end{equation*}
\notag
$$
(здесь $\sigma(ml)=\sigma(0)$). Формула веса минимального параметрического заполнения, полученная в работе [2], в наших обозначениях имеет вид
$$
\begin{equation*}
\operatorname{mf}{\mathcal{M}}=\min_{G\in \mathfrak{B}} \max_{\sigma \in \mathcal{T'}(G)}p(\mathcal{M},\sigma).
\end{equation*}
\notag
$$
Обозначим $\varkappa(G)$ максимальную кратность неприводимого мультиобхода дерева $G\in \mathfrak{B}$. В работе [2] дана оценка $\varkappa(G)\leqslant C_{m}^2!$; в работе [3] эта оценка была улучшена: $\varkappa(G)\leqslant 2^{2m-5}$. В настоящей работе показано (см. теорему 3), что $\varkappa(G)\leqslant m$. В работе [3] задача о минимальном параметрическом заполнении рассматривается как задача линейного программирования, а формула веса минимального заполнения получается с помощью перехода к двойственной задаче. Допустимое множество в двойственной задаче – выпуклый многогранник $\mathbf{X}(G)$ размерности $C_{m-2}^{2}$ в пространстве $\mathbb{R}^{C_m^2}$, состоящий из точек с неотрицательными координатами, для которых выполнено условие $Ax=(1,1,\dots,1)^\top$. В работе [4] установлена естественная биекция между вершинами $\mathbf{X}(G)$ и $\mathcal{T'}(G)$, таким образом, поиск множества $\mathcal{T'}(G)$ эквивалентен поиску вершин многогранника $\mathbf{X}(G)$. Компьютерный поиск вершин $\mathbf{X}(G)$ оказывается неэффективным уже для бинарного дерева с $m=|\partial G|=10$ и практически нереализуем при $m\geqslant 12$. Напомним, что усами бинарного дерева называется пара граничных вершин, имеющих общую смежную вершину. Для бинарных деревьев с двумя усами (так называемая “змея”) в работе [4] удалось явно найти все неприводимые мультиобходы $\mathcal{T'}(G)$ и соответственно вершины $\mathbf{X}(G)$: оказывается у таких бинарных деревьев нет неприводимых мультиобходов кратности выше 1. В работе [5] удалось доказать, что $\varkappa(G)\leqslant 2$ для бинарных деревьев с тремя усами. Ключевую роль в обоих случаях сыграла возможность установить, что всякий мультиобход эквивалентен мультиобходу определенного вида, затем получить ограничение на кратность, тем самым показав, что других неприводимых мультиобходов нет. Лемма 1 (переформулировка леммы 4 из [4]). Если пара граничных вершин $(a,b)$ образует усы, то координата $w_{ab}$ вектора $w^{\sigma}$ мультиобхода $\sigma$ кратности $l$ равна $l$. 2. Теорема о нормальной формеБудем обозначать мультиобходы подобно перестановкам, запись $\sigma=(i_0i_1\dots i_{lm-1})$ означает, что $\sigma(i_k)=i_{k+1}$ для всех $k\in \mathbb{Z}_{lm}$. Рассмотрим полный граф $K(M)$, обозначим цепи в $K(M)$, содержащие каждый элемент множества $M=\partial G$ ровно 1 раз, как $M_i$. Теорема 2. Для всякого $l$-обхода $\sigma$ бинарного дерева $G$ имеет место следующая эквивалентность: причем каждое выражение $(M_i)$ – 1-обход. Схема доказательства. Индукция по количеству $m$ граничных вершин. Для $m=2$ утверждение очевидно. Пусть оно верно для всех бинарных деревьев с не более чем $m-1$ граничной вершиной, и пусть $G$ – бинарное дерево c $m$, $m\geqslant 3$, граничными вершинами. Каждое такое дерево имеет усы, фиксируем усы с вершинами $a,b$ и общей соседней вершиной $c$. Пусть $\sigma$ – произвольный мультиобход дерева $G$ кратности $l$. По лемме 1 обход $\sigma$ содержит ровно $l$ пар вида $ab$ или $ba$. Построим бинарное дерево $G'$, удалив из дерева $G$ усы $a,b$ (вершины и ребра). Вершина $c$ является вершиной степени $1$ дерева $G'$. Заменяя в обходе $\sigma$ все пары $ab$ и $ba$ на $c$, получим обход $\sigma'$ дерева $G'$ той же кратности $l$. Для дерева $G'$ и обхода $\sigma'$ справедливо предположение индукции, поэтому обход $\sigma'$ эквивалентен обходу вида $M'_1\dots M'_l$, где каждый $M'_i$ представляет собой $1$-обход дерева $G'$. Заменяя в каждом $M'_i$ вершину $c$ на соответствующее $ab$ или $ba$, получим обход исходного дерева $G$, эквивалентный исходному обходу $\sigma$, что и требовалось доказать. Правую часть (*) назовем нормальной формой мультиобхода. 3. Ограничение на кратность неприводимого мультиобходаПонадобится следующая лемма [5; следствие 2]. Лемма 2. Пусть мультиобход $\sigma$ приводится к виду: где $\tau$ – тоже мультиобход. Тогда $\sigma$ приводим. Доказательство. Рассмотрим $(m+n)$-обход $\sigma$, $n>0$. Согласно предыдущей теореме $\sigma\cong (M_1\dots M_{m+n})$. Среди $m+n$ цепей имеются хотя бы 2 с одинаковым началом, поскольку имеется всего $m$ вершин. Пусть это цепи $M_i$ и $M_{i+j}$. Тогда $(M_{i}\dots M_{i+j-1})$ – $j$-обход, по лемме 2 получаем приводимость $\sigma$. Автор благодарит профессора А. О. Иванова за оказанное внимание к работе, помощь в оформлении настоящего текста и полезные обсуждения. 
Цитирование в формате AMSBIB
\RBibitem{Shc24} |
|
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|