Некоторые близкие к оптимальным вложения полных двоичных и троичных деревьев в прямоугольные решетки минимальной длины

Поступила: 15.01.2025

Принята к публикации: 31.01.2025

Дата публикации в журнале: 20.06.2025

Ключевые слова: вложение деревьев, прямоугольные решетки, минимальная длина

DOI: 10.55959/MSU/0137–0782–15–2025–49–2–30–37

Для цитирования статьи

Ложкин С.А., Мо Ди Некоторые близкие к оптимальным вложения полных двоичных и троичных деревьев в прямоугольные решетки минимальной длины // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2025. № 2. С. 30-37 https://doi.org/10.55959/MSU/0137–0782–15–2025–49–2–30–37.

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция-Некоммерчески») 4.0 Всемирная

Ложкин С.А. (Московский государственный университет им. М.В. Ломоносова (МГУ))
Мо Ди (Московский государственный университет им. М.В. Ломоносова (МГУ))

Аннотация

В работе решается задача конструктивного построения вложений полных корневых двоичных и троичных деревьев с k, k = 1, 2, . . . , ярусами в прямоугольные решетки (ПР), имеющие минимальную длину и близкую к минимальной высоту. При этом предполагается, что различные вершины дерева переходят в различные (основные) вершины ПР, причем листья дерева переходят в вершины ПР, расположенные на ее горизонтальных сторонах. Предполагается также, что ребра дерева переходят в простые (транзитные) цепи ПР, соединяющие образы их концевых вершин и не проходящие через другие основные вершины, причем через одно и то же ребро (одну и ту же вершину) ПР проходит не более 1 (соответственно 2) транзитных цепей.

Литература

Ложкин С.А., Ли Да Мин. О некоторых оптимальных вложениях двоичных и троичных деревьев в плоские прямоугольные решетки // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибер. 1995. № 4. С. 49–55.
Ли Да Мин. Некоторые оптимальные вложения древовидных графов в плоские прямоугольные решетки: Дис. . . . канд. физ.-матем. наук. МГУ, 1994.
Высоцкий Л.И., Ложкин С.А. Оптимальные двусторонние вложения полных двоичных деревьев в прямоугольные решетки // Прикладная математика и информатика. № 59. М.: МАКС Пресс, 2018. С. 25–39.
Ложкин С.А., Высоцкий Л.И. О некоторых асимптотически оптимальных односторонних вложениях деревьев подобных формул в прямоугольные решетки // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибер. 2017. № 2. С. 38–45.
Ложкин С.А., Мо Ди. Оптимальные вложения троичных деревьев подобных формул в прямоугольные решетки // Материалы конф. ДМТУС-11 2023. М.: МАКС Пресс, 2023. С. 72–74.
Ложкин С.А. Лекции по основам кибернетики. М.: Изд-во Моск. ун-та, 2004.