Укладка дерева — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева или же, воспользовавшись [[Теорема_Понтрягина-Куратовского|теоремой Понтрягина-Куратовского]], заметить, что раз этот граф по определению не содержит циклов, значит и подграфов, гомеоморфных <tex>K_{5}</tex> или <tex>K_{3, 3}</tex> содержать не может, а значит он планарен. По формуле Эйлера <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>.
  
 
== Укладка дерева ==
 
== Укладка дерева ==

Версия 22:59, 17 января 2012

Дерево — планарный граф. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По формуле Эйлера [math]V - E + F = 2, V - (V - 1) + F = 2 \Leftrightarrow F = 1 [/math].

Укладка дерева

Рисунок 1. Пример поуровневой укладки дерева.

Существуют несколько способов укладки дерева на плоскости.

Поуровневая укладка

Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения (layered drawing), при котором вершины глубины [math]a[/math] имеют координату [math]y = – a[/math], а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми (см. рисунок 1). Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера [math]O(N^2)[/math] (где [math]N[/math] — число вершин дерева).

Радиальная поуровневая укладка

Рисунок 2. Граф из рисунка 1, но уложенный радиально.

Радиальная поуровневая укладка(radial drawing) дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты (см. рисунок 2).

Выбор угла [math]\beta_p[/math] секторного сегмента для поддерева с корнем [math]p[/math] и количеством вершин [math]l(p)[/math] определяется следующим образом: пусть вершина [math]p[/math] лежит на уровне [math]C_i[/math], тогда для каждого ее сына [math]q[/math] имеем: [math]\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)[/math], где [math]\tau[/math] — это угол области [math]F_p[/math], определяемой пересечением касательной к точке [math]p[/math] уровня [math]C_i[/math] и окружностью уровня [math]C_{i+1}[/math].

Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.

Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.

hv-изображения

Бинарные деревья можно изобразить при помощи hv-изображений (horizontal-vertical drawing, см. рисунок 3). При этом для каждой вершины [math]p[/math] выполняются следующие свойства:

  • сын вершины [math]p[/math] ставится в ряд за [math]p[/math] либо по горизонтали справа, либо по вертикали вниз
  • два прямоугольника, ограничивающие левое и правое поддерево вершины [math]p[/math] не пересекаются







Ссылки