Укладка дерева — различия между версиями
м |
|||
| Строка 1: | Строка 1: | ||
| − | [[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По формуле Эйлера <tex>V - E + F = 2, V - (V - 1) + F = 2 \Leftrightarrow F = 1 </tex>. | + | [[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 \Leftrightarrow F = 1 </tex>. |
== Укладка дерева == | == Укладка дерева == | ||
| Строка 12: | Строка 12: | ||
Выбор угла <tex>\beta_p</tex> секторного сегмента для поддерева с корнем <tex>p</tex> и количеством вершин <tex>l(p)</tex> определяется следующим образом: пусть вершина <tex>p</tex> лежит на уровне <tex>C_i</tex>, тогда для каждого ее сына <tex>q</tex> имеем: <tex>\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)</tex>, где <tex>\tau</tex> — это угол области <tex>F_p</tex>, определяемой пересечением касательной к точке <tex>p</tex> уровня <tex>C_i</tex> и окружностью уровня <tex>C_{i+1}</tex>. | Выбор угла <tex>\beta_p</tex> секторного сегмента для поддерева с корнем <tex>p</tex> и количеством вершин <tex>l(p)</tex> определяется следующим образом: пусть вершина <tex>p</tex> лежит на уровне <tex>C_i</tex>, тогда для каждого ее сына <tex>q</tex> имеем: <tex>\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)</tex>, где <tex>\tau</tex> — это угол области <tex>F_p</tex>, определяемой пересечением касательной к точке <tex>p</tex> уровня <tex>C_i</tex> и окружностью уровня <tex>C_{i+1}</tex>. | ||
| − | Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин. | + | Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин <ref name="Центральная вершина">Центральная вершина - эта такая вершина, для которой расстояние до самой удаленной от нее вершины - минимально среди всех вершин графа. Формально: Пусть <tex>r(p) = \underset{u:u\in V(G)}{sup} dist(p, u)</tex>, тогда <tex>p</tex> - центральная, если <tex>r(p) = \underset{v:v\in V(G)}{inf} r(v)</tex>. Понятно, что таких вершин может быть несколько. Под расстоянием здесь подразумевается длина кратчайшего пути.</ref>. |
[[Файл:Hv_tree.jpg|250px|left|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]] | [[Файл:Hv_tree.jpg|250px|left|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]] | ||
=== hv-изображения === | === hv-изображения === | ||
| Строка 24: | Строка 24: | ||
<br/> | <br/> | ||
| − | < | + | ==Примечания== |
| + | <references/> | ||
| + | |||
==Ссылки== | ==Ссылки== | ||
* [http://sydney.edu.au/engineering/it/~shhong/comp5048-lec2.pdf Tree Drawing Algorithms and Tree Visualisation Methods (PDF)] | * [http://sydney.edu.au/engineering/it/~shhong/comp5048-lec2.pdf Tree Drawing Algorithms and Tree Visualisation Methods (PDF)] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Укладки графов ]] | [[Категория: Укладки графов ]] | ||
Версия 21:53, 6 февраля 2012
Дерево — планарный граф. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По формуле Эйлера: .
Содержание
Укладка дерева
Существуют несколько способов укладки дерева на плоскости.
Поуровневая укладка
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения (layered drawing), при котором вершины глубины имеют координату , а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми (см. рисунок 1). Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера (где — число вершин дерева).
Радиальная поуровневая укладка
Радиальная поуровневая укладка(radial drawing) дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты (см. рисунок 2).
Выбор угла секторного сегмента для поддерева с корнем и количеством вершин определяется следующим образом: пусть вершина лежит на уровне , тогда для каждого ее сына имеем: , где — это угол области , определяемой пересечением касательной к точке уровня и окружностью уровня .
Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин [1].
hv-изображения
Бинарные деревья можно изобразить при помощи hv-изображений (horizontal-vertical drawing, см. рисунок 3). При этом для каждой вершины выполняются следующие свойства:
- сын вершины ставится в ряд за либо по горизонтали справа, либо по вертикали вниз
- два прямоугольника, ограничивающие левое и правое поддерево вершины не пересекаются
Примечания
- ↑ Центральная вершина - эта такая вершина, для которой расстояние до самой удаленной от нее вершины - минимально среди всех вершин графа. Формально: Пусть , тогда - центральная, если . Понятно, что таких вершин может быть несколько. Под расстоянием здесь подразумевается длина кратчайшего пути.
