51
правка
Изменения
Нет описания правки
Назовём лист бамбука вершиной <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> существуют.
}}
== Применение ==
'''Метод барицентров''' (англ. ''barycenter heuristic'') используется в одном из этапов визуализации ориентированных ациклических графов. Сначала в графе находятся множества вершин <tex> - </tex> '''уровни''' (англ. ''layers''). Уровни ищутся так, чтобы рёбра между вершинами разных уровней шли в неубывающем или невозрастающем направлении по вертикали или горизонтали. После того, как найдены уровни, нужно уменьшить число пересечений между рёбрами. Одна из используемых эвристик и есть <tex> - </tex> метод барицентров. Его суть заключается в том, чтобы координаты вершины определялись как среднее арифметическое координат смежных вершин предыдущего уровня. Важной особенностью этого метода является то, что если возможно построить граф без пересечений рёбер, то метод барицентров построит его без них. А в противном случае пересечений будет не более, чем в <tex> 3 </tex> раза больше, чем минимальное число пересечений.
== Примечания ==
== Источники информации ==
* [httpshttp://wwwrain.macalesterifmo.eduru/~abeveridcat/papersview.php/tree.pdf Andrew Beveridge {{theory/graph-coloring-layout/dag-planarization-}} Centers for Random Walks on Trees2007 Построение изображений ациклических ориентированных графов]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Основные определения теории графов]]
