1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Файл: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>\beta_q = \min</tex><tex dpi=150>\left(</tex><tex>\dfrac{l(q)}{l(p)}\beta_p, \tau</tex><tex dpi=150>\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>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]].
