Укладка дерева - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:33:15Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:23, 1 сентября 2022

2022-09-01T04:23:24Z

Shersh: /* Радиальная поуровневая укладка */

2016-01-18T14:46:54Z

‎Радиальная поуровневая укладка

5.18.163.38: /* Радиальная поуровневая укладка */

2016-01-18T14:41:13Z

‎Радиальная поуровневая укладка

5.18.163.38: /* Радиальная поуровневая укладка */

2016-01-18T14:30:14Z

‎Радиальная поуровневая укладка

5.18.163.38 в 14:26, 18 января 2016

2016-01-18T14:26:53Z

5.18.163.38 в 13:52, 18 января 2016

2016-01-18T13:52:43Z

5.18.163.38: /* hv-изображения */

2016-01-18T13:50:15Z

‎hv-изображения

5.18.163.38 в 16:43, 15 января 2016

2016-01-15T16:43:40Z

5.18.163.38: /* См. так же */

2016-01-13T14:01:14Z

‎См. так же

← Предыдущая		Версия 16:33, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	[[Дерево, эквивалентные определения \|Дерево]] — планарный [[Основные_определения_теории_графов\|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера\|формуле Эйлера]]: <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>. Значит дерево можно уложить на плоскость и у него будет только одна грань.
	Для произвольных графов есть [[Гамма-алгоритм\|гамма-алгоритм]], который проверяет произвольный граф на планарность.		Для произвольных графов есть [[Гамма-алгоритм\|гамма-алгоритм]], который проверяет произвольный граф на планарность.

← Предыдущая		Версия 04:23, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	[[Дерево, эквивалентные определения \|Дерево]] — планарный [[Основные_определения_теории_графов\|граф]]. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По [[Формула Эйлера\|формуле Эйлера]]: <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>. Значит дерево можно уложить на плоскость и у него будет только одна грань.
	Для произвольных графов есть [[Гамма-алгоритм\|гамма-алгоритм]], который проверяет произвольный граф на планарность.		Для произвольных графов есть [[Гамма-алгоритм\|гамма-алгоритм]], который проверяет произвольный граф на планарность.

@@ Строка 18: / Строка 18: @@
 [[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]
-Радиальная поуровневая укладка ''(англ. radial drawing)'' дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
+'''Радиальная поуровневая укладка''' ''(англ. radial drawing)'' дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
 Вершины глубины <tex>a</tex> располагаются на окружностях с радиусом <tex>r = a</tex>, при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра).

@@ Строка 22: / Строка 22: @@
 Вершины глубины <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>(</tex><tex>\dfrac{l(q)}{l(p)}\beta_p, \tau</tex><tex dpi=150>)</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>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]].

@@ Строка 22: / Строка 22: @@
 Вершины глубины <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(\dfrac{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</tex><tex dpi=150>(</tex><tex>\dfrac{l(q)}{l(p)}\beta_p, \tau</tex><tex dpi=150>)</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>, причем в качестве вершины, размещаемой в центре, берется одна из его [[Алгоритмы_на_деревьях|центральных вершин]].

@@ Строка 41: / Строка 41: @@
 <br/>
-==Примечания==
 ==См. также==
@@ Строка 48: / Строка 47: @@
 *[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]
 *[[Гамма-алгоритм|Гамма-алгоритм]]
 ==Источники информации==

@@ Строка 34: / Строка 34: @@
 === hv-изображения ===
-[[Дерево_поиска,_наивная_реализация|Бинарные деревья]] можно изобразить при помощи '''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>, не пересекаются.
 <br/>
 <br/>

@@ Строка 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>. Значит дерево можно уложить на плоскость и у него будет только одна грань.
 == Укладка дерева ==
@@ Строка 48: / Строка 49: @@
 *[[Укладка_графа_на_плоскости|Укладка графа на плоскости]]
 *[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]
 ==Источники информации==