Коды Прюфера - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:06:59Z

rollbackEdits.php mass rollback

194.88.143.66 в 06:22, 1 сентября 2022

2022-09-01T06:22:28Z

Masha: добавлен алгоритм декодирования

2021-01-10T16:39:40Z

добавлен алгоритм декодирования

81.89.176.32: /* Алгоритм построения кодов Прюфера */

2019-10-17T05:42:59Z

‎Алгоритм построения кодов Прюфера

Дмитрий Мурзин: ё

2017-01-30T21:08:53Z

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

2015-12-29T23:43:09Z

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

91.151.202.175 в 23:03, 29 декабря 2015

2015-12-29T23:03:58Z

Lapenok.aleksej в 16:32, 29 ноября 2015

2015-11-29T16:32:33Z

Lapenok.aleksej в 16:26, 29 ноября 2015

2015-11-29T16:26:10Z

Lapenok.aleksej: /* Алгоритм построения кодов Прюфера */

2015-11-29T16:20:18Z

‎Алгоритм построения кодов Прюфера

← Предыдущая		Версия 16:06, 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>n</tex>]] в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:<br>		Кодирование Прюфера переводит [[Количество помеченных деревьев#Помеченное дерево\|помеченные деревья порядка <tex>n</tex>]] в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:<br>

← Предыдущая		Версия 06:22, 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>n</tex>]] в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:<br>		Кодирование Прюфера переводит [[Количество помеченных деревьев#Помеченное дерево\|помеченные деревья порядка <tex>n</tex>]] в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:<br>

@@ Строка 49: / Строка 49: @@
 == Пример построения кода Прюфера ==
 [[Файл: Prufer.png|500px]]
 == Пример декодирования кода Прюфера ==

@@ Строка 6: / Строка 6: @@
 # Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
 <br>
-Полученная последовательность называется '''кодом Прюфера''' ''(англ. Codes Priifer)'' для заданного дерева.
+Полученная последовательность называется '''кодом Прюфера''' ''(англ. Prüfer code)'' для заданного дерева.
 {{Лемма

@@ Строка 14: / Строка 14: @@
 # Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
 # Если вершина не является листом, то у неё на некотором шаге была смежная вершина <tex>-</tex> лист, следовательно номер этой вершины встречается в коде.
-# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален ее сосед, следовательно ее номер не встречается в коде.
+# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален её сосед, следовательно её номер не встречается в коде.
 Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные <tex>-</tex> нет.

@@ Строка 61: / Строка 61: @@
 == Источники информации ==
-# [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
+* [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Остовные деревья ]]
 [[Категория: Свойства остовных деревьев ]]

@@ Строка 28: / Строка 28: @@
 <tex>n = 1</tex> <tex>-</tex> верно.
-<br>
-<u>''Индукционный переход:</u>
+<u>''Индукционный переход:''</u>
-<br>
 Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
 Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> <tex>-</tex> вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.

@@ Строка 24: / Строка 24: @@
 для которого эта последовательность является кодом Прюфера.
 |proof=
-Доказательство проведем по индукции. <br>
+Доказательство проведем по индукции по числу <tex>n</tex><br>
-База. <tex>n = 1</tex> <tex>-</tex> верно.
+<u>''База индукции:''</u>
 <br>
-Переход от <tex>n</tex> к <tex>n + 1</tex>.
+<u>''Индукционный переход:</u>
 <br>
 Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>