Барицентр дерева — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Центр дерева)
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 2 участников)
Строка 16: Строка 16:
 
|id = lem2
 
|id = lem2
 
|statement = Функция <tex> d(x) </tex> строго выпукла на любом пути в дереве.
 
|statement = Функция <tex> d(x) </tex> строго выпукла на любом пути в дереве.
|proof = Признак непрерывной строго выпуклой функции <ref>https://ru.wikipedia.org/wiki/Выпуклая_функция</ref>: <tex> 2f(\displaystyle \frac{x+y}{2}) < f(x) + f (y) </tex>. Функция <tex> d(x) </tex> не является непрерывной при <tex> x \in \mathbb{R} </tex>, но её можно доопределить так, чтобы на интервале <tex> (a, b) </tex>, где <tex> a, b \in \mathbb {N} </tex> она соединяла значения <tex> d(a) </tex> и <tex> d(b) </tex> параболой (или любой другой выпуклой функцией). Это можно сделать, потому что для функции на пути в дереве рассматриваются только натуральные аргументы. Для доказательства выпуклости нам интересна только точка параболы, абсцисса которой равна <tex> \displaystyle \frac{a+b}{2} </tex>. В ней функция будет принимать значение, строго меньшее <tex> \displaystyle \frac{d(a)+d(b)}{2} </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>, сохраняя инвариант.  
 
Есть два случая: когда расстояние между <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>, сохраняя инвариант.  
 
}}
 
}}
Строка 39: Строка 39:
 
|proof= Рассмотрим дерево, построенное следующим образом: к вершине дерева <tex> x </tex> подвесим <tex> n </tex> свободных вершин (в дереве они станут листьями) и бамбук, расстояние в котором от листа до <tex> x </tex> назовём числом <tex> l </tex>. Докажем, что существуют такие <tex> n, l </tex>, что расстояние между центром и барицентром не меньше <tex> k </tex>.
 
|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> 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>.
+
'''Замечание''': доказательство существования такого <tex> n </tex>, чтобы вершина <tex> x </tex> была барицентром можно было проводить и менее строго, ведь очевидно, что при больших <tex> n </tex> у барицентра должно быть минимальное расстояние до <tex> n </tex> листьев. И такой вершиной и является <tex> x </tex>.
}}
 
  
 
== Примечания ==
 
== Примечания ==
Строка 50: Строка 50:
 
* [[Выпуклые функции]]
 
* [[Выпуклые функции]]
 
* [[Дерево, эквивалентные определения]]
 
* [[Дерево, эквивалентные определения]]
 +
 +
== Источники информации ==
 +
 +
* ''Melnikov O.''. «Exercises in Graph Theory» — «Springer», 2013 г. — 47-48 стр. — ISBN 978-94-017-1514-0
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Текущая версия на 19:17, 4 сентября 2022

Определение:
Барицентром дерева (англ. tree barycenter) называется вершина [math] x [/math], у которой величина [math]d(x) = \sum\limits_v dist(x, v) [/math] минимальна, где [math] dist(x, v) -[/math] расстояние между вершинами [math] x [/math] и [math] v [/math].


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

Лемма:
Пусть существуют вершины [math] y, z -[/math] соседи вершины [math] x [/math]. Тогда [math] 2d(x) \lt d(y) + d(z) [/math].
Доказательство:
[math]\triangleright[/math]

Подвесим дерево за вершину [math] x [/math]. Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: [math] Y, Z \ - [/math] поддеревья с корнями в вершинах [math] y, z [/math] соответственно и [math] X = V_G \setminus (Y \cup Z) [/math]. Заметим, что все эти множества не пустые, так как содержат вершины [math] y, z, x [/math] соответственно. Найдём [math] d(x) [/math].

Простой путь до вершины [math] t \in Y [/math] из [math] x [/math] всегда единственный и представим следующим образом: [math] x \rightarrow y \rightsquigarrow t[/math]. Значит, все вершины из множества [math] Y [/math] находятся от [math] x [/math] на одно ребро дальше, чем от [math] y [/math]. Аналогично все вершины из множеств [math] Z, X [/math] ближе на одно ребро к [math] x [/math], чем к [math] y [/math]. Тогда [math] d(x) = d(y) + |Y| - |Z| - |X| [/math]. Аналогично [math] d(x) = d(z) + |Z| - |Y| - |X| [/math]. Сложим эти уравнения и получим: [math] 2d(x) = d(y) + d(z) - 2|X| [/math]. При этом [math] |X| \gt 0 [/math]. Таким образом, [math] 2d(x) \lt d(y) + d(z) [/math].
[math]\triangleleft[/math]
Лемма:
Функция [math] d(x) [/math] строго выпукла на любом пути в дереве.
Доказательство:
[math]\triangleright[/math]

Признак непрерывной строго выпуклой функции [1]: [math] \forall x, y \in \mathbb{R} (x \neq y) [/math] выполнено [math] 2f(\displaystyle \frac{x+y}{2}) \lt f(x) + f (y) [/math]. Будем называть функцию строго выпуклой на множестве натуральных чисел, если предыдущее неравенство выполнено для всех [math] x, y \in \mathbb{N} [/math]. Введём функцию [math] g_p(x): \mathbb{N} \rightarrow V_G [/math], которая по номеру вершины в пути [math] p [/math] находит саму вершину. В дальнейшем [math] d(a) [/math] будем считать как [math] d(g_p(a)) [/math] для некоторого рассматриваемого пути [math] p [/math]. Доопределим функцию [math] d(x) [/math] так, чтобы в точке [math] a + \displaystyle \frac{1}{2} [/math], где [math] a \in \mathbb{N} [/math] она принимала значение, строго меньшее [math] \displaystyle \frac{d(a)+d(a+1)}{2} [/math]. Это нужно сделать, потому что не всегда [math] \displaystyle \frac{a+b}{2} \in \mathbb{N}[/math]. Докажем, что такая функция строго выпукла на множестве натуральных чисел.

Есть два случая: когда расстояние между [math] x, y [/math] четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от [math] x [/math] до [math] y [/math], кроме них есть только вершина [math] z [/math]. Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, кроме [math] x, y, z [/math], тогда их не меньше двух, так как [math] dist(x, y) [/math] четно. Рассмотрим тогда в этом пути вершины, которые находятся от [math] z [/math] на расстоянии не больше [math] 2 [/math] (пусть они идут в порядке: [math] a b z c d [/math]), и докажем, что неравенство всё ещё сохраняется. [math] 4d(z) \lt 2d(b) + 2d(c) \lt d(a) + d(z) + d(z) + d (b) \Rightarrow 2d(z) \lt d(a) + d (b)[/math]. Так будем увеличивать расстояние от [math] z [/math] и придём к вершинам [math] x, y [/math], сохраняя инвариант.
[math]\triangleleft[/math]
Теорема (о числе барицентров):
В дереве не более [math] 2 [/math] барицентов
Доказательство:
[math]\triangleright[/math]
Пусть в дереве есть хотя бы [math] 3 [/math] барицентра: [math] a, b, c [/math]. Тогда рассмотрим путь, начинающийся в [math] a [/math] и заканчивающийся в [math] b [/math]. Так как [math] d(a) = d(b) = d_{min} [/math], и функция [math] d(x) [/math] строго выпукла, вершины [math] a, b [/math] являются соседями. В противном случае, или в этом пути есть вершина [math] v: d(v) \lt d_{min} [/math], или для всех вершин [math] u [/math] в пути [math] d(u) = d_{min} [/math]. Первое предположение противоречит тому, что [math] a, b \ - [/math] барицентры, а второе [math] - [/math] тому, что функция [math] d(x) [/math] строго выпукла. Таким образом, вершины [math] a, b [/math] являются соседями. Аналогично доказывается, что вершины [math] b, c [/math] и [math] a, c \ -[/math] соседи. Но в таком случае в дереве образовался цикл, что противоречит определению дерева. Таким образом, более [math] 2 [/math] барицентров в дереве быть не может.
[math]\triangleleft[/math]

Центр дерева

Определение:
Центром дерева (англ. Tree center) называется вершина [math] x [/math], для которой величина [math] \max\limits_v dist(x, v) [/math] минимальна.


Теорема:
Для любого числа [math] k [/math] существует дерево, в котором расстояние между центром и барицентром дерева не меньше [math] k [/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим дерево, построенное следующим образом: к вершине дерева [math] x [/math] подвесим [math] n [/math] свободных вершин (в дереве они станут листьями) и бамбук, расстояние в котором от листа до [math] x [/math] назовём числом [math] l [/math]. Докажем, что существуют такие [math] n, l [/math], что расстояние между центром и барицентром не меньше [math] k [/math].

Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные [math] l. [/math] Назовём лист бамбука вершиной [math] a [/math], а центр дерева [math]- \ c [/math]. Тогда [math] dist(a, c) = \displaystyle \frac{l+1}{2} [/math]. Теперь будем искать, какое [math] n [/math] стоит выбрать, чтобы барицентром оказалась вершина [math] x [/math]. Найдём [math] d(x) [/math]: [math] d(x) = n + 1 + \dots + l = n + \displaystyle \frac{(l+1)l}{2} [/math]. Рассмотрим вершину [math] v \neq x [/math]. [math] d(v) \gt 2(n-1) [/math], так как все вершины, кроме [math] x [/math] удалены хотя бы на расстояние [math] 2 [/math] от [math] n-1 [/math] вершины. В таком случае, [math] d(x) \lt d(v) \Leftarrow n \gt \displaystyle \frac{(l+1)l}{2} + 2 [/math]. Мы получили, что [math] dist(c, x) = \displaystyle \frac{l-1}{2} [/math], и [math] x [/math] является барицентром. Найдём такие [math] l ,[/math] что [math] \displaystyle \frac{l-1}{2} \geqslant k[/math]. Для этого можно взять любое [math] l \geqslant 2k + 1 [/math]. Таким образом, искомые [math] n, l [/math] существуют.
[math]\triangleleft[/math]

Замечание: доказательство существования такого [math] n [/math], чтобы вершина [math] x [/math] была барицентром можно было проводить и менее строго, ведь очевидно, что при больших [math] n [/math] у барицентра должно быть минимальное расстояние до [math] n [/math] листьев. И такой вершиной и является [math] x [/math].

Примечания

См. также

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

  • Melnikov O.. «Exercises in Graph Theory» — «Springer», 2013 г. — 47-48 стр. — ISBN 978-94-017-1514-0