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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Укладка дерева)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 4 участников)
Строка 1: Строка 1:
[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 \Leftrightarrow F = 1 </tex>.
+
[[Дерево, эквивалентные определения |Дерево]] — планарный [[Основные_определения_теории_графов|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера|формуле Эйлера]]: <tex>V - E + F = 2, V - (V - 1) + F = 2 </tex> <tex dpi=150> \Leftrightarrow</tex><tex> F = 1 </tex>. Значит дерево можно уложить на плоскость и у него будет только одна грань.
 +
Для произвольных графов есть [[Гамма-алгоритм|гамма-алгоритм]], который проверяет произвольный граф на планарность.  
  
 
== Укладка дерева ==
 
== Укладка дерева ==
  
 +
[[Файл:Layer-graph.jpg|250px|right|thumb|Рисунок 1. Пример поуровневой укладки дерева.]]
 
Существуют несколько способов укладки дерева на плоскости.
 
Существуют несколько способов укладки дерева на плоскости.
  
[[Файл:Layer-graph.jpg|250px|left|thumb|Рисунок 1. Пример поуровневой укладки дерева.]]
 
 
=== Поуровневая укладка ===
 
=== Поуровневая укладка ===
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения (''layered drawing''), при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми (см. рисунок 1). Возможна реализация за линейное время, позволяющая получить оптимальное по ширине [[Укладка графа на плоскости|плоское дерево]] в области размера <tex>O(N^2)</tex> (где <tex>N</tex> — число вершин дерева).  
+
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его '''поуровневого расположения''' ''(англ. layered drawing)'', при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми (см. рисунок 1). Возможна реализация за линейное время, позволяющая получить оптимальное по ширине [[Укладка графа на плоскости|плоское дерево]] в области размера <tex>O(N^2)</tex> (где <tex>N</tex> — число вершин дерева).  
  
 
<br>
 
<br>
[[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]
+
<br>
 +
<br>
 +
<br>
 +
 
 
=== Радиальная поуровневая укладка ===
 
=== Радиальная поуровневая укладка ===
  
Радиальная поуровневая укладка(''radial drawing'') дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
+
[[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]
 +
'''Радиальная поуровневая укладка''' ''(англ. 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>\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>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]].  
[[Файл:Hv_tree.jpg|250px|left|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]]
+
<br>
 
<br>
 
<br>
 +
<br>
 +
 +
 +
[[Файл:Hv_tree.jpg|250px|right|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]]
 +
 
=== hv-изображения ===
 
=== hv-изображения ===
Бинарные деревья<ref name = "Бинарное дерево">Бинарное дерево (двоичное дерево, ''binary tree''), то есть такое дерево, у каждой вершины которого не более двух поддеревьев.</ref> можно изобразить при помощи hv-изображений (''horizontal-vertical drawing'', см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства:
+
 
* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex> либо по горизонтали справа, либо по вертикали вниз
+
[[Дерево_поиска,_наивная_реализация|Бинарные деревья]] можно изобразить при помощи '''hv-изображений''' ''(англ. horizontal-vertical drawing)'' (см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства: сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex>: либо по горизонтали справа, либо по вертикали вниз; два прямоугольника, ограничивающие левое и правое поддерево вершины <tex>p</tex>, не пересекаются.
* два прямоугольника, ограничивающие левое и правое поддерево вершины <tex>p</tex> не пересекаются
 
 
<br/>
 
<br/>
 
<br/>
 
<br/>
Строка 31: Строка 40:
 
<br/>
 
<br/>
 
<br/>
 
<br/>
 +
 +
 +
 +
==См. также==
 +
*[[Укладка_графа_на_плоскости|Укладка графа на плоскости]]
 +
*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]
 +
*[[Гамма-алгоритм|Гамма-алгоритм]]
  
 
==Примечания==
 
==Примечания==
 
<references/>  
 
<references/>  
  
==Ссылки==
+
==Источники информации==
 
* [http://sydney.edu.au/engineering/it/~shhong/comp5048-lec2.pdf Tree Drawing Algorithms and Tree Visualisation Methods (PDF)]
 
* [http://sydney.edu.au/engineering/it/~shhong/comp5048-lec2.pdf Tree Drawing Algorithms and Tree Visualisation Methods (PDF)]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов ]]
 
[[Категория: Укладки графов ]]

Текущая версия на 19:33, 4 сентября 2022

Дерево — планарный граф. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По формуле Эйлера: [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) понимают деревья без выделенного корня.

Источники информации