Укладка дерева — различия между версиями
Exprmntr (обсуждение | вклад) (Новая страница: «Дерево — планарный граф. Согласно [[Формула Эйлера|с…») |
Exprmntr (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за полиномиальное время, позволяющая получить оптимальное по ширине плоское дерево. | Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за полиномиальное время, позволяющая получить оптимальное по ширине плоское дерево. | ||
=== Радиальная поуровневая укладка === | === Радиальная поуровневая укладка === | ||
| − | Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты. | + | Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты. |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Укладки графов ]] | [[Категория: Укладки графов ]] | ||
Версия 20:39, 21 октября 2010
Дерево — планарный граф. Согласно следствию из формулы Эйлера: для дерева с вершинами .
Укладка дерева
Существуют несколько способов укладки дерева на плоскости.
Поуровневая укладка
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины имеют координату , а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за полиномиальное время, позволяющая получить оптимальное по ширине плоское дерево.
Радиальная поуровневая укладка
Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты.
