Нахождение корня, который минимизирует глубину дерева

Question

Предоставление дерева, которое не содержит циклов (например, минимальное связующее дерево: http://fr.wikipedia.org/wiki/Fichier:Minimum_spanning_tree.svg) Как рассчитать, какой узел минимизирует глубину дерева, если он используется в качестве корневого?

Answer 1

Все деревья не содержат циклов.По определению, дерево является циклическим связным графом.Если есть одна вершина, ответ тривиален.Итак, предположим, что есть как минимум две вершины.

Позвольте u и v быть двумя вершинами, так что их расстояние d ( u, v ) - максимум.Должно быть легко увидеть, что если выбрать корень вдоль кратчайшего uv в качестве корня, глубина будет составлять не менее потолок ( d ( u , v ) / 2).Также следует отметить, что если выбрать вершину, которая не является корнем на этом пути, глубина будет больше, чем потолок ( d ( u , v ) / 2).

Предположим, что мы выбрали корень r в качестве средней вершины вдоль минимального uv пути, такого, что d ( u , r ) = потолок ( d ( u , *)1049 * v ) / 2) и d ( r , v ) ≤ потолок ( d ( u , v ) / 2).Если была другая вершина, w , такая, что d ( r , w )> потолок ( d ( u , v ) / 2), у нас будет d ( u , r) <<em> d ( w , r ), а затем, поскольку между любыми двумя различными вершинами дерева существует только один путь, мы имеем d ( u , v ) = d ( u , r ) + d ( r , v ) <<em> d ( u , r ) + d ( r , w ) = d ( u , w ), чтопротиворечит тому, что u и v имеют наибольшее расстояние.Так что теперь глубина, заданная r в качестве корня, составляет потолок ( d ( u , v )/ 2).

Итак, нам нужно найти две вершины с наибольшим расстоянием.Как только мы это сделаем, мы можем использовать алгоритм поиска кратчайшего пути для uv , отметить длину и пройти половину пути вдоль указанного пути и использовать эту среднюю вершину в качестве корня.

Как мы находим эти вершины?Выберите вершину w и поместите ее в очередь.Пока очередь не пуста, добавьте соседей следующей вершины в очереди в конец очереди.Когда очередь пуста, обратите внимание на последнюю удаленную вершину.Это будет u .Выполните процедуру еще раз, и у вас будет v .

Почему это работает?Приведенный выше алгоритм находит самую дальнюю вершину из w .Если w окажется u или v , алгоритм явно найдет v или u , соответственно.Предположим, что w не является ни u , ни v .Если алгоритм обнаружил u или v на первом проходе, он снова будет работать (так как он найдет другой на втором проходе), поэтому предположим, что противоречието, что после первого прохода он нашел x такой, что это не конец максимального пути для дерева.Из неравенства треугольника получаем d ( u , v ) ≤ d ( u , w ) + d ( w , v ) и d ( v , x ) ≤ d ( v , w ) + d ( w , х ).Вычитая второе из первого, мы имеем d ( u , v ) - d ( v , x ) ≤ d ( u , w ) - d ( w , х ).Затем мы можем изменить это на d ( u , v ) + d ( w , x ) ≤ d ( u , w ) + d ( v , х ).Поскольку d ( w , u ) ≤ d ( w , x )( x - это конец максимального пути от w ; wu не может превышать wx ) и d ( v , x ) <<em> d ( u , v ) ( x isне конец максимального пути), мы можем усилить неравенство до d ( u , v ) + d ( w , x ) <<em> d ( u , v ) + d ( ш , х ).Однако это невозможно, поэтому x должно быть в конце максимального пути.

Answer 2

Найдите диаметр дерева, после чего выберите средний узел диаметра в качестве корня. Для определения диаметра запустить две BFS, первая BFS начинается со случайного узла v и находит самый дальний узел из v, назовите его x, вторая BFS находит самый дальний узел из x назовите его y. Теперь путь между x и y является диаметром.

Answer 3

Я думаю, что следующий алгоритм может работать (я не проверял его), начиная с любого древовидного представления вашего графа.

S = set of all leaves of the tree
foreach node in S: mark(node)
repeat:
  # at each iteration, S is the set of all nodes at
  # a given min distance to a leave
  # initially this distance is 0, then 1, etc.
  S' = empty set
  foreach node in S:
    parent = parent(node)
    if !marked(parent): S' += parent; mark(parent)
  if S' is empty then S contains all innermost nodes, we are done
  S = S' and continue