Асимптотически оптимальные гомеоморфные двусторонние вложения полных троичных деревьев в прямоугольные решетки
Дискретная математика · 2026 · 38 (2) · 35-52
DOI: 10.4213/dm1898 ↗Kurz gefasst
Fachartikel in der Zeitschrift Дискретная математика, online erschienen am 29.05.2026. Verfasst von Sergei Andreevich Lozhkin und 1 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Gefördert von: Ministry of Science and Higher Education of the Russian Federation.
Abstract (Originalsprache)
Рассматривается задача построения гомеоморфного вложения полного троичного $n$-ярусного, $n=1,2,…$, дерева в прямоугольную решетку с расположением листьев дерева на ее горизонтальных сторонах. Доказано, что минимально возможная площадь такой решетки асимптотически не меньше чем $n \cdot 3^{n-1}$, и построено вложение указанного вида в решетку, высота и длина которой асимптотически равны $\frac{2}{3}n$ и $\frac{3^n}{2}$ соответственно.
Förderung
- Ministry of Science and Higher Education of the Russian Federation
Zitieren
APA
Lozhkin, S. A., & Mo, D. (2026). Асимптотически оптимальные гомеоморфные двусторонние вложения полных троичных деревьев в прямоугольные решетки. Дискретная математика, 38(2), 35-52. https://doi.org/10.4213/dm1898
Vancouver
Lozhkin SA, Mo D. Асимптотически оптимальные гомеоморфные двусторонние вложения полных троичных деревьев в прямоугольные решетки. Дискретная математика. 2026;38(2):35-52. doi:10.4213/dm1898
BibTeX
@article{Lozhkin2026,
author = {Lozhkin, Sergei Andreevich and Mo, Di},
title = {Асимптотически оптимальные гомеоморфные двусторонние вложения полных троичных деревьев в прямоугольные решетки},
journal = {Дискретная математика},
year = {2026},
volume = {38},
number = {2},
pages = {35--52},
doi = {10.4213/dm1898}
}
EUVIMED