Барицентр дерева - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:17:46Z

rollbackEdits.php mass rollback

185.86.148.90 в 05:36, 1 сентября 2022

2022-09-01T05:36:35Z

Anverk в 11:49, 27 декабря 2017

2017-12-27T11:49:59Z

Anverk: /* Основные свойства */

2017-12-27T11:23:45Z

‎Основные свойства

Anverk в 10:50, 27 декабря 2017

2017-12-27T10:50:59Z

Anverk в 10:50, 27 декабря 2017

2017-12-27T10:50:27Z

Anverk: /* Основные свойства */

2017-12-24T21:30:13Z

‎Основные свойства

Anverk: /* Центр дерева */

2017-12-24T18:15:47Z

‎Центр дерева

Anverk: /* Центр дерева */

2017-12-24T13:37:53Z

‎Центр дерева

Anverk: /* Центр дерева */

2017-12-23T22:35:39Z

‎Центр дерева

← Предыдущая		Версия 16:17, 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 Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|id = tree_barycenter		\|id = tree_barycenter

← Предыдущая		Версия 05:36, 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 Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|id = tree_barycenter		\|id = tree_barycenter

@@ Строка 50: / Строка 50: @@
 * [[Выпуклые функции]]
 * [[Дерево, эквивалентные определения]]
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Основные определения теории графов]]

@@ Строка 16: / Строка 16: @@
 |id = lem2
 |statement = Функция <tex> d(x) </tex> строго выпукла на любом пути в дереве.
-|proof = Признак непрерывной строго выпуклой функции <ref>https://ru.wikipedia.org/wiki/Выпуклая_функция</ref>: <tex> \forall x, y \in \mathbb{R} (x \neq y) </tex>  выполнено <tex> 2f(\displaystyle \frac{x+y}{2}) < f(x) + f (y) </tex>. Будем называть функцию строго выпуклой на множестве натуральных чисел, если предыдущее неравенство выполнено для всех <tex> x, y \in \mathbb{N} </tex>. Доопределим функцию <tex> d(x) </tex> так, чтобы в точке <tex> a + \displaystyle \frac{1}{2} </tex>, где <tex> a \in \mathbb{N} </tex> она принимала значение, строго меньшее <tex> \displaystyle \frac{d(a)+d(a+1)}{2} </tex>. Это нужно сделать, потому что не всегда <tex> \displaystyle \frac{a+b}{2}  \in \mathbb{N}</tex>. Докажем, что такая функция строго выпукла на множестве натуральных чисел.
+|proof = Признак непрерывной строго выпуклой функции <ref>https://ru.wikipedia.org/wiki/Выпуклая_функция</ref>: <tex> \forall x, y \in \mathbb{R} (x \neq y) </tex>  выполнено <tex> 2f(\displaystyle \frac{x+y}{2}) < f(x) + f (y) </tex>. Будем называть функцию строго выпуклой на множестве натуральных чисел, если предыдущее неравенство выполнено для всех <tex> x, y \in \mathbb{N} </tex>. Введём функцию <tex> g_p(x): \mathbb{N} \rightarrow V_G </tex>, которая по номеру вершины в пути <tex> p </tex> находит саму вершину. В дальнейшем <tex> d(a) </tex> будем считать как <tex> d(g_p(a)) </tex> для некоторого рассматриваемого пути <tex> p </tex>. Доопределим функцию <tex> d(x) </tex> так, чтобы в точке <tex> a + \displaystyle \frac{1}{2} </tex>, где <tex> a \in \mathbb{N} </tex> она принимала значение, строго меньшее <tex> \displaystyle \frac{d(a)+d(a+1)}{2} </tex>. Это нужно сделать, потому что не всегда <tex> \displaystyle \frac{a+b}{2}  \in \mathbb{N}</tex>. Докажем, что такая функция строго выпукла на множестве натуральных чисел.
 Есть два случая: когда расстояние между <tex> x, y </tex> четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от <tex> x </tex> до <tex> y </tex>, кроме них есть только вершина <tex> z </tex>. Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, кроме <tex> x, y, z </tex>, тогда их не меньше двух, так как <tex> dist(x, y) </tex> четно. Рассмотрим тогда в этом пути вершины, которые находятся от <tex> z </tex> на расстоянии не больше <tex> 2 </tex> (пусть они идут в порядке: <tex> a b z c d </tex>), и докажем, что неравенство всё ещё сохраняется. <tex> 4d(z) < 2d(b) + 2d(c) < d(a) + d(z) + d(z) + d (b) \Rightarrow 2d(z) < d(a) + d (b)</tex>. Так будем увеличивать расстояние от <tex> z </tex> и придём к вершинам <tex> x, y </tex>, сохраняя инвариант.
 }}

@@ Строка 16: / Строка 16: @@
 |id = lem2
 |statement = Функция <tex> d(x) </tex> строго выпукла на любом пути в дереве.
-|proof = Признак непрерывной строго выпуклой функции <ref>https://ru.wikipedia.org/wiki/Выпуклая_функция</ref>: <tex> \forall x, y \in \mathbb{R} (x \neq y) </tex>  выполнено <tex> 2f(\displaystyle \frac{x+y}{2}) < f(x) + f (y) </tex>. Будем называть функцию выпуклой на множестве натуральных чисел, если предыдущее неравенство выполнено для всех <tex> x, y \in \mathbb{N} </tex>. Доопределим функцию <tex> d(x) </tex> так, чтобы в точке <tex> a + \displaystyle \frac{1}{2} </tex>, где <tex> a \in \mathbb{N} </tex> она принимала значение, строго меньшее <tex> \displaystyle \frac{d(a)+d(a+1)}{2} </tex>. Это нужно сделать, потому что не всегда <tex> \displaystyle \frac{a+b}{2}  \in \mathbb{N}</tex>. Докажем, что такая функция строго выпукла на множестве натуральных чисел.
+|proof = Признак непрерывной строго выпуклой функции <ref>https://ru.wikipedia.org/wiki/Выпуклая_функция</ref>: <tex> \forall x, y \in \mathbb{R} (x \neq y) </tex>  выполнено <tex> 2f(\displaystyle \frac{x+y}{2}) < f(x) + f (y) </tex>. Будем называть функцию строго выпуклой на множестве натуральных чисел, если предыдущее неравенство выполнено для всех <tex> x, y \in \mathbb{N} </tex>. Доопределим функцию <tex> d(x) </tex> так, чтобы в точке <tex> a + \displaystyle \frac{1}{2} </tex>, где <tex> a \in \mathbb{N} </tex> она принимала значение, строго меньшее <tex> \displaystyle \frac{d(a)+d(a+1)}{2} </tex>. Это нужно сделать, потому что не всегда <tex> \displaystyle \frac{a+b}{2}  \in \mathbb{N}</tex>. Докажем, что такая функция строго выпукла на множестве натуральных чисел.
 Есть два случая: когда расстояние между <tex> x, y </tex> четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от <tex> x </tex> до <tex> y </tex>, кроме них есть только вершина <tex> z </tex>. Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, кроме <tex> x, y, z </tex>, тогда их не меньше двух, так как <tex> dist(x, y) </tex> четно. Рассмотрим тогда в этом пути вершины, которые находятся от <tex> z </tex> на расстоянии не больше <tex> 2 </tex> (пусть они идут в порядке: <tex> a b z c d </tex>), и докажем, что неравенство всё ещё сохраняется. <tex> 4d(z) < 2d(b) + 2d(c) < d(a) + d(z) + d(z) + d (b) \Rightarrow 2d(z) < d(a) + d (b)</tex>. Так будем увеличивать расстояние от <tex> z </tex> и придём к вершинам <tex> x, y </tex>, сохраняя инвариант.
 }}

@@ Строка 41: / Строка 41: @@
 }}
-'''Замечание''': доказательство существования такого <tex> n </tex>, чтобы вершина <tex> x </tex> была барицентром можно было проводить и неконструктивно, ведь очевидно, что при больших <tex> n </tex> у барицентра должно быть минимальное расстояние до <tex> n </tex> листьев. И такой вершиной и является <tex> x </tex>.
+'''Замечание''': доказательство существования такого <tex> n </tex>, чтобы вершина <tex> x </tex> была барицентром можно было проводить и менее строго, ведь очевидно, что при больших <tex> n </tex> у барицентра должно быть минимальное расстояние до <tex> n </tex> листьев. И такой вершиной и является <tex> x </tex>.
 == Примечания ==

@@ Строка 39: / Строка 39: @@
 |proof= Рассмотрим дерево, построенное следующим образом: к вершине дерева <tex> x </tex> подвесим <tex> n </tex> свободных вершин (в дереве они станут листьями) и бамбук, расстояние в котором от листа до <tex> x </tex> назовём числом <tex> l </tex>. Докажем, что существуют такие <tex> n, l </tex>, что расстояние между центром и барицентром не меньше <tex> k </tex>.
 Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные <tex> l. </tex> Назовём лист бамбука вершиной <tex> a </tex>, а центр дерева <tex>- \  c </tex>. Тогда <tex> dist(a, c) = \displaystyle \frac{l+1}{2} </tex>. Теперь будем искать, какое <tex> n </tex> стоит выбрать, чтобы барицентром оказалась вершина <tex> x </tex>. Найдём <tex> d(x) </tex>: <tex> d(x) = n + 1 + \dots + l = n + \displaystyle \frac{(l+1)l}{2} </tex>. Рассмотрим вершину <tex> v \neq x </tex>. <tex> d(v) > 2(n-1) </tex>, так как все вершины, кроме <tex> x </tex> удалены хотя бы на расстояние <tex> 2 </tex> от <tex> n-1 </tex> вершины. В таком случае, <tex> d(x) < d(v) \Leftarrow n > \displaystyle \frac{(l+1)l}{2} + 2 </tex>. Мы получили, что <tex> dist(c, x) = \displaystyle \frac{l-1}{2} </tex>, и <tex> x </tex> является барицентром. Найдём такие <tex> l ,</tex> что <tex> \displaystyle \frac{l-1}{2} \geqslant k</tex>. Для этого можно взять любое <tex> l \geqslant 2k + 1 </tex>. Таким образом, искомые <tex> n, l </tex> существуют.
 '''Замечание''': доказательство существования такого <tex> n </tex>, чтобы вершина <tex> x </tex> была барицентром можно было проводить и неконструктивно, ведь очевидно, что при больших <tex> n </tex> у барицентра должно быть минимальное расстояние до <tex> n </tex> листьев. И такой вершиной и является <tex> x </tex>.
 == Примечания ==