Изменения

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

 [[Файл:Layer-graph.jpg|250px|right|thumb|Рисунок 1. Пример поуровневой укладки дерева.]]

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

Выбор [[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]'''Радиальная поуровневая укладка''' ''(англ. radial drawing)'' дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2). Вершины глубины <tex>a</tex> располагаются на окружностях с радиусом <tex>r = a</tex>, при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра). Определим способ выбора угла этого сектора для некоторого поддерева вершины <tex>p</tex> находящейся на уровне <tex>\beta_pi</tex> секторного сегмента . Пусть угол сектора для поддерева дерева с корнем <tex>p</tex> и количеством вершин равен <tex>\beta_p</tex>l. Пусть корень поддерева(непосредственный ребенок <tex>p)</tex> определяется следующим образом: пусть ) {{---}} вершина <tex>pq</tex> лежит на уровне , обозначим количество вершин в дереве с корнем <tex>C_iq</tex>, тогда для каждого ее сына как <tex>l(q)</tex> имеем: .Тогда <tex>\beta_q = \min\left(\fracdfrac{l(q)\beta_p}{l(p)}\beta_p, \tau\right)</tex>, где <tex>\tau</tex> — это угол области <tex>F_p</tex>, определяемой пересечением касательной к в точке <tex>p</tex> к окружности уровня <tex>C_ii</tex> и окружностью уровня <tex>C_{i+1}</tex>.Угол <tex>\tau</tex> необходим для того, чтобы отрезок <tex>pq</tex> не пересек окружность уровня <tex>i</tex>. Радиальное изображение дерева часто используют для представления свободных деревьев<ref name = "Свободное дерево">Под свободными деревьями ''(англ. free trees)'' понимают деревья без выделенного корня. </ref>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]]. <br><br><br>  [[Файл:Hv_tree.jpg|250px|right|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]]

 [[Файл:Hv_tree.jpgДерево_поиска,_наивная_реализация|250px|right|thumb|Пример укладки двоичного дереве в виде hv-изображенияБинарные деревья]]При можно изобразить при помощи '''hv-изображении дерева изображений''' ''(англ. horizontal-vertical drawing)'' (см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства:* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex> : либо по горизонтали справа, либо по вертикали вниз;* не пересекаются минимальные прямоугольники с горизонтальными два прямоугольника, ограничивающие левое и вертикальными вершинами, покрывающие поддеревья правое поддерево вершины <tex>p</tex>, не пересекаются.<br/><br/><br/><br/><br/>   ==См. также==*[[Укладка_графа_на_плоскости|Укладка графа на плоскости]]*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]*[[Гамма-алгоритм|Гамма-алгоритм]] ==Примечания==<references/>  ==Источники информации==* [http://sydney.edu.au/engineering/it/~shhong/comp5048-lec2.pdf Tree Drawing Algorithms and Tree Visualisation Methods (PDF)]