223
правки
Изменения
Нет описания правки
[[Дерево, эквивалентные определения |Дерево]] — планарный граф. Согласно Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева или же, воспользовавшись [[Формула ЭйлераТеорема_Понтрягина-Куратовского|следствию из формулы Эйлератеоремой Понтрягина-Куратовского]]: для дерева с , заметить, что раз этот граф по определению не содержит циклов, значит и подграфов, гомеоморфных <tex>K_{5}</tex> или <tex>NK_{3, 3}</tex> вершинами содержать не может, а значит он планарен. По формуле Эйлера <tex>N V - E + F = 2, V - (V - 1 ) + F = 2 \le 3 \cdot N - 6Leftrightarrow F = 1 </tex>.
== Укладка дерева ==
[[Файл:Layer-graph.jpg|250px|right|thumb|Рисунок 1. Пример поуровневой укладки дерева.]]
Существуют несколько способов укладки дерева на плоскости.
=== Поуровневая укладка ===
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения(''layered drawing''), при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера <tex>O(N^2)</tex> (где <tex>N</tex> — число вершин дерева).
=== Радиальная поуровневая укладка ===
[[Файл:Circle_layered_tree.jpg|250px|right|thumb|Тот же графРисунок 2. Граф из рисунка 1, но уложенный радиально.]]Радиальная поуровневая укладка (''radial drawing'') дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты.
Выбор угла <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>.
Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.
[[Файл:Hv_tree.jpg|250px|left|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]]
=== hv-изображения ===
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
