3622
правки
Изменения
м
==Примечания==<references/>
→Радиальная поуровневая укладка
[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 </tex> <tex dpi=150> \Leftrightarrow</tex><tex> F = 1 </tex>. Значит дерево можно уложить на плоскость и у него будет только одна грань.Для произвольных графов есть [[Гамма-алгоритм|гамма-алгоритм]], который проверяет произвольный граф на планарность.
== Укладка дерева ==
[[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]
'''Радиальная поуровневая укладка ''' ''(англ. 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 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>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]].
=== hv-изображения ===
[[Дерево_поиска,_наивная_реализация|Бинарные деревья]] можно изобразить при помощи '''hv-изображений''' ''(англ. horizontal-vertical drawing)'' (см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства:* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex>: либо по горизонтали справа, либо по вертикали вниз* ; два прямоугольника, ограничивающие левое и правое поддерево вершины <tex>p</tex>, не пересекаются.
<br/>
<br/>
<br/>
==См. также==
*[[Укладка_графа_на_плоскости|Укладка графа на плоскости]]
*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]
*[[Гамма-алгоритм|Гамма-алгоритм]]
==Примечания==
<references/>
==Источники информации==
