http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=Exprmntr 2026-04-05T20:53:45Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BA%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=4442 2010-10-27T06:12:36Z

<p>Exprmntr: /* hv-изображения */</p> <hr /> <div>[[Дерево, эквивалентные определения |Дерево]] — планарный граф. Согласно [[Формула Эйлера|следствию из формулы Эйлера]]: для дерева с &lt;tex&gt;N&lt;/tex&gt; вершинами &lt;tex&gt;N - 1 \le 3 \cdot N - 6&lt;/tex&gt;.<br /> <br /> == Укладка дерева ==<br /> Существуют несколько способов укладки дерева на плоскости.<br /> === Поуровневая укладка ===<br /> Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины &lt;tex&gt;a&lt;/tex&gt; имеют координату &lt;tex&gt;y = – a&lt;/tex&gt;, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера &lt;tex&gt;O(N^2)&lt;/tex&gt; (где &lt;tex&gt;N&lt;/tex&gt; — число вершин дерева). <br /> === Радиальная поуровневая укладка ===<br /> Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты. <br /> <br /> Выбор угла &lt;tex&gt;\beta_p&lt;/tex&gt; секторного сегмента для поддерева с корнем &lt;tex&gt;p&lt;/tex&gt; и количеством вершин &lt;tex&gt;l(p)&lt;/tex&gt; определяется следующим образом: пусть вершина &lt;tex&gt;p&lt;/tex&gt; лежит на уровне &lt;tex&gt;C_i&lt;/tex&gt;, тогда для каждого ее сына &lt;tex&gt;q&lt;/tex&gt; имеем: &lt;tex&gt;\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)&lt;/tex&gt;, где &lt;tex&gt;\tau&lt;/tex&gt; — это угол области &lt;tex&gt;F_p&lt;/tex&gt;, определяемой пересечением касательной к точке &lt;tex&gt;p&lt;/tex&gt; уровня &lt;tex&gt;C_i&lt;/tex&gt; и окружностью уровня &lt;tex&gt;C_{i+1}&lt;/tex&gt;.<br /> <br /> Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.<br /> === hv-изображения ===<br /> При hv-изображении дерева для каждой вершины &lt;tex&gt;p&lt;/tex&gt; выполняются следующие свойства:<br /> * сын вершины &lt;tex&gt;p&lt;/tex&gt; ставится в ряд за &lt;tex&gt;p&lt;/tex&gt; либо по горизонтали справа, либо по вертикали вниз;<br /> * не пересекаются минимальные прямоугольники с горизонтальными и вертикальными вершинами, покрывающие поддеревья вершины &lt;tex&gt;p&lt;/tex&gt;. <br /> [[Категория: Алгоритмы и структуры данных]]<br /> [[Категория: Укладки графов ]]</div>

Exprmntr http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BA%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=4441 2010-10-27T06:12:04Z

<p>Exprmntr: /* hv-изображения */</p> <hr /> <div>[[Дерево, эквивалентные определения |Дерево]] — планарный граф. Согласно [[Формула Эйлера|следствию из формулы Эйлера]]: для дерева с &lt;tex&gt;N&lt;/tex&gt; вершинами &lt;tex&gt;N - 1 \le 3 \cdot N - 6&lt;/tex&gt;.<br /> <br /> == Укладка дерева ==<br /> Существуют несколько способов укладки дерева на плоскости.<br /> === Поуровневая укладка ===<br /> Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины &lt;tex&gt;a&lt;/tex&gt; имеют координату &lt;tex&gt;y = – a&lt;/tex&gt;, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера &lt;tex&gt;O(N^2)&lt;/tex&gt; (где &lt;tex&gt;N&lt;/tex&gt; — число вершин дерева). <br /> === Радиальная поуровневая укладка ===<br /> Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты. <br /> <br /> Выбор угла &lt;tex&gt;\beta_p&lt;/tex&gt; секторного сегмента для поддерева с корнем &lt;tex&gt;p&lt;/tex&gt; и количеством вершин &lt;tex&gt;l(p)&lt;/tex&gt; определяется следующим образом: пусть вершина &lt;tex&gt;p&lt;/tex&gt; лежит на уровне &lt;tex&gt;C_i&lt;/tex&gt;, тогда для каждого ее сына &lt;tex&gt;q&lt;/tex&gt; имеем: &lt;tex&gt;\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)&lt;/tex&gt;, где &lt;tex&gt;\tau&lt;/tex&gt; — это угол области &lt;tex&gt;F_p&lt;/tex&gt;, определяемой пересечением касательной к точке &lt;tex&gt;p&lt;/tex&gt; уровня &lt;tex&gt;C_i&lt;/tex&gt; и окружностью уровня &lt;tex&gt;C_{i+1}&lt;/tex&gt;.<br /> <br /> Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.<br /> === hv-изображения ===<br /> Для hv-изображения дерева для каждой вершины &lt;tex&gt;p&lt;/tex&gt; выполняются следующие свойства:<br /> * сын вершины &lt;tex&gt;p&lt;/tex&gt; ставится в ряд за &lt;tex&gt;p&lt;/tex&gt; либо по горизонтали справа, либо по вертикали вниз;<br /> * не пересекаются минимальные прямоугольники с горизонтальными и вертикальными вершинами, покрывающие поддеревья вершины &lt;tex&gt;p&lt;/tex&gt;. <br /> [[Категория: Алгоритмы и структуры данных]]<br /> [[Категория: Укладки графов ]]</div>

Exprmntr http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BA%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=4440 2010-10-27T06:06:12Z

<p>Exprmntr: </p> <hr /> <div>[[Дерево, эквивалентные определения |Дерево]] — планарный граф. Согласно [[Формула Эйлера|следствию из формулы Эйлера]]: для дерева с &lt;tex&gt;N&lt;/tex&gt; вершинами &lt;tex&gt;N - 1 \le 3 \cdot N - 6&lt;/tex&gt;.<br /> <br /> == Укладка дерева ==<br /> Существуют несколько способов укладки дерева на плоскости.<br /> === Поуровневая укладка ===<br /> Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины &lt;tex&gt;a&lt;/tex&gt; имеют координату &lt;tex&gt;y = – a&lt;/tex&gt;, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера &lt;tex&gt;O(N^2)&lt;/tex&gt; (где &lt;tex&gt;N&lt;/tex&gt; — число вершин дерева). <br /> === Радиальная поуровневая укладка ===<br /> Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты. <br /> <br /> Выбор угла &lt;tex&gt;\beta_p&lt;/tex&gt; секторного сегмента для поддерева с корнем &lt;tex&gt;p&lt;/tex&gt; и количеством вершин &lt;tex&gt;l(p)&lt;/tex&gt; определяется следующим образом: пусть вершина &lt;tex&gt;p&lt;/tex&gt; лежит на уровне &lt;tex&gt;C_i&lt;/tex&gt;, тогда для каждого ее сына &lt;tex&gt;q&lt;/tex&gt; имеем: &lt;tex&gt;\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)&lt;/tex&gt;, где &lt;tex&gt;\tau&lt;/tex&gt; — это угол области &lt;tex&gt;F_p&lt;/tex&gt;, определяемой пересечением касательной к точке &lt;tex&gt;p&lt;/tex&gt; уровня &lt;tex&gt;C_i&lt;/tex&gt; и окружностью уровня &lt;tex&gt;C_{i+1}&lt;/tex&gt;.<br /> <br /> Радиальное изображение дерева часто используют для представления свободных деревьев, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин.<br /> === hv-изображения ===<br /> [[Категория: Алгоритмы и структуры данных]]<br /> [[Категория: Укладки графов ]]</div>

Exprmntr http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BA%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=4306 2010-10-21T17:39:12Z

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

Exprmntr http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BA%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=4303 2010-10-21T17:33:40Z

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

Exprmntr