Изменения

|definition = '''Барицентром дерева''' (англ. ''Tree 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> в рёбрах.

|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> t \in Y </tex> из <tex> x </tex> всегда единственный и представим следующим образом:<tex> d(x) = d(\rightarrow y) + |Y| - |Z| - |X| \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>.

|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> dg_p(x) : \mathbb{N} \rightarrow V_G </tex>, вообще говоря, не является непрерывной, но её можно доопределить так, чтобы на интервале которая по номеру вершины в пути <tex> (a, b) p </tex>, где находит саму вершину. В дальнейшем <tex> d(a, b \in \mathbb {N} ) </tex> она соединяла значения будем считать как <tex> d(g_p(a) ) </tex> для некоторого рассматриваемого пути <tex> p </tex> и . Доопределим функцию <tex> d(bx) </tex> отрезком. Для доказательства непрерывности нам интересна только середина этого отрезкатак, то есть чтобы в точке <tex> a + \displaystyle \frac{a+b1}{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>, сохраняя инвариант.

|proof= Рассмотрим дерево, построенное следующим образом: к вершине дерева <tex> x </tex> проводим подвесим <tex> n + 1 </tex> ребро, <tex> n </tex> из которых проведено свободных вершин (в листья дерева, а одно ребро продолжим достраивать как дереве они станут листьями) и бамбук, расстояние в котором от листа до <tex> x </tex> назовём числом <tex> l </tex>. Докажем, что существуют такие <tex> mn, 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> 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 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> mn, l </tex> существуют.

== Применение =='''Метод барицентровЗамечание''' (англ. ''barycenter heuristic'') используется в одном из этапов визуализации ориентированных ациклических графов. Сначала в графе находятся множества вершин : доказательство существования такого <tex> - n </tex> '''уровни''' (англ. ''layers''). Уровни ищутся так, чтобы рёбра между вершинами разных уровней шли в неубывающем или невозрастающем направлении по вертикали или горизонтали. После тоговершина <tex> x </tex> была барицентром можно было проводить и менее строго, как найдены уровниведь очевидно, нужно уменьшить число пересечений между рёбрами. Одна из используемых эвристик и есть что при больших <tex> n </tex> у барицентра должно быть минимальное расстояние до <tex> - n </tex> метод барицентровлистьев. Его суть заключается в том, чтобы координаты вершины определялись как среднее арифметическое координат смежных вершин предыдущего уровня. Важной особенностью этого метода И такой вершиной и является то, что если возможно построить граф без пересечений рёбер, то метод барицентров построит его без них. А в противном случае пересечений будет не более, чем в <tex> 3 x </tex> раза больше, чем минимальное число пересечений.

* [http://rain''Melnikov O.ifmo''.ru/cat/view«Exercises in Graph Theory» — «Springer», 2013 г.php/theory/graph— 47-coloring48 стр. — ISBN 978-94-layout/dag017-planarization1514-2007 Построение изображений ациклических ориентированных графов]0