Изменения

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

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

'''Радиальная поуровневая укладка(''' ''(англ. radial drawing)'') дерева отличается тем, что его уровни имеют вид концентрических окружностей(см. рисунок 2). Вершины глубины <tex>a</tex> располагаются на окружностях с радиусом <tex>r = a</tex>, при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра). Определим способ выбора угла этого сектора для некоторого поддерева вершины <tex>p</tex> находящейся на уровне <tex>i</tex>. Пусть угол сектора для дерева с корнем <tex>p</tex> равен <tex>\beta_p</tex>. Пусть корень поддерева(непосредственный ребенок <tex>p</tex>) {{---}} вершина <tex>q</tex>, обозначим количество вершин в дереве с корнем <tex>q</tex> как <tex>l(q)</tex>.Тогда <tex>\beta_q = \min\left(\dfrac{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>, причем в качестве вершины, поддеревья занимают секторные сегментыразмещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]]. <br><br><br> 

Выбор угла <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|right|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]]

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

  ==См. также==*[[Укладка_графа_на_плоскости|Укладка графа на плоскости]]*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]*[[Гамма-алгоритм|Гамма-алгоритм]] ==Примечания==<brreferences/> ==СсылкиИсточники информации==