5
правок
Изменения
Новая страница: «Дерево — планарный граф. Согласно [[Формула Эйлера|с…»
[[Дерево, эквивалентные определения |Дерево]] — планарный граф. Согласно [[Формула Эйлера|следствию из формулы Эйлера]]: для дерева с <tex>N</tex> вершинами <tex>N - 1 \le 3 \cdot N - 6</tex>.
== Укладка дерева ==
Существуют несколько способов укладки дерева на плоскости.
=== Поуровневая укладка ===
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за полиномиальное время, позволяющая получить оптимальное по ширине плоское дерево.
=== Радиальная поуровневая укладка ===
Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
== Укладка дерева ==
Существуют несколько способов укладки дерева на плоскости.
=== Поуровневая укладка ===
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за полиномиальное время, позволяющая получить оптимальное по ширине плоское дерево.
=== Радиальная поуровневая укладка ===
Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
