Алгоритмы на деревьях - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:11:03Z

rollbackEdits.php mass rollback

185.220.100.252 в 06:14, 1 сентября 2022

2022-09-01T06:14:38Z

VictorMinsky: /* Реализация */

2021-08-25T20:16:51Z

‎Реализация

178.252.127.225: /* Источники информации */

2019-11-03T19:46:50Z

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

Acherepkov: /* Определения */

2017-06-08T13:09:56Z

‎Определения

Acherepkov: /* Алгоритм */

2017-06-08T13:05:29Z

‎Алгоритм

Kano vas: /* Алгоритм для дерева за O(n) */

2015-01-12T12:43:47Z

‎Алгоритм для дерева за O(n)

Kano vas: /* Алгоритм для дерева за O(n) */

2015-01-12T12:23:59Z

‎Алгоритм для дерева за O(n)

Kano vas: /* Алгоритм для дерева за O(n) */

2015-01-12T11:12:09Z

‎Алгоритм для дерева за O(n)

Shersh: /* Реализация */

2015-01-12T10:26:39Z

‎Реализация

← Предыдущая		Версия 16:11, 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 Майкл Наки].
−	\|}
−
	__TOC__		__TOC__

← Предыдущая		Версия 06:14, 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 Майкл Наки].
		+	\|}
		+
	__TOC__		__TOC__

@@ Строка 24: / Строка 24: @@
            '''if''' d[i] > d[u]
                 u = i
-      bfs(g, u)
+      d = bfs(g, u)
       '''for''' i = 0, i < n, i++
             '''if''' d[i] > d[w]

@@ Строка 122: / Строка 122: @@
 * [[wikipedia:Distance_(graph_theory)|Wikipedia {{---}} Distance (graph theory)]]
 * ''Ф. Харари'': Теория графов
-* [http://rain.ifmo.ru/cat/data/theory/graph-location/centers-2006/article.pdf ''А. Клебанов'': Центры графов]
+* [http://rain.ifmo.ru/cat/data/theory/graph-location/centers-2006/article.pdf ''А. Клебанов'': Центры графов(нерабочая ссылка)]
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Основные определения теории графов]]

@@ Строка 67: / Строка 67: @@
 |id = tree
 |definition =
-'''Эксцентриситет вершины <tex>e(v)</tex>''' (англ. ''eccentricity of a vertex'') — <tex>\max\limits_{u, v \in V} dist(v, u)</tex>, где <tex>V</tex> — множество вершин связного графа <tex>G</tex>.
+'''Эксцентриситет вершины <tex>e(v)</tex>''' (англ. ''eccentricity of a vertex'') — <tex>\max\limits_{u\in V} dist(v, u)</tex>, где <tex>V</tex> — множество вершин связного графа <tex>G</tex>.
 }}
 {{Определение

@@ Строка 11: / Строка 11: @@
 === Алгоритм ===
-* Возьмём любую вершину <tex> v \in V </tex> и найдём расстояния до всех других вершин. <tex>d[i] = \min\limits_{u, i \in V} dist(u, i)</tex>
+* Возьмём любую вершину <tex> v \in V </tex> и найдём расстояния до всех других вершин. <tex>d[i] = dist(v, i)</tex>
 * Возьмём вершину <tex> u \in V </tex> такую, что <tex>d[u] \geqslant d[t]</tex> для любого <tex>t</tex>. Снова найдём расстояние от <tex>u</tex> до всех остальных вершин. Самое большое расстояние — диаметр дерева.

← Предыдущая		Версия 12:43, 12 января 2015
Строка 112:		Строка 112:

	Оставшиеся листья являются центром дерева.		Оставшиеся листья являются центром дерева.
		+
		+	Для того, чтобы алгоритм работал за <tex>O(n)</tex>, нужно обрабатывать листья по одному, поддерживая в [[Очередь\|очереди]] два последовательных по глубине слоя.

	== См. также ==		== См. также ==

@@ Строка 106: / Строка 106: @@
 Собственно, алгоритм нахождения центра описан в доказательстве теоремы.
-* Пройдёмся по дереву [[Обход_в_глубину,_цвета_вершин|обходом в глубину]] и поместим в очередь все висячие вершины. Пометим их числом 0.
+* Пройдёмся по дереву [[Обход_в_глубину,_цвета_вершин|обходом в глубину]] и пометим все висячие вершины числом <tex>0</tex>.
-* Пока размер очереди больше 1 и в графе больше 2 вершин, будем удалять из графа вершину, находящуюся в начале очереди. Если вершина является последним ребенком своего родителя, то его необходимо поместить в конец очереди и пометить большим на единицу числом.
+* Обрежем помеченные вершины.
-То, что осталось в очереди, является центром дерева.
+Оставшиеся листья являются центром дерева.
 == См. также ==

@@ Строка 18: / Строка 18: @@
 === Реализация ===
   <span style="color:green">//граф g представлен списком смежности</span>
-  '''int''' diameterTree(list<list<int>> g)
+  '''int''' diameterTree('''list<list<int>>''' g):
       v = u = w = 0
       d = bfs(g, v)