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

Материал из Викиконспекты
Перейти к: навигация, поиск
(hv-изображения)
(hv-изображения)
Строка 12: Строка 12:
 
Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.
 
Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.
 
=== hv-изображения ===
 
=== hv-изображения ===
Для hv-изображения дерева для каждой вершины <tex>p</tex> выполняются следующие свойства:
+
При hv-изображении дерева для каждой вершины <tex>p</tex> выполняются следующие свойства:
 
* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex> либо по горизонтали справа, либо по вертикали вниз;
 
* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex> либо по горизонтали справа, либо по вертикали вниз;
 
* не пересекаются минимальные прямоугольники с горизонтальными и вертикальными вершинами, покрывающие поддеревья вершины <tex>p</tex>.  
 
* не пересекаются минимальные прямоугольники с горизонтальными и вертикальными вершинами, покрывающие поддеревья вершины <tex>p</tex>.  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов ]]
 
[[Категория: Укладки графов ]]

Версия 09:12, 27 октября 2010

Дерево — планарный граф. Согласно следствию из формулы Эйлера: для дерева с [math]N[/math] вершинами [math]N - 1 \le 3 \cdot N - 6[/math].

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

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

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

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

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

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

Выбор угла [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].

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

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

При hv-изображении дерева для каждой вершины [math]p[/math] выполняются следующие свойства:

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