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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id = tree_barycenter
 
|id = tree_barycenter
|definition = '''Барицентром дерева''' (англ. ''Tree barycenter'') называется вершина <tex> x </tex>, у которой величина <tex>d(x) = \sum\limits_v dist(x, v) </tex> минимальна, где <tex> dist(x, v) -</tex> расстояние между вершинами <tex> x </tex> и <tex> v </tex> в рёбрах.
+
|definition = '''Барицентром дерева''' (англ. ''tree barycenter'') называется вершина <tex> x </tex>, у которой величина <tex>d(x) = \sum\limits_v dist(x, v) </tex> минимальна, где <tex> dist(x, v) -</tex> расстояние между вершинами <tex> x </tex> и <tex> v </tex>.
 
}}
 
}}
  
Строка 9: Строка 9:
 
|id = lem1
 
|id = lem1
 
|statement = Пусть существуют вершины <tex> y, z -</tex> соседи вершины <tex> x </tex>. Тогда <tex> 2d(x) < d(y) + d(z) </tex>.
 
|statement = Пусть существуют вершины <tex> y, z -</tex> соседи вершины <tex> x </tex>. Тогда <tex> 2d(x) < d(y) + d(z) </tex>.
|proof = Подвесим дерево за вершину <tex> x </tex>. Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: <tex> Y, Z </tex> (поддеревья с корнем в вершинах <tex> y, z </tex> соответственно) и <tex> X - </tex> остальных вершин (заметим, что все эти множества не пустые, так как содержат вершины <tex> y, z, x </tex> соответственно). Найдём <tex> d(x) </tex>:
+
|proof = Подвесим дерево за вершину <tex> x </tex>. Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: <tex> Y, Z \ - </tex> поддеревья с корнями в вершинах <tex> y, z </tex> соответственно и <tex> X = V_G \setminus (Y \cup Z) </tex>. Заметим, что все эти множества не пустые, так как содержат вершины <tex> y, z, x </tex> соответственно. Найдём <tex> d(x) </tex>.
<tex> d(x) = d(y) + |Y| - |Z| - |X| </tex>. Это верно, так как все вершины из множества <tex> Y </tex> находятся от <tex> x </tex> на одно ребро дальше, чем от <tex> y </tex>, а вершины из множеств <tex> Z, X </tex> наоборот. Аналогично <tex> d(x) = d(z) + |Z| - |Y| - |X| </tex>. Сложим эти уравнения и получим: <tex> 2d(x) = d(y) + d(z) - 2|X| </tex>. При этом <tex> |X| > 0 </tex>. Таким образом, <tex> 2d(x) < d(y) + d(z) </tex>.
+
Простой путь до вершины <tex> t \in Y </tex> из <tex> x </tex> всегда единственный и представим следующим образом: <tex> x \rightarrow y \rightsquigarrow t</tex>. Значит, все вершины из множества <tex> Y </tex> находятся от <tex> x </tex> на одно ребро дальше, чем от <tex> y </tex>. Аналогично все вершины из множеств <tex> Z, X </tex> ближе на одно ребро к <tex> x </tex>, чем к <tex> y </tex>. Тогда <tex> d(x) = d(y) + |Y| - |Z| - |X| </tex>. Аналогично <tex> d(x) = d(z) + |Z| - |Y| - |X| </tex>. Сложим эти уравнения и получим: <tex> 2d(x) = d(y) + d(z) - 2|X| </tex>. При этом <tex> |X| > 0 </tex>. Таким образом, <tex> 2d(x) < d(y) + d(z) </tex>.
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
 
|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> (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> 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>, сохраняя инвариант.  
 
}}
 
}}
  
Строка 37: Строка 37:
 
|id = theor2
 
|id = theor2
 
|statement= Для любого числа <tex> k </tex> существует дерево, в котором расстояние между центром и барицентром дерева не меньше <tex> k </tex>
 
|statement= Для любого числа <tex> k </tex> существует дерево, в котором расстояние между центром и барицентром дерева не меньше <tex> k </tex>
|proof= Рассмотрим дерево, построенное следующим образом: к вершине дерева <tex> x </tex> проводим <tex> n + 1 </tex> ребро, <tex> n </tex> из которых проведено в листья дерева, а одно ребро продолжим достраивать как бамбук, расстояние в котором от листа до <tex> x </tex> назовём числом <tex> l </tex>. Докажем, что существуют такие <tex> m, 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> a </tex>, а центр дерева <tex>- \  c </tex>. Тогда <tex> dist(a, c) = \displaystyle \frac{l+1}{2} </tex>. Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные <tex> l. </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) \Leftrightarrow 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> m, 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>.
'''Метод барицентров''' (англ. ''barycenter heuristic'') используется в одном из этапов визуализации ориентированных ациклических графов. Сначала в графе находятся множества вершин <tex> - </tex> '''уровни''' (англ. ''layers''). Уровни ищутся так, чтобы рёбра между вершинами разных уровней шли в неубывающем или невозрастающем направлении по вертикали или горизонтали. После того, как найдены уровни, нужно уменьшить число пересечений между рёбрами. Одна из используемых эвристик и есть <tex> - </tex> метод барицентров. Его суть заключается в том, чтобы координаты вершины определялись как среднее арифметическое координат смежных вершин предыдущего уровня. Важной особенностью этого метода является то, что если возможно построить граф без пересечений рёбер, то метод барицентров построит его без них. А в противном случае пересечений будет не более, чем в <tex> 3 </tex> раза больше, чем минимальное число пересечений.
 
  
 
== Примечания ==
 
== Примечания ==
Строка 54: Строка 53:
 
== Источники информации ==
 
== Источники информации ==
  
* [http://rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout/dag-planarization-2007 Построение изображений ациклических ориентированных графов]
+
* ''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