Укладка дерева — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(hv-изображения)
м (Радиальная поуровневая укладка)
 
(не показано 10 промежуточных версий 1 участника)
Строка 1: Строка 1:
[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 </tex> <tex dpi=150> \Leftrightarrow</tex><tex> F = 1 </tex>.
+
[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 </tex> <tex dpi=150> \Leftrightarrow</tex><tex> F = 1 </tex>. Значит дерево можно уложить на плоскость и у него будет только одна грань.
 +
Для произвольных графов есть [[Гамма-алгоритм|гамма-алгоритм]], который проверяет произвольный граф на планарность.  
  
 
== Укладка дерева ==
 
== Укладка дерева ==
Строка 17: Строка 18:
  
 
[[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]
 
[[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]
Радиальная поуровневая укладка ''(англ. radial drawing)'' дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
+
'''Радиальная поуровневая укладка''' ''(англ. radial drawing)'' дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
  
 
Вершины глубины <tex>a</tex> располагаются на окружностях с радиусом <tex>r = a</tex>, при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра).  
 
Вершины глубины <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>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(\frac{l(q)}{l(p)}\beta_p, \tau)</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>.
+
Тогда <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>, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин <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>.
+
Радиальное изображение дерева часто используют для представления свободных деревьев<ref name = "Свободное дерево">Под свободными деревьями ''(англ. free trees)'' понимают деревья без выделенного корня.  </ref>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]].  
 
<br>
 
<br>
 
<br>
 
<br>
Строка 33: Строка 34:
 
=== hv-изображения ===
 
=== hv-изображения ===
  
Бинарные деревья<ref name = "Бинарное дерево">Бинарное дерево (двоичное дерево) ''(англ. binary tree)'', то есть такое дерево, у каждой вершины которого не более двух поддеревьев.</ref> можно изобразить при помощи '''hv-изображений''' ''(англ. horizontal-vertical drawing)'' (см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства:
+
[[Дерево_поиска,_наивная_реализация|Бинарные деревья]] можно изобразить при помощи '''hv-изображений''' ''(англ. horizontal-vertical drawing)'' (см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства: сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex>: либо по горизонтали справа, либо по вертикали вниз; два прямоугольника, ограничивающие левое и правое поддерево вершины <tex>p</tex>, не пересекаются.
* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex>: либо по горизонтали справа, либо по вертикали вниз
 
* два прямоугольника, ограничивающие левое и правое поддерево вершины <tex>p</tex>, не пересекаются
 
 
<br/>
 
<br/>
 
<br/>
 
<br/>
Строка 41: Строка 40:
 
<br/>
 
<br/>
 
<br/>
 
<br/>
 +
 +
 +
 +
==См. также==
 +
*[[Укладка_графа_на_плоскости|Укладка графа на плоскости]]
 +
*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]
 +
*[[Гамма-алгоритм|Гамма-алгоритм]]
  
 
==Примечания==
 
==Примечания==

Текущая версия на 17:46, 18 января 2016

Дерево — планарный граф. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По формуле Эйлера: [math]V - E + F = 2, V - (V - 1) + F = 2 [/math] [math] \Leftrightarrow[/math][math] F = 1 [/math]. Значит дерево можно уложить на плоскость и у него будет только одна грань. Для произвольных графов есть гамма-алгоритм, который проверяет произвольный граф на планарность.

Укладка дерева[править]

Рисунок 1. Пример поуровневой укладки дерева.

Существуют несколько способов укладки дерева на плоскости.

Поуровневая укладка[править]

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





Радиальная поуровневая укладка[править]

Рисунок 2. Граф из рисунка 1, но уложенный радиально.

Радиальная поуровневая укладка (англ. radial drawing) дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).

Вершины глубины [math]a[/math] располагаются на окружностях с радиусом [math]r = a[/math], при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра). Определим способ выбора угла этого сектора для некоторого поддерева вершины [math]p[/math] находящейся на уровне [math]i[/math]. Пусть угол сектора для дерева с корнем [math]p[/math] равен [math]\beta_p[/math]. Пусть корень поддерева(непосредственный ребенок [math]p[/math]) — вершина [math]q[/math], обозначим количество вершин в дереве с корнем [math]q[/math] как [math]l(q)[/math]. Тогда [math]\beta_q = \min\left(\dfrac{l(q)}{l(p)}\beta_p, \tau\right)[/math], где [math]\tau[/math] — это угол области [math]F_p[/math], определяемой пересечением касательной в точке [math]p[/math] к окружности уровня [math]i[/math] и окружностью уровня [math]i+1[/math]. Угол [math]\tau[/math] необходим для того, чтобы отрезок [math]pq[/math] не пересек окружность уровня [math]i[/math].

Радиальное изображение дерева часто используют для представления свободных деревьев[1], причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.



Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.

hv-изображения[править]

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





См. также[править]

Примечания[править]

  1. Под свободными деревьями (англ. free trees) понимают деревья без выделенного корня.

Источники информации[править]