Изменения

[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 </tex> <tex dpi=150> \Leftrightarrow</tex><tex> F = 1 </tex>. Значит дерево можно уложить на плоскость и у него будет только одна грань.Для произвольных графов есть [[Гамма-алгоритм|гамма-алгоритм]], который проверяет произвольный граф на планарность.

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

Тогда <tex dpi=140>\beta_q = \min\left(\fracdfrac{l(q)}{l(p)}\beta_p, \tau\right)</tex>, где <tex>\tau</tex> — это угол области <tex>F_p</tex>, определяемой пересечением касательной в точке <tex>p</tex> к окружности уровня <tex>i</tex> и окружностью уровня <tex>i+1</tex>. Угол <tex>\tau</tex> необходим для того, чтобы отрезок <tex>pq</tex> не пересек окружность уровня <tex>i</tex>.

Радиальное изображение дерева часто используют для представления свободных деревьев<ref name = "Свободное дерево">Под свободными деревьями ''(англ. free trees)'' понимают деревья без выделенного корня. </ref>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин <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>]].<br>

[[Дерево_поиска,_наивная_реализация|Бинарные деревья<ref name = "Бинарное дерево">Бинарное дерево (двоичное дерево) ''(англ. binary tree)'', то есть такое дерево, у каждой вершины которого не более двух поддеревьев.</ref> ]] можно изобразить при помощи '''hv-изображений''' ''(англ. horizontal-vertical drawing)'' (см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства:* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex> : либо по горизонтали справа, либо по вертикали вниз* ; два прямоугольника, ограничивающие левое и правое поддерево вершины <tex>p</tex> , не пересекаются.

==СсылкиИсточники информации==