Изменения
Нет описания правки
[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера ]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 \Leftrightarrow F = 1 </tex>.
== Укладка дерева ==
Выбор угла <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>.
Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин<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>.
[[Файл:Hv_tree.jpg|250px|left|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]]
=== hv-изображения ===
<br/>
==Примечания==<brreferences/>
==Ссылки==
* [http://sydney.edu.au/engineering/it/~shhong/comp5048-lec2.pdf Tree Drawing Algorithms and Tree Visualisation Methods (PDF)]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
